Random Walk on a Circle: How Does the Last Unique Position Visited Distribute?

[sam_bell]

Homework Statement

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}.

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,
Sam

 

[sam_bell]

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.