3D Random Walk Within a Unit Cube

Question

You start at point (0,0,0) and are within a unit cube meaning the values for x, y, z are all either 0 or 1 at any time.

You move with equal chance of taking 1 step in x, y or z axes.

How do you work out the probability that after X steps you are at (1,1,1)?

Produce an equation to work out the probability of being at (1,1,1) after X steps.

---

So far I know that all odd number of steps can get to (1,1,1) except 1 step. Each step is either +1 or -1 in the axis you travel depending on if you are at 0 or 1.

I have done 1d and 2d random walks but not sure how to input them into a fixed space like this and make it a 3d random walk.

Answer 1

If we understand the question to ask for a formula in terms on $n$ to be at the vertex $(1,1,1)$ after $n$ steps, the answer is $0$ if $n$ is even and $1/4 - (3/4) 3^{-n}$, which can be seen by exploiting the fact that the tuple $(A,B,C)$ counting the number of flips in the $x$, $y$, and $z$ coordinate directions has a multinomial distribution, so $E u^A v^B w^C = ((u+v+w)/3)^n.$ The desired probability is the sum of just the terms in this polynomial in which $u$, $v$, and $w$ each appear with an odd exponent, evaluated at $u=v=w=1$. Using the trick that for a polynomial $P(t)$, the polynomial $(P(t)-P(-t))/2$ is its odd part, once for each of the variables $u$, $v,$ and $w$, on the polynomial $(u+v+w)^n$, we arrive at the a combination of terms like $(1+1+1)^n - (1+1-1)^n \dots$ which is straightforward but too tedious to write out in full here. The final result is $$ p_n = \frac{(3)^n -3 (1)^n + 3(-1)^n - (-3)^n}{8\cdot 3^n},$$ which vanishes if $n$ is even, and reduces to the formula stated above if $n$ is odd.

Answer 2

This can be done directly with stochastic transition matrices. You are in 1 of 4 states:

• Initial vertex
• Adjacent to initial vertex
• Adjacent to target vertex
• Target vertex

If you are in the initial vertex, there is a 100% chance of transitioning to an adjacent vertex. If you are adjacent to the initial vertex, there is a 1/3 chance of transitioning to the initial vertex, 2/3 chance of transitioning to a vertex adjacent to the target vertex. If you are at a vertex adjacent to the target vertex, there is a 2/3 chance of transitioning to a vertex adjacent to the start, and a 1/3 chance of hitting the target. If you are at the target vertex, there is a 100% chance of transitioning to an adjacent vertex. In summary, the transition matrix is:

$$M = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1/3 & 0 & 2/3 & 0 \\ 0 & 2/3 & 0 & 1/3 \\ 0 & 0 & 1 & 0 \end{bmatrix}$$

So the probability of transitioning from state $i$ to state $j$ after $n$ steps is exactly:

$$P_n = \left(M^n\right)_{i, j}$$

Since we are only interested in odd $n$ (and it makes the problem easier), and we only care about going from state 1 to 4, we only have to consider

$$P_{2k+1} = \left(M^{2k+1}\right)_{1, 4} = M\left(M^2\right)^k{}_{1,4}$$

So finding the result entirely comes down to diagonalizing $M^2$. The eigenvalues are $\{1, 1, 1/9, 1/9\}$ so

$$M^2 = PDP^{-1}$$ for $$P = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1/3 & 0 \\ 0 & 1 & 0 & -3 \end{bmatrix}$$ $$D = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1/9 & 0 \\ 0 & 0 & 0 & 1/9 \end{bmatrix}$$

So $$P_{2k+1} = \left(MPD^kP^{-1}\right)_{1,4} = \frac{1}{4}\left(1 - \frac{1}{9^k}\right)$$