## Simulating random walk with actions

Hi,

I've created a markov transition matrix that I now want to simulate. Attached should be a picture of a simplified verision of it. There's many more starting and ending states along with more results, but it's essentially just an expanded version of this. To explain, I'd like to simulate a walk through this a number of times. Each time it reaches an end state that ends with 3, it would reset back to it's starting state, 0_0. In the walk, if a certain transition hapens, then a number of points are added, as shown in the table to the right. The purpose of the walk would be to simulate a game and output the final point counts for each walk.

What's the best way to have sas walk through the data as well as keep track of the results?

1 ACCEPTED SOLUTION

Accepted Solutions

## Re: Simulating random walk with actions

Here is an example using the smaller 6x6 matrix. Notice that I have included rows for the final states.

The main ideas are

1. Create a POINTS matrix that contains the number of point that you get when you transition from state S to state T

2. For each game, iterate the transition matrix in a DO WHILE loop until you land in one of the ending states. Accumulate points (and maybe other statistics like number of turns) as you go.

3. When you have successfully implemented one game, put a loop DO game = 1 to NUMGAMES around the iteration.

``````proc iml;
M = {0.05 0.66 0    0    0.29 0    0    0,    /* 00 */
0    0.05 0.67 0    0    0.28 0    0,    /* 01 */
0    0    0.02 0.68 0    0    0.30 0,    /* 02 */
1    0    0    0    0    0    0    0,    /* 03 */
0.2  0.03 0.11 0    0.58 0.08 0    0,    /* 10 */
0    0.02 0.03 0.14 0    0.33 0.48 0,    /* 11 */
0    0    0.02 0.18 0    0    0.21 0.59, /* 12 */
1    0    0    0    0    0    0    0  }; /* 13 */

points = I(nrow(M));   /* identity matrix */
points[5,1] = 2;       /* set off-diagonal elements of transitions */

/* row M[i, ] contains probabilities for transitioning from state i */

/* play one game */
state = 1;  /* start in state 1 */
cnt = 1;
pts = 0;      /* points for this game */
do while (state ^= 3 & state ^= 6);
newState = randfun(1, "Table", M[state,] );  /* new state */
pts = pts + points[state, newState];
cnt = cnt + 1;
state = newState;
end;

print pts cnt state;
``````
9 REPLIES 9  Ksharp
Super User

## Re: Simulating random walk with actions

calling @Rick_SAS

## Re: Simulating random walk with actions

The easiest way is to use the SAS/IML matrix language, since applying a transition matrix to the current state is a matrix-vector computation. To get started, see the example in the article

"Markov transition matrices in SAS/IML"

## Re: Simulating random walk with actions

So then how would I incoroprate the results into that?

## Re: Simulating random walk with actions

You need to tell us your level of expertise and the tools you have available.  If you have SAS/IML and know about matrix operations, I can move this discussion to the SAS/IML Support Community.

If you prefer to use the DATA step to solve this problem, then say so and someone can help you use arrays to solve this problem.

In either case, you are going to use the "Table" distribution to generate the next state from the current state,  The rows of the transition matrix give the probability of transitioning to the other states. I recommend that you add two other rows for the transition to the 03 and 13 states.

In matrix notation, if M is the 8x8 transition matrix and s is the current state of the system, then

s = randfun(1, "Table", M[s, ]);

updates the state.  You just need to put it in a loop and add logic to accumulate points.

## Re: Simulating random walk with actions

Hi Rick, thanks for your help. I do have some experience with SAS, but am nowhere near being an expert. I do have SAS/IML and have a basic understanding of matrix operations. I think the article you linked to helped clarify a few points. The image posted was just a simplification of what we actually have. Attached is a more accurate representation of the matrix, which is actually 24 rows by 32 columns. Currently they're displaying the row cumulative percent which I think is the harder method you talk about in the article. Between your article and some more reading what we have in mind is running a loop to generate a random number to select our first end state. We would then set the end state as our next start state and repeat the process, as certain end states can only be reached from a particular start state. For a more concrete example: suppose we start at state 0_0 then transtition to 1_0. The probabilities of transitioning out of 1_0 are stored in that row. Thus we would want to generate another random number to select our end state, which then becomes our next row. Is that possible to do in both the data step or IML, or is there a better way to approach this?

