Past exam of the mathematics course of the University of Cambridge / 2017 / ib / Paper 2 / 20H (Markov Chains)

Let $S_k={\sum }_{\ell =1}^k{Y}_{\ell }$, $S_0=0$, be the epochs of the renewal process. The definition uses the next epoch at or after $n$, so $X_n=0$ at an epoch. If $X_n=i\ge 1$, no renewal occurs before $n+i$ and necessarily $X_{n+1}=i-1$.

If $X_n=0$, time $n$ is a renewal epoch, and the next unused interarrival time is independent of the entire observed past with the original distribution. To justify the random index, condition on each possible number $k$ of renewals up to $n$: the event identifying $k$ depends only on $Y_1,\dots ,Y_k$, whereas $Y_{k+1}$ is independent of those variables. Summing over $k$ preserves that distribution and independence. Therefore the residual lifetime Markov chain has transition probabilitiesIts reachable state space is $E=\{j\ge 0:\mathbb{P}(Y_1>j)>0\}$, either an initial finite segment or all nonnegative integers. The conditional next-step law depends only on $X_n$, proving the Markov property. Initially $X_0=0$. The reset is $Y-1$, rather than $Y$, because one unit of time has elapsed by the next step.

Starting at zero, the next renewal is at time $Y_1$, and there are no intervening renewals because $Y_1\ge 1$. Thus the first return time obeys $T_0=Y_1$ in distribution, indeed under the original renewal construction. Its mean recurrence time isThe chain returns to zero almost surely and has a finite expected return time, so zero is a positive recurrent state. The assumption $\mu <\infty$ is what upgrades recurrence to positive recurrence.

Every reachable state $i$ reaches zero deterministically in $i$ steps. For $j\in E$, choose a supported lifetime $k>j$; zero can jump to $k-1$ and then count down to $j$. Thus the chain is an irreducible Markov chain on $E$. Its positive-probability first return lengths are exactly the support of $Y_1$; all other return lengths are sums of such lengths. Their greatest common divisor is therefore one by assumption, so the chain is an aperiodic Markov chain.

The equilibrium residual-life distribution isIt is a probability distribution because the tail-sum identity gives ${\sum }_{j\ge 0}\mathbb{P}(Y_1>j)=\mathbb{E}{Y}_1=\mu$. With zero masses outside $E$,so it is a stationary distribution. This also displays why finite mean is needed for normalization.

Use the countable-state Markov chain convergence theorem: an irreducible, aperiodic, positive recurrent discrete-time chain on a countable state space has a unique stationary distribution and $P^n(i,j)\to {\pi }_j$ for every pair of states. All hypotheses were verified, including positive recurrence in part (b). Since $X_0=0$ and $\mathbb{P}(Y_1>0)=1$,The finite-state convergence theorem alone would not suffice when the lifetimes are unbounded. The gcd hypothesis is also necessary for this ordinary limit: deterministic lifetime 2, for example, produces alternating renewal probabilities rather than convergence.