Mathematics desk
< June 19	<< May \| June \| Jul >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 20

Random walk on a 2d rectangle graph

I have a 2d rectangle graph with 4 vertices: A,B, C, D. An agent start moving from an initial position p0∈{A,B,C,D}, either clockwise or counterclockwise. When encountering the vertex A, it can change its movement direction with probability of 0.5. How can I calculate the probability the agent will be at position P after t time steps? intuitively I guess after long enough time the probability to be in each of the 4 positions is approximately equal, but I am looking for an analytical solution. I am especially in a modeling that can be extended to other movement schems (i.e. various "direction flipping" points or other probabilities for changing the direction). Thanks! — Preceding unsigned comment added by 77.125.59.241 (talk) 16:09, 20 June 2017 (UTC)[reply]

You probably want to have a look at Markov chains. --Deacon Vorbis (talk) 16:28, 20 June 2017 (UTC)[reply]

If t = 0 mod 4 then the agent must be at vertex A, and if t = 2 mod 4 then it must be at position C. Gandalf61 (talk) 16:32, 20 June 2017 (UTC)[reply]

Please notice agents don't necessarily start at A, and change movement direction randomely when visiting point A. 77.125.59.241 (talk) 16:44, 20 June 2017 (UTC)[reply]

I think this works: Label the positions with their numerical values 4, 3, 2, 1, such that the initial direction of movement is toward a lower number with wraparound. Let x_n be the position after n moves (n≥0). Then for ~~n≥1~~ n≥x_0 we have:

If n = x_0 + 4k, Pr(x_n=4)=1;

If n = x_0 + 4k ± 2, Pr(x_n=2) = 1;

If n = x_0 + 4k ± 1, Pr(x_n=1) = 1/2 = Pr(x_n=3).

Loraof (talk) 19:29, 20 June 2017 (UTC)[reply]

can you please explain how did you derive this? — Preceding unsigned comment added by 77.125.59.241 (talk) 20:42, 20 June 2017 (UTC)[reply]

I set it up so after n= x_0 iterations, we are at the value 4 with certainty. After that, every four more iterations in either direction brings us back to the value 4 with certainty. From value 4, two iterations more or less in either direction would leave us at 2 with certainty, whereas from 4 one iteration more or less moves us left or right, and hence to value 1 or 3, with the equal probablilties you gave as 0.5. (Note that I have changed the above slightly so that it applies for n ≥ x_0, since smaller numbers of iterations give a deterministic result.) Loraof (talk) 22:09, 20 June 2017 (UTC)[reply]

thanks! — Preceding unsigned comment added by 77.125.59.241 (talk) 19:38, 21 June 2017 (UTC)[reply]