1
$\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
    I think if the markov chain is regular, then $Q$ exists. Namely, if some power of $P$ has all positive entries.2011-08-18
  • 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
    Somehow I was accustomed to "Perron-Frobenius", but I think I'll like the alphabetical arrangement...2011-08-18
  • 2
    Doesn't $P=\pmatrix{0&1\cr1&0}$ satisfy the hypotheses in the question? And doesn't the limit fail to exist?2011-08-18
  • 0
    @Gerry: You are right, of course. Thanks for pointing that out. My memory of the statement of the irreducible case was inaccurate.2011-08-18
  • 0
    @Gerry I think that Geoff meant that *both* the rows and columns must be permuted with the same permutation. This amounts to relabelling the states of the Markov chain, and in this case Geoff's answer is correct. In fact, his condition characterizes those stochastic matrices $P$ where the limit $\lim_n P^n$ exists.2011-08-28
  • 0
    @Byron: Yes, thanks Byron. The answer as now written is correct (if you interpret the permutation as you did). Gerry's coment referred to an earlier version of the answer, which I re-edited as indicated.2011-08-28
  • 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