Past exam of the options II course of the University of Oxford / 2005 / N

Starting from a state $i$, let ${\tau }_i=\inf \{n\ge 1:X_n=i\}$ be the first return time, with value infinity if no return occurs. The state is recurrent if ${\mathrm{Pr}}_i({\tau }_i<\infty )=1$ and transient if this probability is less than 1. A recurrent state is positive recurrent if ${\mathbb{E}}_i{\tau }_i<\infty$, and null recurrent if that expectation is infinite.

If $i$ and $j$ communicate, choose $r,s$ with $p_{ij}^{(r)}>0$ and $p_{ji}^{(s)}>0$. The Chapman-Kolmogorov equations give, for every $n$,If $j$ is recurrent, the supplied criterion makes ${\sum }_n{p}_{jj}^{(n)}$ infinite. Summing this inequality shows that ${\sum }_n{p}_{ii}^{(n)}$ is also infinite, so $i$ is recurrent. The same argument with the states exchanged gives the converse. Hence recurrence and transience are class properties: states in one communicating class cannot have different answers to that dichotomy.

Assume $N\ge 2$, as required by the source's selection probabilities, and put $q=(1-p)/(N-1)$. Conditional on the red book's current position, the next independent selection determines its move without needing its earlier history. Selecting the red book moves it left, unless already leftmost. Selecting the plain book immediately to its right moves it right. Every other selection leaves its position unchanged. Thus this position process is a Markov chain on $\{1,\dots ,N\}$, withand boundary self-loop probabilities $P_{11}=1-q$, $P_{NN}=1-p$. These account for every selection and each row sums to one.

Stationarity at the first state gives ${\pi }_1=(1-q){\pi }_1+p{\pi }_2$, hence $p{\pi }_2=q{\pi }_1$. When $N\ge 3$, for the second state substitution of this identity into its stationarity equation gives $p{\pi }_3=q{\pi }_2$. More generally, summing stationarity over the initial segment $\{1,\dots ,i\}$ equates its sole outward and inward probability flows:Write $r=q/p$. Then ${\pi }_i={\pi }_1{r}^{i-1}$. Normalization givesThe expression is positive also for $r>1$, since both numerator prefactor and denominator are negative. The uniform case is exactly $p=1/N$, when all books are equally likely to be selected. Since both neighboring transition probabilities are positive, the finite chain is irreducible; the displayed stationary distribution is therefore unique.