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

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