Question

Suppose \(P=\left\|P_{1 j}\right\|\) is the transition probability matrix of an irreducible recurrent Markov chain \(\left\\{X_{n}\right\\} .\) Use the supermartingale convergence theorem (see Remark 5.1) to show that every nonnegative solution \(y=\\{y(i)\\}\) to the system of inequalities \(y(i) \geq \sum_{j=0}^{\infty} P_{i j} y(j), \quad\) for all \(i\) is constant.

Short answer

We started by defining a sequence of random variables Y_n as the solution y evaluated at each state of the Markov chain. We then showed that Y is a supermartingale, as \(E\left[Y_{n+1} |Y_n\right] \leq Y_n\). By applying the supermartingale convergence theorem, we deduced that Y has a limit Y_∞ almost surely. Since Y cannot decrease indefinitely and y is non-negative, there must be a constant c such that \(Y_\infty = c\) almost surely. This implies that the function y is constant, proving that every nonnegative solution y to the given system of inequalities must be constant.

Step-by-step solution

Formulate the supermartingale

Let Y = \(\\{Y_n\\}\) be a sequence of random variables defined as, Y_n = \(y(X_n)\), where y is the solution to the system of inequalities and \(X_n\) is the Markov chain. Notice that, for any i, \(E\left[Y_{n+1} | X_n = i\right] = \sum_j P_{ij} y(j) \leq y(i)= Y_n\) Since the Markov chain is independent of y, so we can write this inequality as: \(E\left[Y_{n+1} |Y_n\right] \leq Y_n\) This shows that Y is a supermartingale.

Apply the supermartingale convergence theorem

Using the supermartingale convergence theorem, we know that Y has a limit Y_∞ almost surely as n approaches infinity because the Markov chain is irreducible and recurrent. That is, \(P\left(\lim_{n \to \infty} Y_n = Y_{\infty}\right) = 1\). Since Y has a limit, it is impossible for the values of Y to oscillate, they must either keep increasing or keep decreasing. However, since we have the inequality \(E\left[Y_{n+1} | Y_n\right] \leq Y_n\), by the supermartingale property, it is clear that the values of Y can only keep decreasing. But since y is non-negative, Y cannot decrease indefinitely, so there must be a constant c such that the limit \(Y_\infty = c\) almost surely.

Conclude that y is constant

Since we know that the limit exists and that \(Y_\infty = c\) almost surely, it follows that the function y must be constant. Otherwise, there would be two different states i and j for which y(i) ≠ y(j), leading to oscillations, which would contradict our conclusion in step 2. Thus, we have shown that every nonnegative solution y to the given system of inequalities must be constant.