Ponder This Challenge - April 2006 - Random walk on a hypercube

Ponder This Challenge:

Puzzle for April 2006.

This month's puzzle concerns random walks on a n-dimensional hypercube. Each step of the random walk moves from one of the 2**n vertices of the hypercube to one of the n adjacent vertices selected at random. The vertices of a n-dimensional hypercube can be identified with length n 0-1 vectors in an obvious way. Consider random walks starting at the vertex (0,0,....,0). We want to know how many steps on average it will take for the random walk to reach the diagonally opposite vertex. This can be found by answering the following questions.

1. How many steps on average does it take the random walk to return to its starting point?

2. How many steps on average does it take the random walk to return to its starting point or reach the diagonally opposite vertex (ie the vertex (1,1,...,1))?

3. What is the probability that the random walk reaches the diagonally opposite vertex before it returns to its starting point?

4. How many steps on average does it take the random walk to reach the diagonally opposite vertex?

The first 100 people who answer all 4 parts correctly will be listed. The answer will be posted a week after the 100th is received, or at the end of the month.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  April 2006 Solution:

  1. Consider a very long random walk. The walk will occupy each vertex after about 1/2**n of the steps. Therefore the average return time is 2**n steps.

  2. Similarly pair each vertex with its diagonally opposite vertex. A long walk will occupy each pair after about 1/2**(n-1) of the steps. Hence the average return time is 2**(n-1) steps.

  3. Let p(x) be the probability that a random walk starting at vertex x will arrive at vertex (1,1,....,1) before it arrives at vertex (0,0,....,0). Let x=(x1,x2,....,xn). Clearly p(x) will only depend on how many of the xi are 1. Let w(x)=x1+x2+...+xn be the weight of x. Let p(k)=p(x) for x with weight k. Clearly p(0)=0 and p(n)=1. Furthermore p(k)=(k/n)*p(k-1)+((n-k)/n)*p(k+1) for 0<k<n (since a random walk at a vertex with weight k will go next to a vertex with weight k-1 with probability (k/n) or to a vertex with weight k+1 with probability ((n-k)/n)). Let q(k)=p(k+1)-p(k). Then the above equation can be rewritten as (k/n)q(k-1)=((n-k)/k)q(k) or q(k)=q(k-1)*k/(n-k). So q(1)=q(0)/(n-1), q(2)=q(0)*2/((n-1)*(n-2)) etc. Therefore q(k)=q(0)/C(n-1,k) where C(n-1,k) is the binomial coefficient n-1 choose k. Let S(n-1)=Sum 1/C(n-1,k) for k=0,1,...,n-1. We have 1=p(n)-p(0)=q(0)+q(1)+...+q(n-1)=q(0)*S. Therefore q(0)=1/S. Now if a random walk starts at (0,0,...,0) after one step it will be at a vertex of weight 1. So the probability it will reach (1,1,...,1) before returning to (0,0,...,0) is p(1)=p(1)-0=q(0)=1/S. So the answer is 1/S where S is the sum of inverses of the (n-1)th row of Pascal's triangle.

  4. Let T be the average number of steps it takes to reach the opposite corner. By question 2 it takes an average of 2**(n-1) steps to either reach the opposite corner or return to the starting point. By question 3 the walk will return to the starting point a fraction (S-1)/S of the time. So T=2**(n-1)+((S-1)/S)*T. Solving T=S*2**(n-1) where S is defined as above. Note as n goes to infinity S=2+2/n+O(1/n*n) so asymptotically T=2**n + (2**n)/n + O((2**n)/n*n).

Solvers

• Graeme McRae (04.02.2006 @08:44:47 AM EDT)
• Balakrishnan V (04.02.2006 @05:40:21 PM EDT)
• Roberto Tauraso (04.03.2006 @04:43:46 AM EDT)
• Frank Yang (04.04.2006 @10:18:07 AM EDT)
• Dan Dima (04.10.2006 @04:56:12 PM EDT)
• John G. Fletcher (04.10.2006 @07:36:05 PM EDT)
• Zhou Guang (04.10.2006 @10:00:35 PM EDT)
• Jomy (04.15.2006 @03:09:47 AM EDT)
• Jack Kennedy (04.15.2006 @05:58:33 PM EDT)
• Se Kwon Kim (04.16.2006 @11:04:52 PM EDT)
• Frank Mullin (04.19.2006 @08:40:05 AM EDT)
• David Wolfe (04.20.2006 @01:35:10 PM EDT)
• Phil Muhm (04.20.2006 @10:44:16 PM EDT)
• Dinesh (04.21.2006 @02:18:19 PM EDT)
• Dharmadeep Muppalla (04.24.2006 @10:46:54 AM EDT)
• Rubén Hernández Aza (04.24.2006 @03:53:37 PM EDT)
• Bernie R. Erickson (04.24.2006 @05:13:55 PM EDT)
• David McQuillan (04.26.2006 @06:12:35 PM EDT)
• Yurun Liu (04.30.2006 @09:58:25 PM EDT)