4
$\begingroup$

This question will be a little out-of-character for me. I'm reading an evolutionary game theory book (which isn't for mathematicians), and I'm not sure of the mathematics involved.

My definition of a stochastic matrix will be a square matrix with real $\geq 0$ coordinates, such that the sum of each row is $1$.

I will call a stochastic matrix positive, if all of its coordinates are positive.

The book I'm looking at is describing finite birth-death processes. The idea is that there is a finite population $A$ and a finite population $B$ and at each step one of either $A$ or $B$ randomly dies, and one randomly multiplies. We think of this as a stochastic process with $N+1$ states, one for each of the possible number of people in $A$. ($N$ being the number of people in $A$ plus the number of people in $B$)

Let $P$ be the corresponding stochastic matrix.

The book declares the following: let $x_i$ be the probability of reaching state $N$ when starting from $i$ EVENTUALLY (in the limit of the process continuing ad infinitum). Let $\underline{x}$ denote the $x_i$'s as a vector. Then $\underline{x}=P\underline{x}$, and (and I quote) "the absorption probabilities are given by the right-hand eigenvector associated with the largest eigenvalue, which is one, because $P$ is a stochastic matrix."

My real question is: what is the right statement of the theorem this uses?

Notice that this $\underline{x}$ is just the last column of $P^{\infty}$ (the limit of $P^n$). Is the correct statement that all of the columns of $P^{\infty}$ eigenvectors for the eigenvalue $1$? Is the correct statement that all of the columns of $P^{\infty}$ are eigenvectors of some eigenvalue (which might change from column to column) with absolute value $1$ (possibly complex)?

I'm also having a hard time comparing it to the Perron-Frobenius theorem. Birth-death is not a positive stochastic process (one having a positive stochastic matrix), but whatever theorem I'm seeking should work also for those. Let $Q$ be a positive stochastic matrix. Then according to Perron-Frobenius (my understanding of which is mostly from http://people.brandeis.edu/~igusa/Math56F06/Math56a_lectures.pdf page 4, but also a little from wiki): the eigenspace of $1$ is exactly $1$-dimensional, and $1$ is the only eigenvalue with absolute value $1$. Further, there is a (unique, obviously) vector $\underline{\pi}$ such that it is in this eigenspace, and such that it has positive coordinates, and their sum is $1$. Further yet, $P^{\infty}$ has as all of its rows $\underline{\pi}$!! Further even yet, $P^t\pi=\pi$.

So... I'm confused. What is the theorem I'm seeking, and how does it make sense with Perron-Frobenius?

1 Answers 1

6

Take any finite state space Markov chain with transition matrix $P$.

When the limit $P^\infty$ exists, its columns $v$ all satisfy $Pv=v$. Indeed, its columns span the eigenspace corresponding to the eigenvalue 1.

There is a probabilistic formula for the $j$th column function, it is $i\mapsto {\mathbb{P}_i(T_j<\infty)\over \mathbb{E}_j(T_j)}$ where $T_j$ is the hitting time of the state $j$, i.e., $T_j=\inf(n\geq 1: X_n=j)$. This formula can be proved using the strong Markov property.

When $j$ is transient, then $\mathbb{E}_j(T_j)=\infty$ (since the chain may fail to return to $j$) and the ratio above is zero. Then the $j$th column of $P^\infty$ is the zero vector. Obviously, the zero vector satisfies $Pv=v$!

In the extreme case when $j$ is absorbing, then $\mathbb{E}_j(T_j)=1$ so $P^\infty_{ij}=\mathbb{P}_i(T_j<\infty)$ is the chance of being absorbed at $j$, starting at state $i$.

It seems that in your model every state is either absorbing or transient, so that every column is made up of absorption probabilities.


By contrast, when $P$ has all strictly positive entries then all states belong to a common recurrent class, and $\mathbb{P}_i(T_j<\infty)=1$ for all $i,j$. In this case, all the columns are constant functions, indeed multiples of the vector $(1,1,\dots,1)^T$. Equivalently all rows are identical and give the unique invariant probability distribution for the chain.


The upshot is that Markov chains with strictly positive $P$ vs. general non-negative $P$ can have quite different limits and behaviour. Please let me know if any of this is unclear.

  • 0
    The short answer to the span problem is this: if $Pv=v$ then $P^nv=v$ for all $n\geq 0$. Letting $n\to\infty$ we have $P^\infty v=v$, which expresses $v$ as a linear combination of the columns of $P^\infty$.2011-08-17