6
$\begingroup$

Given some finite state space $\Omega\equiv\{\omega_1,\ldots,\omega_n\}$ be given, and let any Markov chain $\{X_t\}$ with $n\times n$ transition matrix $A$ on $\Omega$ be given. I would like to know if there are standard results out there I can cite that give the following:

  1. There always exists some (not necessarily unique) stationary distribution $\pi$ such that $A\pi = \pi$.
  2. Let any initial distribution $\pi^0\equiv (\pi^0_1,\ldots,\pi^0_n)$ (where $\pi^0_i$ is the initial probability of being in state $\omega_i$) be given, and define $\pi^{t}=\pi^0 A^t$. The "time average limiting distribution" $x$ (is there a more standard term for this out there?) exists: $$x_i \equiv \lim_{t\to\infty}\frac{1}{t} \sum_{s=0}^{t-1} \pi^t_i.$$
  3. The time average limiting distribution $x$ given above is stationary: $x = xA$.

I know this is all implied by the Ergodic Theorem for irreducible Markov chains, but I would like to see that it is also true for all (finite) Markov chains. I don't need convergence to a unique stationary distribution, which is the concern of most of the stuff out there.

$\endgroup$
1
  • $\begingroup$ An alternative argument for 2. can be found in this answer. $\endgroup$
    – heiner
    Feb 18, 2022 at 16:07

1 Answer 1

4
$\begingroup$

All of your statements are true. For the first, you can use a purely linear algebraic fact, that a stochastic matrix always has an eigenvalue of 1 with a left eigenvector whose entries are nonnegative.

For the second, let's say the chain has $m$ communicating classes $C_j$. If the initial condition is entirely in a single communicating class $C_j$ (i.e. $\sum_{i \in C_j} \pi^0_i = 1$), then the time average of the distributions converge to the unique stationary distribution of the Markov chain restricted to $C_j$. This follows from the ergodic theorem. So if you find the time average limit of each subchain, then you can manage the whole chain by writing

$$\mathbb{P} \left ( X_k = i \right ) = \sum_{j=1}^m \mathbb{P} \left ( \left. X_k = i \right | X_0 \in C_{j} \right ) \mathbb{P} \left ( X_0 \in C_{j} \right ) \\ = \mathbb{P} \left ( \left. X_k = i \right | X_0 \in C_{j(i)} \right ) \mathbb{P} \left ( X_0 \in C_{j(i)} \right )$$

where $C_{j(i)}$ is the communicating class of state $i$. Then the second term is constant and the time average of the first term is convergent, so the time average of the whole thing is also convergent.

For the third, you can use linearity:

$$\left ( \frac{\sum_{k=1}^t \pi^k}{t} \right ) A = \frac{\sum_{k=1}^t \pi^k A}{t} = \frac{\left ( \sum_{k=1}^t \pi^k \right ) + \pi^{t+1} - \pi^1}{t}.$$

Taking $t \to \infty$ and exploiting continuity of $A$, we get

$$\left ( \lim_{t \to \infty} \frac{\sum_{k=1}^t \pi^k}{t} \right ) A = \lim_{t \to \infty} \frac{\sum_{k=1}^t \pi^k}{t}.$$

$\endgroup$
11
  • $\begingroup$ Re your last sentence, I am not sure that Cesaro means are relevant (they would be if $\pi^t$ was convergent but this is not always so). $\endgroup$
    – Did
    Aug 15, 2014 at 15:55
  • $\begingroup$ Ah, right. That mistake actually changes problems earlier in the discussion as well. Thank you. $\endgroup$
    – Ian
    Aug 15, 2014 at 15:56
  • $\begingroup$ Sorry but I must also disagree with the new last sentence since the OP is interested in the time average of the distributions $\pi^t$, not in the distributions $\pi^t$ themselves. $\endgroup$
    – Did
    Aug 15, 2014 at 16:10
  • $\begingroup$ @Did The third statement in the OP is that the time average limit is stationary. A deterministic oscillator between two states has a time average limit, namely a uniform distribution on the two states, but it has no stationary distribution. Is that what you are disagreeing with? (Please excuse my many edits). $\endgroup$
    – Ian
    Aug 15, 2014 at 16:13
  • 1
    $\begingroup$ Let $t\to\infty$ in the identity $$A\left(\frac1t\sum_{n=0}^{t-1}\pi^n\right)=\frac1t\sum_{n=0}^{t-1}\pi^{n}+\frac{\pi^{t}-\pi^0}t.$$ $\endgroup$
    – Did
    Aug 15, 2014 at 16:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .