7
$\begingroup$

I have a Markov matrix $$P=\begin{bmatrix}1&0&0&0&0&0\\\frac{1}{2}&0&\frac{1}{2}&0&0&0\\\frac{1}{4}&0&\frac{1}{4}&\frac{1}{2}&0&0\\\frac{1}{8}&0&\frac{1}{8}&\frac{1}{4}&\frac{1}{2}&0\\\frac{1}{16}&0&\frac{1}{16}&\frac{1}{8}&\frac{1}{4}&\frac{1}{2}\\0&0&0&0&0&1\end{bmatrix}$$ and I want to show that the powers of $P$ converge. I can see numerically that $$\displaystyle\lim_{n\to\infty}P^n=\begin{bmatrix}1&0&0&0&0&0\\.8&0&0&0&0&.2\\.6&0&0&0&0&.4\\.4&0&0&0&0&.6\\.2&0&0&0&0&.8\\0&0&0&0&0&1\end{bmatrix}$$ but are there any general results I can use to actually prove that $\displaystyle\lim_{n\to\infty}P^n$ exists?

$\endgroup$
7
  • $\begingroup$ @A.S. You are right about the convergence, of course. But I don't think the term "irreducible" is quite right when there are absorbing states. $\endgroup$ – user940 Feb 18 '16 at 2:47
  • $\begingroup$ @Byron You are correct. How do you call a chain whose state space can't be separated into components w/no moves between them? (though in this problem, aperiodicity is enough for convergence). $\endgroup$ – A.S. Feb 18 '16 at 2:51
  • 1
    $\begingroup$ Maybe useful: math.stackexchange.com/questions/58249/the-limit-of-matrices $\endgroup$ – user940 Feb 21 '16 at 1:07
  • 1
    $\begingroup$ This chain has three classes $C_1=\{1\}$ which is absorbing, $C_2=\{2,3,4,5\}$ which is transient and $C_3=\{6\}$ which is again absorbing. So, eventually you will land in one of $C_1$ or $C_3$ and remain there. So, the set of all invariant distributions is given by $π(1)=λ=1-π(6)$ for any $λ\in[0,1]$ and $π(x)=0$ else. So, I do not see how it converges to this matrix. $\endgroup$ – Jimmy R. Feb 21 '16 at 13:13
  • $\begingroup$ @Jimmy The matrix exactly satisfies your description. $\endgroup$ – A.S. Feb 21 '16 at 14:38
6
+100
$\begingroup$

Based on the OP we restrict attention to Markov Chains with finite state space $\Bbb X=\{1,2,\dots,N\}$. There are two conditions (i) irreducibility and (ii) aperiodicity which determine the convergence of the transition matrices $A^n$. But firstly lets introduce some minimal (nowhere exhaustive) standard notation that is common in almost all textbook or references about Markov Chains (see also here):

  • Transition probabilities: $p^{(n)}_{ij}$ denotes the probability of going from state $i$ to state $j$ in $n$ time steps. In particular $p^{(1)}_{ij}$ or simply $p_ij$ is defined as $$p_{ij}=P(X_1=i \mid X_0=j)$$
  • Stationary distribution: A probability vector $π$ that satisfies $π=πP$ is called a stationary distribution. To avoid a sloppy exposition I skip the details and let you read yourself about it.
  • Hitting times/ probabilities: Let $T_1:=\inf\{n\ge 0: X_n=1\}$ be the first time that the chain will land in state $1$ and hence remain at it thereafter (as it is absorbing). Accordingly, define $$h^{1}_k:=\Bbb P(T_1<T_6\mid X_0=k)$$ to be the probability that the chain will be absorbed by state $T_1$ starting from state $k \in \mathbb X$.
  • Irreducibility: A Markov chain is said to be irreducible if its state space is a single communicating class; in other words, if it is possible to get to any state from any state. This is not the case here, as your chain has $3$ communicating classes: $C_1=\{1\}, C_2=\{6\}$ which are closed (absorbing states) and $C_2=\{2,3,4,5\}$ which is open or transient.
  • (A)periodicity: A state $i$ has period $k$ if any return to state $i$ must occur in multiples of $k$ time step. If $k=1$ then the state is called aperiodic. If $p_{ii}>0$ then state $i$ and hence all states in its communicating class are aperiodic. This is the case here for all states.

  1. Case 1: irreducible and aperiodic. If a Markov Chain $(X_n)_{n\in \Bbb N}$ with finite state space is (i) irreducible and (ii) aperiodic, then $$\lim_{n\to+\infty} p_{ij}^n=π_j$$ (where I use the usual notation for the transition probabilities and the stationary distribution). So, the question is what happens when either/both of these conditions are violated:

  2. Case 2: irreducible and periodic. If the chain has period $d$ then for every pair $i,j \in \Bbb X$ there exists $0\le r\le d-1$ such that $$\lim_{n\to+\infty}p_{ij}^{md+r}=dπ_j$$ and $p_{ij}=0$ for all $n$ such that $n\neq r \mod d$.

  3. Case 3: reducible. In this case, $π$ is not uniquely defined. For example in the OP we have that any $λπ^1+(1-λ)π^6$ is a stationary distribution for the whole chain, with $π^1(k)=δ_{1k}$ and $π^6=δ_{6k}$ for any $k\in \Bbb X$. Still, he following holds $$\lim_{n\to+\infty}p_{ij}^n=h_i^Cπ_j$$ where $h_i^C$ denotes the hitting probability of the closed Class $C$ with $j\in C$, starting from state $i$. (This is the case in the OP, see calculations below).

  4. Case 3: reducible and periodic. In this case, you only need to adjust Cases $2$ and $3$ to fit the description of any particular chain.


