IBM Ponder This #096 · April 2006

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.

Solution

Best opened after a real attempt

To be added.