Imagine $5~ by~ 5$ squares. Your character piece starts in the very middle $(0,0)$. The rules allow the character to only move up, down, left, or right, and also not to move at all ($5$ total options).

How can I figure the probability of returning to $(0,0)$ after $X$ attempts? This is assuming I have equal probability of choosing one of the $5$ possible moves.

What is the probability that the character will be touching a wall after $X$ tries? (If the character is touching the east wall and is told to move east, it will stay in place)

Trying to illustrate this in Java, so formulas will suffice for an answer.

  • $\begingroup$ This might be helpful. $\endgroup$ – jay-sun Feb 5 '13 at 19:28
  • $\begingroup$ Find the eigenvalues and eigenvectors of the $25\times 25$ transition matrix. $\endgroup$ – mjqxxxx Feb 5 '13 at 19:35
  • $\begingroup$ You can use symmetry if all you care about is hitting the edge or returning to center. Then there are only $6$ distinct squares, so the matrix is only $6 \times 6$ $\endgroup$ – Ross Millikan Feb 5 '13 at 19:46
  • $\begingroup$ mjqxxxx, please elaborate. $\endgroup$ – Silvius Feb 5 '13 at 20:02

Probability For an N x N square:

There exist 5^x different paths can be taken:

A walk consists of of a word of up's (1), down's (-1), left's (-i), rights (i) and waits (0) such that that the sum of the elements in the word = 0 and the word is of length X, (has x elements)

Note that a walk can be broken into two parts: an actionable part and wait part. Actionable parts must have even length, as every decision to take a non-waiting move must eventually be undone at a later stage. The wait part is all the instances when waiting did occurred.

We consider the first case where X is odd:

We can have actionable parts of length 0, 2, 4, 6 ... X -1 respectively:

Each of these actionable parts has a total of 2 * rC2 * 2 * (r-2)C2 * 2 * (r - 4)C2 ... different arrangements which creates r! ways to arrange an actionable part of length r.

Therefore we know there exist 0! 2! 4! 6! ... (x - 1)! actionable parts correspondingly.

This can also be derived as: for an even integer I have r spots for the first move, r - 1 for the next unmove, etc...

Now for each of these actionable parts we must compute the number of ways to take its elements and then place on the x possible locations. That of course can be accomplished in x!/(x-r)! ways for each of the r! possible walks therefore we have:

x!0!/(x-0)! + x!2!/(x-2)! + x!4!/(x-4)! ...+ x!(x-1)!/1! possible ways to arrange actionable parts. The factorial function + while loop + a factorial function can quickly calculate this. For the probability we will denote the above sum as S(x). Simply compute S(x)/5^x to be done.

In the case of X being even, actionable parts can be computed as being either:

0, 2, 4 ... X moves and therefore there exist:

x!0!/(x-2)! + x!2!(x-2)! ... x!x!/0! possible ways to arrange the actionable parts.

Pseudo-code style:

Make a Factorial Method, we'll call it fact(x)

if x is odd then x = x - 1: else x = x

start a while loop with index at 0

while index <= x - 1: sum = sum + x!i!/(x-i)!

finally print sum/5^x.

I'm sure this can be optimized. I don't know how atm.

  • $\begingroup$ for fixed N one needs to account additionally for the fact that only a finite number of "moves" can be made before an "unmove" must be made as there do exist finite walls $\endgroup$ – frogeyedpeas Feb 5 '13 at 21:24
  • $\begingroup$ You are a scholar and a gentleman. Thank you. $\endgroup$ – Silvius Feb 5 '13 at 21:47
  • $\begingroup$ frog, is your answer based on a Markov chain, or is it your own method? Doesn't matter to the answer, just curious. $\endgroup$ – Silvius Feb 6 '13 at 19:04
  • $\begingroup$ Self derived method... Idk what Markov Chains are but I'm pretty sure this is probably the same thing as that, just idk how $\endgroup$ – frogeyedpeas Feb 10 '13 at 1:56

A general approach may encompass the usage of Markov-chains which may be used to model the random walk you are talking about. In your case of a 5x5 board, the matrix $\mathbf{A}$ of this model will be from $\mathbb{R}^{25,25}$ as there are 25 states.

When you fill this matrix with all the transition probabilities (each row will have from 3 to 5) non-zero elements (3 for the corner elements, 5 for the elements in the middle).

You can get the probability distribution of the states after one move $p'$ given the probability distribution before this move ($p$) by following formula: $p' = \mathbf{A}p$. As you are interested in the probability of getting back to the $i$-th state starting at the same state after $x$ steps, you can do following calculation: $p' = \mathbf{A}^xp$, where the vector $p$ has all elements zero except the $i$-th one. The probability you are looking for is the $i$-th element of the vector $p'$.

As for the case of touching the wall, you will just focus on other elements in the $p'$ vector.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.