Thank you.

## Re: Simulating random walk with actions

Here is an example using the smaller 6x6 matrix. Notice that I have included rows for the final states.

The main ideas are

1. Create a POINTS matrix that contains the number of point that you get when you transition from state S to state T

2. For each game, iterate the transition matrix in a DO WHILE loop until you land in one of the ending states. Accumulate points (and maybe other statistics like number of turns) as you go.

3. When you have successfully implemented one game, put a loop DO game = 1 to NUMGAMES around the iteration.

``````proc iml;
M = {0.05 0.66 0    0    0.29 0    0    0,    /* 00 */
0    0.05 0.67 0    0    0.28 0    0,    /* 01 */
0    0    0.02 0.68 0    0    0.30 0,    /* 02 */
1    0    0    0    0    0    0    0,    /* 03 */
0.2  0.03 0.11 0    0.58 0.08 0    0,    /* 10 */
0    0.02 0.03 0.14 0    0.33 0.48 0,    /* 11 */
0    0    0.02 0.18 0    0    0.21 0.59, /* 12 */
1    0    0    0    0    0    0    0  }; /* 13 */

points = I(nrow(M));   /* identity matrix */
points[5,1] = 2;       /* set off-diagonal elements of transitions */

/* row M[i, ] contains probabilities for transitioning from state i */

/* play one game */
state = 1;  /* start in state 1 */
cnt = 1;
pts = 0;      /* points for this game */
do while (state ^= 3 & state ^= 6);
newState = randfun(1, "Table", M[state,] );  /* new state */
pts = pts + points[state, newState];
cnt = cnt + 1;
state = newState;
end;

print pts cnt state;
``````

## Re: Simulating random walk with actions

Rick, that worked perfectly; thank you. I just have one more question, then I should be set.

Currently our transition matrix is rectangular. Is this a valid workaround, or do we need to add rows to make it square?

``````state = 1; /* start in state 1 */
cnt = 1;
pts = 0; /* points for this game */
sentinel = 0;

do while (sentinel ^= 1);
newState = randfun(1, "Table", M[state,] ); /* new state */
pts = pts + points[state, newState];
cnt = cnt + 1;
if (newState = 3 | newState =6) then sentinel = 1;
state = newState;
end;``````

## Re: Simulating random walk with actions

It looks fine. You can try it and see if it works.

You are free to use non-square matrices.  If you only have two states, you might consider using

do while (newState ^= 3 & newState ^=6);

but if you are going to have many states that end the game then your 'sentinel' way is probably clearer.  Ksharp
Super User

## Re: Simulating random walk with actions

Under the @Rick_SAS 's guidance, it seems it is very easy.

``````data x;
input _1-_6;
cards;
0.05 0.66 0 0 0.29 0
0 0.05 0.67 0 0 0.28
0 0 0.02 0.68 0 0.3
0.2 0.03 0.11 0 0.58 0.08
0 0.02 0.03 0.14 0.48 0.33
0 0 0.02 0.18 0.21 0.59
;
run;
data point;
input s e point;
cards;
1 2 1
1 1 1
2 2 1
1 4 2
;
run;

%let start=1;
%let steps=20;

proc iml;
use x;
read all var _all_ into x;
close;
use point;
read all var {s e point};
close;

start=&start;
points=0;
call randseed(12345678);
do i=1 to &steps;
end=randfun(1, "Table", x[start, ]);
idx=(s=start & e=end);
if any(idx) then points=points+point[loc(idx)];

msg="steps="+char(i)+",start="+char(start)+',end='+char(end)+',points='+char(points);
print msg;

if end=3 then start=&start;
else start=end;

end;

quit;``````

Discussion stats
• 9 replies
• 1097 views
• 2 likes
• 3 in conversation