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

Question

$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$?

Answer 1

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