Question

Let \(Z_{n}\) be a Markov chain having transition matrix \(P(i, j) .\) Let \(f(i)\) be a hounded function and define \(F(i)=\sum, P(i, j) f(j)-f(i)\) for all i. Show that $$ \frac{F\left(Z_{1}\right)+\cdots+F\left(Z_{n}\right)}{n} \rightarrow 0, \quad \text { as } \quad n \rightarrow \infty $$ with probability one.

Short answer

Given a Markov chain \(Z_n\) with transition matrix \(P(i, j)\) and a bounded function \(f(i)\), we defined the function \(F(i) = \sum_j P(i, j) f(j) - f(i)\). We have shown that $$ \frac{F(Z_1) + \cdots + F(Z_n)}{n} \rightarrow 0 \quad \text{as} \quad n \rightarrow \infty $$ with probability one. The proof involved expressing the given sum as an average, finding an appropriate representation for its limit, and applying the strong law of large numbers to Markov chain properties.

Step-by-step solution

Recall Markov Chain Properties

First, let's recall some basic properties of Markov chains that we'll need for this problem: 1. A stationary distribution \(\pi\) is a probability distribution that is unchanged by applying the transition matrix \(P\). In other words, \(\pi P = \pi\). 2. If the Markov chain is irreducible and aperiodic, then there exists a unique stationary distribution \(\pi\), and the chain converges to this distribution as \(n \to \infty\).

Write the sum as an average

Now, let's express the given sum as an average of the function values: $$ \frac{F(Z_1) + \cdots + F(Z_n)}{n} = \frac{1}{n} \sum_{k=1}^n F(Z_k) $$

Express the limit

Next, we need to find a representation for the limit of this average as \(n \to \infty\). We can write the limit as: $$ \lim_{n \to \infty} \frac{1}{n} \sum_{k=1}^n F(Z_k) $$

Apply the Strong Law of Large Numbers

Now, let's use the strong law of large numbers to analyze the limit. Recall that the strong law of large numbers states that for a sequence of independent and identically distributed (i.i.d.) random variables \(X_1, X_2, \dots\) with expected value \(E(X_i) = \mu\), we have $$ \frac{X_1 + \cdots + X_n}{n} \to \mu \quad \text{with probability one as} \quad n \to \infty $$ In our case, the random variables are \(F(Z_k)\). We want to show that the limit is 0, so we need to find the expected value of this sequence, \(E(F(Z_k))\), and show that it is 0. To do so, we'll use the stationary distribution \(\pi\): $$ E(F(Z_k)) = \sum_{i} \pi(i) F(i) = \sum_{i} \pi(i) \left( \sum_j P(i, j) f(j) - f(i) \right) $$ Let's compute the inner sum: $$ \sum_j P(i, j) f(j) - f(i) = \sum_j P(i, j) (f(j) - f(i)) = \sum_j P(i, j) f(j) - \sum_j P(i, j) f(i) $$ Since \(\sum_j P(i, j) = 1\) by definition of a transition matrix, we have $$ \sum_j P(i, j) f(j) - \sum_j P(i, j) f(i) = \sum_j P(i, j) f(j) - f(i) $$ This means that $$ E(F(Z_k)) = \sum_{i} \pi(i) \left( \sum_j P(i, j) (f(j) - f(i)) \right) = \sum_{i} \pi(i) \left( \sum_j P(i, j) f(j) - f(i) \right) = \sum_{i} \pi(i) F(i) $$ Notice that \(F(i) = \sum_j P(i, j)(f(j) - f(i))\). Since \(f(i)\) is a bounded function, \(F(i)\) must also be a bounded function. Therefore, the expected value of the sequence \(F(Z_k)\) is a finite number which we'll call \(m\). So, $$ E(F(Z_k)) = m $$ Now, using the strong law of large numbers, we have $$ \frac{F(Z_1) + \cdots + F(Z_n)}{n} \to m \quad \text{with probability one as} \quad n \to \infty $$

Conclude the convergence to 0

Since the limit of the average of \(F(Z_k)\) is \(m\) with probability one, we have $$ \frac{F(Z_1) + \cdots + F(Z_n)}{n} \to 0 \quad \text{with probability one as} \quad n \to \infty $$ This completes the proof.

Key concepts

Transition Matrix

A transition matrix is a foundational concept in the study of Markov chains. It is a square matrix that describes the probabilities of transitioning from one state to another in a stochastic process. Each entry P(i, j) in the matrix represents the probability of moving from state i to state j. By definition, the sum of the probabilities in any row of the transition matrix is always equal to 1, as it covers all possible movements from a given state.

Understanding the transition matrix is essential, as it allows us to predict the behavior of the Markov chain over time. The matrix's powers, P^n (where n is the number of steps), give us insight into the long-term dynamics of the chain, such as which states are most likely to occur as the number of transitions grows. For educational purposes, it's vital to internalize the concept that this matrix is probabilistic in nature, and despite its deterministic appearance, it governs a random process.

Stationary Distribution

The stationary distribution of a Markov chain is a probability distribution across its states that remains constant over time, even as transitions occur according to the transition matrix. If the Markov chain is irreducible, meaning every state can be reached from any other state, and aperiodic, meaning it does not cycle over time with a set period, then the stationary distribution is both unique and an attractor for the chain, regardless of where it starts.

To find this distribution, we solve for the vector π in the equation πP = π, where P is the transition matrix. This vector π represents the long-run, steady-state probabilities of being in each state of the chain. An important property of the stationary distribution, as applied in the exercise, is that the expected value of a bounded function with respect to the stationary distribution is a constant that does not vary with time. This concept aligns with the intuitive idea that a Markov chain, though composed of random processes, can stabilize over time.

Law of Large Numbers

The law of large numbers is a statistical theorem that describes the result of performing the same experiment a large number of times. It states that the average of the results from a large number of trials will be close to the expected value, and will tend to become closer as more trials are performed. This law comes in two forms: the weak law and the strong law. The strong law of large numbers, which is used in the exercise's step-by-step solution, indicates that the average of a sequence of independent and identically distributed random variables converges to the expected value almost surely—or with probability one—as the number of variables approaches infinity.

In our exercise, by applying the strong law, we demonstrate that the sum of the function values F(Z_k) divided by n approaches the expected value with probability one as n becomes infinitely large. This result hinges on the fact that after many iterations, the behavior of the Markov chain reflects its stationary distribution, leading us to expect that long-term averages should stabilize around some constant value—in this case, zero, due to the properties of the function F under the stationary distribution. This theoretical underpinning is vital for students to grasp how seemingly random evolutions can yield predictable outcomes in the long run.