1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Random walk on circle

  1. Mar 24, 2013 #1
    1. The problem statement, all variables and given/known data
    Consider a random walk on a circle of N points, labeled {0,1,...,N-1}. Let the initial state be X = 0 and define T to be the first time all points have been visited at least once. Show that the distribution of X[T] (i.e. last unique position visited) is uniform over {1,...,N-1}.

    3. The attempt at a solution
    I understand the basic formulas for Markov chains; including absorption probabilities, invariant distribution, and return times. The book makes an analogy to the Gambler's Ruin problem to show E[T] = N(N-1)/2. Still, I don't know where to start.

    Thanks for the help,
  2. jcsd
  3. Mar 26, 2013 #2
    I made some progress. I borrowed a result from the Gambler's Ruin problem: For the finite segment {0,...,n} the probability of being absorbed to x = n starting from x = 1 is 1/n. Knowing this, I can consider the state of the random walk on a circle by how many unique points have been discovered, and whether the last discovery was a counterclockwise point (akin to x = n) or a clockwise point (akin to x = 0). For clarity, I attached a picture of the corresponding Markov chain. Then, the final discovered point is determined by how this Markov chain is traversed. If the last discovered point is x = 1, then the Markov chain must have made a CW choice at each step. That has probability p = 1/2 * 2/3 * 3/4 ... * (N-2)/(N-1) = 1/(N-1). For x = 2 there must have been one CCW step. There are N-2 possibilities for this, i.e. p = sum( 1/2*2/3* ... (k-2)/(k-1) * 1/k *1/(k+1) * (k+1)/(k+2) * ... * (N-2)/(N-1) for k=2..N-2) + (special case for k is N-1) = sum( 1/(k(k-1)(N-1)) for k = 2 .. N-2 ) + 1/((N-2)(N-1)) = 1/(N-1) sum( 1/(k-1) - 1/k for k = 2 .. N-1 ) + 1/((N-2)(N-1)) = 1/(N-1). So for x = 1 and x = 2, the probability is p = 1/(N-1) as expected. But this expression gets cumbersome for larger x. There must be an easier way to prove this.

    Attached Files:

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted