Start a random walk on a vertex of a cube, with equal probability going along the three edges that you can see (to another vertex). what is the expected number of steps to reach the opposite vertex that you start with?


$\hskip1.75in$ enter image description here

A random walk on the cube has eight states, but by symmetry we can reduce this to four states: start, nearest neighbors, further neighbors, and opposite. The "boundary" is the single state {o}.

enter image description here

Define $h$ as the expected time to hit the boundary starting at $x$, i.e., $h(x)=\mathbb{E}_x(T).$

First step analysis gives \begin{eqnarray*} h(s)&=&1+h(n)\vphantom{1\over3}\\[3pt] h(n)&=&1+{1\over3}\, h(s)+{2\over 3}\, h(f)\\[3pt] h(f)&=&1+{1\over3}\, 0+{2\over 3}\, h(n). \end{eqnarray*}

You can work out that $h(s)=10$.

  • $\begingroup$ Noting that $h(f)=8-1=7$ speeds things up. $\endgroup$ – A.S. Dec 6 '15 at 14:33
  • $\begingroup$ @A.S. Quite right! $\endgroup$ – user940 Dec 6 '15 at 22:34
  • $\begingroup$ @A.S. why is it better? $\endgroup$ – Marine Galantin Oct 27 '19 at 22:41

It is clear that the expectation is finite. It will be handy to have a cube to play with.

There are $4$ types of vertex: Type A, the vertex we start at; Type B, the ones at distance $1$ from the start; Type C, the ones at distance $2$ from the start; and finally Type D, the vertex opposite from the start.

Let $a$ be the expected number of steps from A to D (this is what we want). Let $b$ be the expected number of (additional) steps to get to D given that we are at a Type B vertex. And let $c$ be the expected number of additional steps given that we are at a Type C vertex.

If we are at A, then with probability $1$, we will be in one step at a Type B vertex, so $$a=b+1.$$

If we are at a tyoe B vertex, then with probability $\frac{1}{3}$ at the next stage we return to A, and with probability $\frac{2}{3}$ we go to a Type C vertex. It follows that $$b=\frac{1}{3}(a+1)+\frac{2}{3}(c+1).$$ Finally, if we are at a Type C vertex, with probability $\frac{2}{3}$ we next go to a Type B, and with probability $\frac{1}{3}$ we get to D. Thus $$c=\frac{2}{3}(b+1)+\frac{1}{3}.$$ We have three linear equations in $3$ unknowns. Solve for $a$.


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.