To obtain the limiting matrix in the given example computationally (and not only numerically as you have it), denote the state space of the chain with $\Bbb X=\{1,2,3,4,5,6\}$ and let $h^{1}_k:=\Bbb P(T_1<T_6\mid X_0=k)$ be the probability that he chain will be absorbed by the absorbing state $1$ instead of $6$. Formally $T_1$ is defined as $T_1:=\inf\{n\ge 0:X_n=1\}$ and similarly $T_6$. Then, solving the following system \begin{align}h^{1}_1&=1\\[0.1cm]h^{1}_2&=\tfrac12h^{1}_1+\tfrac12h^{1}_3\\h^{1}_3&=\tfrac14h^{1}_1+\tfrac14h^{1}_3+\tfrac12h^{1}_4\\h^{1}_4&=\tfrac18h^{1}_1+\tfrac18h^{1}_3+\tfrac14h^{1}_4+\tfrac12h^{1}_5\\h^{1}_5&=\tfrac1{16}h^{1}_1+\tfrac1{16}h^{1}_3+\tfrac18h^{1}_4+\tfrac14h^{1}_5+\tfrac12h^{1}_6\\[0.1cm]h^{1}_6&=0\end{align} yields the first column of the limiting matrix as you have it, i.e. $$\left(h^{1}_1,h^{1}_2,h^{1}_3,h^{1}_4,h^{1}_5,h^{1}_6\right)=\frac1{10}(10,8,6,4,2,0)$$ Since the chain will eventually get absorbed by either state $1$ or state $6$ the last column of the limiting matrix follows by complementarity.

$\endgroup$
3
  • $\begingroup$ Thank you for this answer. Could you please tell me where I can find a reference for the notation and terminology you're using, since I only have very limited familiarity with these ideas. $\endgroup$ – Monty Hall Feb 22 '16 at 21:20
  • $\begingroup$ @MontyHall I gave you a reference in Wikipedia and copied some minimal notation here. I think you will find the same notation in every standard textbook about Markov Chain, so I do find a point in referencing a specific book. Just follow your lecture notes/ reference that your lecturer gave you! To fit the standard notation, I also changed the transition matrix from $A$ to $P$, hope this is not a problem. $\endgroup$ – Jimmy R. Feb 23 '16 at 8:54
  • 1
    $\begingroup$ Thanks a lot for this explanation of the terminology and notation, and the reference as well; it is very helpful! $\endgroup$ – Monty Hall Feb 24 '16 at 0:13
1
$\begingroup$

This may be a problem where you should consider finding the singular value decomposition. In particular, if you can find the eigenvalues and their respective eigenvectors for this problem and degenerate $A = Q\Lambda Q^{-1}$, where $\Lambda$ is the eigenvalue matrix and $Q$ is the matrix who's columns are the eigenvectors of the respective $i$th eigenvalues. This way, we can use some of the theorems related to eigenvalue decomposition to find that $$\lim_{n \rightarrow \infty} A^n = \lim_{n \rightarrow \infty} Q \Lambda^n Q^{-1},$$ and because $\Lambda$ is found to be a diagonal matrix, we only need to calculate $\lim_{n \rightarrow \infty} \lambda_i^n$ for each eigenvalue $\lambda_i$.

$\endgroup$
1
  • $\begingroup$ Does this approach work for this matrix? $\endgroup$ – Roland Feb 18 '16 at 2:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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