Suppose i have a circular array of $n$ elements. At time $t=0$ i am in position 0 of the array. The algorithm moves left or right with probability $p=1/2$ (since the array is circular when it moves left from 0 it goes to position $n$). When i visited all the positions at least once the algorithm returns the position it terminated into.
Launching the algorithms many times shows that it stops with the same probability in any of the n positions (except for zero obviously). How do i demonstrate that the probability of ending up in each state is uniform?
My understanding is that this process is explained by a doubly stochastic Markov chain, but is there a theorem i can quote about this specific case?

  • $\begingroup$ Frankly, I don't see a lots of CS here. Plenty of Mathematics, but very little Computer Science. Perhaps try the Math site instead? $\endgroup$ Jan 28 '20 at 15:48
  • $\begingroup$ it's from an advanced algorithm course in a computer Science degree. Usually when an algorithm is commissioned it's also asked to prove its correctness, that's why i'm posting it here. $\endgroup$
    – toploz
    Jan 28 '20 at 15:55
  • 1
    $\begingroup$ Just to give reference, this is exercise 7.26 from the book Probability and Computing: Randomized Algorithms and Probabilistic Analysis. $\endgroup$
    – Laakeri
    Jan 28 '20 at 21:55

We can imagine simulating the random walk on an infinite line, keeping track of the "extension", which is the distance between the rightmost point visited and the leftmost point visited. Let $\ell(a,b)$ denote the probability that the extension became $b-a$ due to a move to $a$, and let $r(a,b)$ denote the probability that the extension became $b-a$ due to a move to $b$. When $a=b=0$, we arbitrarily define $\ell(0,0) = 1$ and $r(0,0) = 0$.

If we are at the situation counted by $\ell(a,b)$, then known formulas show that we move to the situation counted by $\ell(a-1,b)$ with probability $1-1/(b-a+2)$, and to the situation counted by $r(a,b+1)$ with probability $1/(b-a+2)$. Together with an analogous argument for $r(a,b)$, this gives the recurrences $$ \ell(a,b) = \left(1 - \frac{1}{b-a+1}\right) \ell(a+1,b) + \frac{1}{b-a+1} r(a+1,b), \\ r(a,b) = \frac{1}{b-a+1} \ell(a,b-1) + \left(1 - \frac{1}{b-a+1}\right) r(a,b-1). $$ We want to show that for $i=1,\ldots,n-1$, $$ r(i-n+1,i) + \ell(i-n,i-1) = \frac{1}{n-1}. $$ We will prove the stronger result $$ r(i-n+1,i) = \frac{i}{n(n-1)}, \\ \ell(i-n,i-1) = \frac{n-i}{n(n-1)}. $$ When $n=2$, we need to show $$ r(0,1) = \ell(-1,0) = \frac{1}{2}, $$ which can be checked directly. For $n > 2$, we have $$ r(i-n+1,i) = \frac{1}{n} \ell(i-n+1,i-1) + \frac{n-1}{n} r(i-n+1,i-1) = \\ \frac{1}{n} \frac{n-i-1}{(n-1)(n-2)} + \frac{n-1}{n} \frac{i-1}{(n-1)(n-2)} = \frac{i}{n(n-1)}, $$ and similarly $$ \ell(i-n,i-1) = \frac{n-1}{n} \ell(i-n+1,i-1) + \frac{1}{n} r(i-n+1,i-1) = \\ \frac{n-1}{n} \frac{n-i-1}{(n-1)(n-2)} + \frac{1}{n} \frac{i-1}{(n-1)(n-2)} = \frac{n-i}{n(n-1)}. $$ (We don't really need to calculate the two cases separately, since symmetry arguments show that $r(i-n+1,i) = \ell(-i,n-i-1)$.)

  • $\begingroup$ An ingenious proof to a marvelous phenomenon! $\endgroup$
    – John L.
    Mar 21 '20 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.