Past exam of the probability course of the University of Oxford / 2021 / 3 / c

Take an integer $c\ge \max \{a,b\}$. On $I=\{-c,\dots ,c\}$, the modified transition matrix $Q=(q_{i,j})$ agrees with $P$. Above $c$, it stays put with probability $a/(a+b)$ and jumps to each of $c-b+1,\dots ,c$ with probability $1/(a+b)$. Below $-c$, it stays put with probability $b/(a+b)$ and jumps to each of $-c,\dots ,-c+a-1$ with probability $1/(a+b)$. All unspecified entries are zero. These rows sum to one. The integer qualification is necessary: if $c$ were nonintegral, $i=\lfloor c\rfloor +1$ would fit none of the printed row conditions.

DefineAn interior jump cannot go below $-c-b$ or above $c+a$, and every exterior reset lands in $I$. Thus $C$ is closed.

To prove that it is one communicating class, start anywhere in $C$. From $L$ or $U$, a reset can reach $I$ with positive probability. From any state of $I$, repeated $+a$ steps reach some state of $U$, after staying in $I$ up to the last step. A reset from this state can reach every point of the consecutive blockEvery integer $j\in \{-c-b,\dots ,c\}$ has the form $t-kb$ for some $t\in B$ and an integer $k\ge 0$. Repeated $-b$ steps from $t$ reach $j$, with all departure states in $I$ until a possible last step into $L$. This gives access to all of $I\cup L$. Finally, each $j\in U$ can be reached from $j-a\in I$. Every path described has strictly positive probability. Therefore every state in $C$ reaches every other state in $C$.

Each state outside $C$ can only stay put or reset into $I$, and no transition from $C$ returns to it. Different states outside $C$ cannot reach one another. Hence the complete list of communicating classes isThe finite class $C$ is the unique closed communicating class. The exterior singleton classes are transient communicating classes, since their self-transition probabilities are strictly less than one. Notice that this reachability proof does not require $a,b$ to be coprime.

The restriction $Q_C$ is a finite Markov chain that is an irreducible Markov chain. It is aperiodic, because its upper states have self-transition probability $a/(a+b)>0$, and the period is constant on a communicating class. We now find its stationary distribution.

Every column of $Q_C$ sums to one. Here is the full incoming-mass check, with each total measured in units of $1/(a+b)$. For $j\in L$, the incoming contributions are $a$ from $j+b\in I$ and $b$ from the self-transition. For $j\in U$, they are $b$ from $j-a\in I$ and $a$ from the self-transition.

For $j\in I$, the upward predecessor $j-a$ lies in $I$ exactly when $j\ge -c+a$, contributing $b$ units. When $j\le -c+a-1$, that predecessor is replaced by resets from all $b$ states of $L$, again contributing $b$ units. Independently, the downward predecessor $j+b$ contributes $a$ units when $j\le c-b$; when $j\ge c-b+1$, resets from the $a$ states of $U$ contribute those $a$ units instead. Thus every column total is $a+b$ units.

Therefore $Q_C$ is a doubly stochastic matrix, and the uniform distribution on $C$ is stationary:The countable-state Markov chain convergence theorem, applied to the finite closed class $C$, gives $Q_C^n(i,j)\to {\pi }_j$ for every $i\in C$. Its hypotheses hold: $C$ is finite and irreducible, hence positive recurrent, and it is aperiodic.

If $i_0>c+a$, the hitting time $H$ of $C$ has $\mathbb{P}(H>n)=(a/(a+b){)}^n$. If $i_0<-c-b$, the corresponding tail is $(b/(a+b){)}^n$. Thus $H<\infty$ almost surely from every exterior initial state. Conditioning on $H$ and $R_H$, use convergence within $C$ after entrance and the bounded convergence theorem; equivalently, first restrict to $H\le K$ and then let $K\to \infty$. This proves, for every $i_0\in \mathbb{Z}$,The limiting distribution is independent of $i_0$.