April 2006
Answer:
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).
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com