2
$\begingroup$

If a particle performs a random walk on the vertices of a cube, what is the mean number of steps before it returns to the starting vertex S? What is the mean number of visits to the opposite vertex T to S before its first return to S and what is the mean number of steps before its first visit to T?

Nobody ever explained random walks to me, so I find it all very odd right now. Maybe someone can explain how to handle these problems or you can link me to a site where these kinds of problems are explained well? Thanks a lot!

$\endgroup$
  • $\begingroup$ Not really an answer but the vertices of a cube can be labeled as a 3-digit binary #. So one step of the random walk is equivalent to randomly choosing 1 digit and flipping it. That allows us to move to a random neighbouring point at each timstep. $\endgroup$ – Dan May 3 '15 at 20:31
  • 1
    $\begingroup$ More generally, for a random walk on a finite connected undirected graph, the expected return time is $2n/d$ where $n$ is the number of edges and $d$ is the degree of the starting vertex. For the cube you have $n=12$ and $d=3$ so the answer is $8$. $\endgroup$ – bof May 3 '15 at 21:43
4
$\begingroup$

The vertices of a cube(oid) can be labelled with 3-digit binary numbers since there are $8$ corners and $2^3=8$. To keep things simple lets say that we are considering the unit cube and the binary number correspond directly to the coordinates, so that vertce $000$ is at $(0,0,0)$, vertex $010$ is at $(0,1,0)$ and so forth. Taking one step on the random walk is equivalent to picking one digit with uniform probability of $1/3$ from our binary number and flipping it.


W.l.o.g. let us consider starting at $000$, let us say that the expected time to return to $000$ is $x$. Now consider the three vertices $001$,$010$ and $100$, they are all one step away from the start. Let's say the expected time to return to the start from here is $y$. Similarly consider the vertices with two ones $110$, $101$ and $011$. These are all two steps away from the start. Let us say that the expected time to get back to $000$ from here is $z$.

How can we link all of these together? Well, if we are at one of the vertices $001$, $010$ or $100$ we have a $1/3$ probability of returning to the start and a $2/3$ probability to go to one that is two steps away. This gives us $$y = \frac{1}{3} + \frac{2}{3}(z+2)$$ To make sense of this, see that we have a 1/3 probability to be finished, otherwise we are at a vertex two steps away (whose expected time is $z$) but we took two steps to get there (hence $z+2$). We can perform a similar process for the vertices $011$, $101$ and $110$. Here we have a $2/3$ probability to return to a vertex one step from the start and a $1/3$ prob. to go to $111$, but at $111$ our only option is to back to one of the vertices two steps away and so the corresponding equation reads $$z = \frac{2}{3}(y+1) + \frac{1}{3}(z+2)$$ Using these we can solve to get $y=7$. Now clearly from $000$ we can only reach vertices one step away, for which we already know the expected time to return to $000$ is 7. Thus our expected time to return to $000$ is $x=y+1=8$.

Although our discussion focused on starting from $000$ there was nothing special about this choice other than to keep the number of ones equal to the steps away from the start and thus it holds for any starting vertex the expected number of steps to return is $8$.


I decided to check whether this answer is correct using Monte-Carlo. With 1,000,000 trials the answer came out as 7.99 (3 s.f.).

$\endgroup$
  • $\begingroup$ A nice analysis that takes full advantage of the symmetry of the cube. $\endgroup$ – Marconius Jul 3 '15 at 13:47
  • $\begingroup$ but if you solve your equations then you will get $y=9 $ and $z=11$ and also can you please explain your equation for $z$ $\endgroup$ – bunny Dec 8 '17 at 17:19
  • $\begingroup$ You're right. Perhaps I was back-rationalising my empirical answer. The mistake is the equation for $y$ which should be $y=\frac{1}{3} + \frac{2}{3}(z+1)$ because it took us only 1 set to get "to" $z$ "from" $y$, the initial step from $000$ is of course already accounted for in $y$. If you solve this you should find $y=7$. $\endgroup$ – Dan Dec 8 '17 at 17:48
0
$\begingroup$

This random walk, like many others, can be modeled by using a Markov chain. See Chapter 11 of the on-line probability book by Grinstead and Snell (it can be freely downloaded). You need to know a bit of linear algebra to understand Markov chain theory.

$\endgroup$

Your Answer

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