IBM四月

constant

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.www.ddhw.com

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?

www.ddhw.com