Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
This was excellent! Thank you very much. –  Nicole Aug 17 '11 at 14:42
    
What would you consider a good reference for this, so I can learn more? (for example, why the columns span the eigenspace of 1) –  Nicole Aug 17 '11 at 14:46
1  
I have some notes about Markov chains (and other topics) on my page for the course STAT 580. The results in my answer here are explained there, and there are additional references to good books. –  Byron Schmuland Aug 17 '11 at 14:50
    
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$. –  Byron Schmuland Aug 17 '11 at 15:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.