Question

Consider an irreducible Markov chain with a finite set of states \(\\{1,2, \ldots, N\\}\). Let \(\left\|P_{i j}\right\|\) be the transition probability matrix of the Markov chain and denote by \(\left\\{\pi_{j}\right\\}\) the stationary distribution of the process. Let \(\left\|P_{i j}^{(m)}\right\|\) denote the \(m\)-step transition probability matrix. Let \(\varphi(x)\) be a concave function on \(x \geq 0\) and define $$ E_{m}=\sum_{j=1}^{N} \pi_{j} \varphi\left(P_{j t}^{(m)}\right) \quad \text { with } l \text { fixed. } $$ Prove that \(E_{m}\) is a nondecreasing function of \(m\), i.e., \(E_{m+1} \geq E_{m}\) for all \(m \geq 1\)

Short answer

In short, we proved that \(E_{m}\) is a nondecreasing function of \(m\) for an irreducible Markov chain with a finite set of states and its transition probability matrix. By using the properties of the Markov chain, the stationary distribution property, and the concave function, we derived the inequality: \[E_{m+1} - E_{m} = \sum_{j=1}^{N} \pi_{j} \left[\varphi\left(\sum_{i} P_{ij} P_{it}^{(m)}\right) - \varphi\left(P_{jt}^{(m)}\right)\right] \geq 0\] Therefore, we showed that \(E_{m+1} \geq E_{m}\) for all \(m \geq 1\), and \(E_{m}\) is a nondecreasing function of \(m\).

Step-by-step solution

Introduction to the proof

In order to prove that \(E_{m}\) is a nondecreasing function of \(m\), we need to show that \(E_{m+1} \geq E_{m}\) for all \(m \geq 1\). Let's first write down the expression for \(E_{m+1}\) and \(E_{m}\): \[E_{m+1} = \sum_{j=1}^{N} \pi_{j} \varphi\left(P_{jt}^{(m+1)}\right)\] \[E_{m} = \sum_{j=1}^{N} \pi_{j} \varphi\left(P_{jt}^{(m)}\right)\] Now let's find the difference between \(E_{m+1} - E_{m}\) and try to show that this difference is non-negative.

Applying the concave function

Since \(\varphi(x)\) is a concave function, we know that for any \(0 \leq x,y,z \leq 1\) and any probability \(p\): \[\varphi(x + y) \geq p \varphi(x) + (1-p) \varphi(z)\] Now, let \(x = P_{jt}^{(m+1)} - P_{jt}^{(m)}\), \(y = P_{jt}^{(m)}\), and \(z = \sum_{i} P_{ij} P_{it}^{(m)}\). We can use this inequality in the following way: \[\varphi\left(P_{jt}^{(m+1)}\right) - \varphi\left(P_{jt}^{(m)}\right) \geq p \left[\varphi\left(P_{jt}^{(m+1)} - P_{jt}^{(m)}\right)\right] + (1-p) \left[\varphi\left(\sum_{i} P_{ij} P_{it}^{(m)}\right)\right]\]

Using the stationary distribution property

We know that the stationary distribution of the Markov chain, \(\left\{\pi_{j}\right\}\), is such that: \[\pi_{j} = \sum_{i=1}^{N} \pi_{i} P_{ij}\] Thus, we can rewrite our inequality as: \[\varphi\left(P_{jt}^{(m+1)}\right) - \varphi\left(P_{jt}^{(m)}\right) \geq p \left[\varphi\left(P_{jt}^{(m+1)} - P_{jt}^{(m)}\right)\right] + (1-p) \left[\varphi\left(\sum_{i} \pi_{i} P_{ij} P_{it}^{(m)}\right)\right]\]

Rearranging the terms

Now let's rewrite the inequality as follows: \[\pi_{j} \left[\varphi\left(P_{jt}^{(m+1)}\right) - \varphi\left(P_{jt}^{(m)}\right)\right] \geq \pi_{j} \left[p \left[\varphi\left(P_{jt}^{(m+1)} - P_{jt}^{(m)}\right)\right] + (1-p) \left[\varphi\left(\sum_{i} \pi_{i} P_{ij} P_{it}^{(m)}\right)\right]\right]\] Summing this inequality over all \(j = 1,2,\cdots,N\), we get: \[\sum_{j=1}^{N} \pi_{j} \left[\varphi\left(P_{jt}^{(m+1)}\right) - \varphi\left(P_{jt}^{(m)}\right)\right] \geq 0\]

Using the transition probability properties

But, we also know that for an irreducible Markov chain, the \(m\)-step transition probability matrix properties imply: \[P_{jt}^{(m+1)} = \sum_{i=1}^{N} P_{ij} P_{it}^{(m)}\] Therefore, we can write our inequality as: \[\sum_{j=1}^{N} \pi_{j} \left[\varphi\left(\sum_{i} P_{ij} P_{it}^{(m)}\right) - \varphi\left(P_{jt}^{(m)}\right)\right] \geq 0\]

Completing the proof

Now, let's go back to the definition of \(E_m\) and see what we get: \[E_{m+1} - E_{m} = \sum_{j=1}^{N} \pi_{j} \varphi\left(P_{jt}^{(m+1)}\right) - \sum_{j=1}^{N} \pi_{j} \varphi\left(P_{jt}^{(m)}\right) = \sum_{j=1}^{N} \pi_{j} \left[\varphi\left(\sum_{i} P_{ij} P_{it}^{(m)}\right) - \varphi\left(P_{jt}^{(m)}\right)\right] \geq 0\] Thus, we have shown that \(E_{m+1} \geq E_{m}\) for all \(m \geq 1\). This completes the proof that \(E_{m}\) is a nondecreasing function of \(m\).