How does one show that any finite-state time homogenous Markov Chain has at least one stationary distribution in the sense of $\pi = \pi Q$ where $Q$ is the transition matrix and $\pi$ is the stationary distribution? My instinct is it involved eigenvalues and the Perron Frobenius theorem but I'm having trouble completing the argument.
[Math] Finite State Markov Chain Stationary Distribution
markov chainsprobability theory
Related Solutions
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}.$$
That is a really convoluted way of describing a steady state in my opinion.
The set of potential states a system can be in is called $S$. For example, $S$ could be "how many animals are there in your socks".
They seem to be describing a system that proceeds in discrete steps (discrete time markov). So a step could be going from one day to the next.
$\pi_k(x)$ is the probability of being in state $x$ on step $k$. So there might be a 10% probability that you have 4 kittens in your socks on Tuesday: $\pi_{\text{Tuesday}}(4) = .1$.
$P(x,y)$ is the probability that you proceed from state $x$ to state $y$. So if you have 3 kittens in your socks on one day, there is a 14% chance that you'll have 5 the next day. $P(3,5) = .14$.
Every step has a probability associated with being in a certain state. If your socks can hold at most $5$ kittens, then $\pi(0) + \pi(1) + \pi(2) + \pi(3) + \pi(4) + \pi(5) = 1$. That's just basic probability, the sum of all possibilities is 100%.
Knowing the transition probabilities $P$, and the probability of states of a certain step $\pi_k()$, then you can calculate the probability of states in the next step, $\pi_{k+1}()$. Specifically, $\pi_{k+1}(y) = \sum_{x \in S} \pi_{k}(x)P(x,y)$. "The probability of having 2 kittens in your sockets is the probability of having 0 kittens times the probability of transitioning from 0 to 2 plus the probability of having 1 times the probability of transitioning from 1 to 2 plus ...".
When $\forall x ~~\pi_{k+1}(x) = \pi_k(x)$, then that $\pi$ is called a steady state. In that state, the transitions don't change the probabilty of each state from step to step.
Example:
You can have at most 2 kittens in your socks.
- If you have zero kittens in your sockets, then the probability that you have 0 the next day is 10%, 1 is 10%, 2 is 80%
- If you have one kitten in your sockets, then the probability that you have 0 the next day is 10%, 1 is 20%, 2 is 70%
- If you have two kittens in your sockets, then the probability that you have 0 the next day is 30%, 1 is 30%, 2 is 40%
Then a steady state is :
$$\pi(0) = \frac{27}{128},\quad \pi(1) = \frac{15}{64},\quad \pi(2) = \frac{71}{128}$$
As you can check, using the given formula.
Best Answer
There are a number of ways to prove this. In a recent article "What is a stationary measure?", Alex Furman outlines a straightforward proof using only linear algebra. He notes that the existence of an invariant probability measure also follows from the Brouwer fixed point theorem.