Last vertex visited by the symmetric random walk on a discrete circle

$n$ cats form a circle, indexed from $0$ to $n-1$. At first, there is a ball at the cat $0$. We throw a coin with the probability of $p$ heads up. If the coin is heads up, we pass the ball clockwise, otherwise counter clockwise. We repeat this until all cats have touched the ball. What is the probability of the ball finally at the cat $k$?

• Does it count that cat $0$ touched the ball in the beginning? – Marcus M Sep 12 '15 at 15:56
• Yes, thus the probability of the ball finally at the cat 0 is 0 when the number of cats is more than one. – younis Sep 12 '15 at 15:59
• If you can express the probability that you will land on the next unused cat in counter-clockwise position, versus the probability you land on the next unused cat in clockwise position, as a function of how many used cats are between them and your current position, then you can write down a somewhat complicated recursion by always assuming your current position is always on the boundary of the used cats. – user2566092 Sep 12 '15 at 16:02
• Here's a relevant link: math.stackexchange.com/questions/116446/random-walk-on-n-cycle – Marcus M Sep 12 '15 at 16:06
• @user2566092, actually, I don't think it's a duplicate; I think this problem is a generalization of the other problem. The other problem assumes $p = \frac{1}{2}$. – Marcus M Sep 12 '15 at 17:03

The notation is easier if we have $n+1$ cat: $0,1,2,\dots,n$. Assume that $p\neq 1/2$ (the symmetric case is considered here; thanks to @MarcusM for giving a link) and denote $q=1-p$.
Theorem The probability $P_k$ that the ball finishes at cat $k$ is proportional to $(\frac{q}{p})^{n-k}$, i.e. it is equal to $$P_k = \frac{p^{k} q^{n-k}}{\sum_{k=1}^n p^{k} q^{n-k}}, \quad k=1,\dots,n.$$
Proof. Let $W_t$ denote the ball position at time $t$ and let for $k=1,\dots,n$ $$\tau_k = \min\{t\ge 1: W_t = k\}$$ be the first time the ball visits the cat $k$. Let also $\sigma_{k-n-1}$ be the first time when the ball comes to $k$ from the right, i.e. from the cat $k+1$, and $\sigma_k$ be the first time when it comes from the left; obviously, $\tau_k = \sigma_k\wedge \sigma_{k-n-1}$.
The crucial idea (which is very standard when dealing with such kind of walks) is to consider the following martingale: $$M_0 = 1,\quad M_{n+1} = \begin{cases} M_n z, & (n+1)\text{th step is clockwise},\\ M_n/z, & (n+1)\text{th step is counterclockwise}, \end{cases}$$ where $z = q/p$. Let us first compute $P_1$ and $P_n$ using this martingale. Obviously, $$P_1 = P(\tau_2<\tau_1) = P(\sigma_{1-n}<\sigma_1).$$ By the Doob optional sampling theorem, $$1 = E[M_{\sigma_1\wedge \sigma_{1-n}}] = z P(\sigma_1<\sigma_{1-n}) + z^{1-n} (\sigma_{1-n}<\sigma_1) = z(1-P_1) + z^{1-n} P_1,$$ whence $$P_1 = z^{n-1}\frac{z-1}{z^{n}-1}.\tag{1}$$ Similarly, $P_n = P (\tau_n>\tau_{n-1}) = \frac{z-1}{z^{n}-1}$.
Denote by $A_k$, $k=2,\dots,n-1$ the event that the ball finishes at cat $k$. Then $$P(A_k) = P(A_k\mid \tau_{k-1}<\tau_{k+1})P(\tau_{k-1}<\tau_{k+1}) + P(A_k\mid \tau_{k+1}<\tau_{k-1}) P(\tau_{k+1}<\tau_{k-1}).$$ Similarly to $(1)$, $$\quad P(\tau_{k-1}<\tau_{k+1}) = \frac{z^{n-k}-1}{z^{n-1}-1},\quad P(\tau_{k+1}<\tau_{k-1}) = \frac{z^{n-1}-z^{n-k}}{z^{n-1}-1}.$$ But $A_k$ conditionally on $\tau_{k-1}<\tau_{k+1}$ is the same as unconditional $A_1$: starting from some point $O$ ($=k-1$), the ball should visit its right neighbour $O+1$ after it visits $O+2$ ($=k+1$). Similarly, $A_k$ conditionally on $\tau_{k-1}>\tau_{k+1}$ is the same as unconditional $A_n$. Therefore, $$P_k = z^{n-1}\frac{z-1}{z^n-1}\cdot \frac{z^{n-k}-1}{z^{n-1}-1} + \frac{z-1}{z^n-1}\cdot \frac{z^{n-1}-z^{n-k}}{z^{n-1}-1} = z^{n-k}\frac{z-1}{z^n-1},$$ as required.
The symmetric case can be dealt with in a similar fashion by considering the martingale $$M_0 = 0,\quad M_{n+1} = \begin{cases} M_n +1, & (n+1)\text{th step is clockwise},\\ M_n-1, & (n+1)\text{th step is counterclockwise}. \end{cases}$$