Let $p$ be a transition function of a Markov Chain on a countable state $S$ and $i \in S$. Assume for every $j \in S$,
$$ \lim_{n\to \infty} p^n(i,j) = \pi(j)$$
Show that $\pi$ is a stationary distribution.
I was trying to show $\pi$ is a stationary distribution by showing that for each $j$, $\sum_{i} p(i,j)\pi(i) = \pi(j)$. But I haven't found a good way to prove this. Does anyone have an idea or reference on how to show this result?
On
First of all , itteration of binary functions is questionable. $f^n(x)$ means $f(f(f(\dots(x))))$, but what does $f^n(x,y)$ mean?
In this case, it is trying to imply successive transitions. So $(p \circ q)(i,j)$ would be transitioning $q$, then $p$, so the only reasonable way to interpret it is:
$$(p \circ q)(i,j) = \sum_{u} q(i, u)p(u, j)$$
So:
$$\lim_{n\to \infty} p^n(i,j) = \pi(j)$$
Implies $$\lim_{n\to \infty} p^{n+1}(i,j) = \pi(j)$$
$$\lim_{n\to \infty} (p^n \circ p)(i,j) = \pi(j)$$
$$\lim_{n\to \infty} \sum_{u} p(i,u) p^n(u,j) = \pi(j)$$
Questionable step (because it assumes convergence to exchange the sum and limit):
$$ \sum_{u} p(i,u) \bigg(\lim_{n\to \infty} p^n(u,j)\bigg) = \pi(j)$$
$$ \sum_{u} p(i,u) \pi(j) = \pi(j)$$
This is the same style of proof where you would say $a_{n+1} = f(a_{n})$, what is $L = \lim_{n \to \infty} a_n$ and solve it by setting $L = a_{n+1} = a_{n}$ and solving $L = f(L)$.
$\newcommand{\Raw}{\Rightarrow}\newcommand{\raw}{\rightarrow}\newcommand{\N}{\mathbb{N}}$
Short answer: A nice, non-standard proof of this well-known theorem is to be found in F. Ceccherini-Silberstein, T. Scarabotti and F. Tolli. Harmonic Analysis on Finite Groups. Cambridge University Press, New York, 2008.
One possible debarring of the existence of a limit is periodicity. Consider a Markov chain $\xi$ on a set $X=X_0\cup X_1$ with $X_0\cap X_1=\emptyset$ and neither of the $X_i=\emptyset$ for $i=1,2$. Suppose $\xi$ has the property that $\xi_{2k+i}\in X_i$, for $k\in\N_0$, $i=0,1$. Then `$\xi_\infty$' cannot exist in the obvious way. In a certain sense $\xi$ must be aperiodic for limiting behaviour to exist. This is of course the case for bipartite graphs.
Suppose $\xi$ is a Markov chain and the limit $\nu P^n\raw \theta$ exists. Loosely speaking, after a long time $N$, $\xi_N$ has distribution $\mu(\xi_N)\sim \theta$: $$\begin{align} \nu P^N\sim \theta \\\Raw \nu P^{N}P\sim\theta P \\\Raw \nu P^{N+1}\sim \theta P \end{align}$$ But $\nu P^{N+1}\sim \theta$ also and hence $\theta P\sim \theta$. So if '$\xi_\infty$' exists then its distribution $\theta$ may have the property $\theta P=\theta$. Such a distribution is said to be a stationary distribution for $P$.
Relaxing the supposition on `$\xi_\infty$' existing, do stationary distributions exist? Clearly they are left eigenvectors of eigenvalue 1 that have positive entries summing to 1.
If $k(x)\in F(X)$ is any constant function then $Pk=k$ so $k$ is a right eigenfunction of eigenvalue 1. Let $u$ be a left eigenvector of eigenvalue 1. By the triangle inequality, $|u(x)|=|\sum_yu(y)p(y,x)|\leq\sum_y|u(y)|p(y,x)$. Now $$\sum_{z\in X}|u(z)|\leq \sum_{z\in X}\left(\sum_{y\in X}|u(y)|p(y,z)\right)=\sum_{y\in X}|u(y)|\underbrace{\left(\sum_{z\in X}p(y,z)\right)}_{=1}=\sum_{y\in X}|u(y)|$$ Hence the inequality is an equality so $\sum_z\left(\sum_y|u(y)|p(y,z)-|u(z)|\right)=0$ is a sum of non-negative terms. Hence $|u|P=|u|$, and by a scaling, $\pi(x):=|u(x)|/\sum_y |u(y)|$, is a stationary distribution.
Therefore a left eigenvector of eigenvalue 1 exists and if it is positive and of weight 1 it is a stationary distribution.
How many stationary distributions exist? Consider Markov Chains $\xi$ and $\zeta$ on disjoint finite sets $X$ and $Y$, with stochastic operators $P$ and $Q$. The block matrix $$ R=\left(\begin{array}{cc}P & 0\\0 & Q\end{array}\right)$$ is a stochastic operator on $X\cup Y$. If $\pi$ and $\theta$ are stationary distributions for $P$ and $Q$ then $$\phi_c=(c\pi,(1-c)\theta)\,,\,\,\,\,c\in[0,1]$$ is an infinite family of stationary distributions for $R$. The dynamics of this walk are that if the particle is in $X$ it stays in $X$, and vice versa for $Y$ (the graph of $R$ has two disconnected components). This example shows that, in general, the stationary distribution need not be unique. Rosenthal shows that a sufficient condition for uniqueness is that the Markov chain $\xi$ has the property that every point is accessible from any other point; i.e. for all $\,x,y\in X$, there exists $r(x,y)\in\N$ such that $p^{(r(x,y))}(x,y)>0$. A Markov chain satisfying this property is said to be irreducible.
So for the existence of a unique, stationary distribution it may be sufficient that the Markov chain is both aperiodic and irreducible. Call a stochastic operator $P$ ergodic if there exists $n_0\in \N$ such that $$p^{(n_0)}(x,y)>0\,,\,\,\forall x,y\in X$$ In fact, ergodicity is equivalent to aperiodic and irreducible, and the following theorem asserts that it is both a necessary and sufficient condition for the existence of a strict distribution for '$\xi_\infty$'. These precluding remarks suggest the distribution of `$\xi_\infty$' is in fact stationary and unique, and indeed this will be seen to be the case. A nice, non-standard proof of this well-known theorem is to be found in F. Ceccherini-Silberstein, T. Scarabotti and F. Tolli. Harmonic Analysis on Finite Groups. Cambridge University Press, New York, 2008.
Markov Ergodic Theorem