2
$\begingroup$

Consider a square matrix $P$. We call it stochastic if it holds that $ p_{ij}\geq0\text{ and } \sum\limits_{j=1}^m\,\,\,\,p_{ij} = 1 $ for all $1\leq i,j\leq m$. I wonder when the following limit exists: $Q = \lim\limits_{n\to\infty}P^n$.

I prefer to use the following norm: $ \|P\| = \sup\limits_{\|f\| = 1}\frac{\|Pf\|}{\|f\|}. $

For example, I know that $\|P\| = 1$.

This question strongly relates to the theory of Markov Chains, since each $P$ defines uniquely a Markov Chain on the space with $m$ states. Each $P^n$ is also a stochastic matrix, and the correspondent Markov Chain is a skeleton of the one defined by $P$.

  • 0
    http://en.wikipedia.org/wiki/Markov_chain2011-08-18

3 Answers 3

6

If $P$ is stochastic, then $\lim_n P^n$ exists if and only if either of the following is true:

  1. (Analytically) If $\lambda$ is an eigenvalue of $P$ with $|\lambda|=1$, then $\lambda=1$.

  2. (Probabilistically) Every recurrent state is aperiodic.

4

Re-written, thanks to comment by Gerry Myerson. The limit will exist, applying the Frobenius Perron Theorem, if some power of $P$ has all its entries positive, or, more generally, the rows and columns of $P$ may be permuted so that $P$ is direct sum of square block matrices, each with this property. The limiting matrix will satisfy $PQ = Q$, naturally, but its rank will, in general, be the number of blocks in such a rearrangement.

  • 0
    Whoops, never mind!2011-08-28
1

The following is an attempt at a combinatorial characterization.

Lets call a directed graph $G=(V,E)$ multipartite if its vertex set $V$ can be partitioned into subsets $V_0, \ldots, V_{k-1}$ such that all the edges originating in $V_i$ lead to $V_{i+1 {\rm mod }~k}$. Consider the directed graph $G$ associated with the Markov chain $P$: we put the edge $(i,j)$ in $G$ whenever $p_{ij}>0$.

Claim 1: If $G$ is strongly connected, then $\lim_n P^n$ exists if and only if $G$ is not multipartite.

Proof: In one direction, its quite easy to verify that if $G$ is multipartite, $P^n$ does not have a limit.

Conversely, suppose that $G$ is not multipartite. Since $G$ is strongly connected (i.e., $P$ is irreducible), a result of Frobenius (the "Frobenius form" on page 680 here) implies that $P^m$ is a positive matrix for some power $m$, which, as Geoff Robinson explained, yield the desired conclusion.

Next, what about the more general case when $G$ is not necessarily strongly connected? Consider the graph obtained by collapsing every strongly connected component of $G$ into a vertex. Some of these "super-vertices" must have no incoming edges; let $g_1, g_2, \ldots, g_k$ be an enumeration of them. Then the graphs which collapsed to them - $G_1, \ldots, G_k$ - must be strongly connected subgraphs of $G$.

Claim 2: $\lim_n P^n$ does not exist if and only if at least one of $G_1, \ldots, G_k$ is multi-partite.

Proof: Again, if some $G_i$ is multipartite, its easy to see $P^n$ has no limit.

Conversely, suppose no $G_i$ is multipartite. We will next argue that $P^n$ has a limit.

Let $S$ be the set of vertices belonging to some $G_i$, and $S^c$ be the other vertices.

Let $x$ be a nonnegative vector that sums to $1$. We have that if $i \in S^c$, then $\lim_n (x P^n)_i = 0.$ This follows by a probabilistic argument - every certain number of steps there is a positive probability of escaping to $S$ and staying there forever so the probability of staying in $S^c$ must approach zero.

Now suppose $i \in S$; actually, for concreteness, lets suppose $i \in G_1$. Let $A_{n/2}$ be the event that starting from initial distribution $x$, the Markov chain reaches $G_1$ (and consequently stays there forever) by time $n/2$. Then $\lim_n (x P^n)_i = P(A_{n/2}) P( \mbox{being at } i \mbox{ at time } n | A_{n/2}) + P_3(n) $ where $P_3(n)$ is something that goes to zero as $n \rightarrow \infty$ by the previous paragraph. Its not hard to see that each of the first two terms in the previous equation approaches a limit as $n \rightarrow \infty$ - the first approaches the probability of eventual absorption into $G_1$; and the second approaches a limit because $P$ restricted to $G_1$ is strongly connected, and this is where we use Claim 1.

Finally, if $x P^n $ has a limit for every $x$ which is nonnegative and has components which sum to $1$, then by taking $x=e_j$ for every $j$ we see that $P^n$ has a limit. That concludes the proof.

Things are a bit simpler in the case when $G$ is an undirected graph (i.e., if $p_{ij}>0$ implies p_{ji}>0) since an undirected graph splits up into connected components and is multipartite if and only if it is bipartite. Thus:

Claim 3: If $G$ is undirected, $\lim_n P^n$ does not exist if and only if one of the connected components of $G$ is bipartite.

  • 0
    @Byron Schmuland - thanks for pointing out the error. I think the new version should be correct (fingers crossed).2011-08-28