0
$\begingroup$

Let's say I have the Markov chain $\begin{bmatrix} 0 && 1 \\ 1 && 0 \end{bmatrix}$. From my understanding this is periodic and thus its convergence depends on the initial conditions. However, I have two questions about this:

1) How am I able to compute that it's periodic (and its period) from the transition matrix? I found the following, but I'm not sure how to interpret this for a transition matrix.$$d( x) = \{\gcd{n \in \mathbb{N}+ : P^n ( x, x) > 0}\}$$

2) Am I able to compute the vectors which will cause this periodic Markov chain to converge to a steady state? I think for this matrix the only vector $v_0$ which does this is $\begin{bmatrix} \frac{1}{2} \\ \frac{1}{2}\end{bmatrix}$.

$\endgroup$

1 Answer 1

1
$\begingroup$

Note that for $$A= \begin{bmatrix} 0 && 1 \\ 1 && 0 \end{bmatrix}$$ we have $$A^2=I$$ thus it is periodic with period $2$.

The eigenvalues of $A$ are the roots of its characteristic polynomial, $$P(\lambda ) = \lambda ^2 -1$$ namely $\lambda =\pm 1$ with corresponding eigenvectors of $ \begin {bmatrix} 1\\1\end {bmatrix}$ and $ \begin {bmatrix} 1\\-1\end {bmatrix}$

The eigenvalue $\lambda =1$ gives us the equilibrium state which is $ \begin {bmatrix} 1\\1\end {bmatrix}$ Upon scaling we get $V=\begin{bmatrix} {1/2}\\{1/2} \end{bmatrix}$

$\endgroup$
6
  • $\begingroup$ Thank you! I’m sorry, I should’ve been more clear. For the first question, is there a way to find it without just observation? For example, if it had period 7, I wouldn’t know that the matrix’s 7th power is the identity. Also, for the second question, I’m familiar with eigenvector computation and the steady state solution - I’m wondering if there’s a way to know what initial conditions cause it to converge to the steady state. I’m not sure if all periodic Markov chains converge only if their initial condition is the steady state. $\endgroup$
    – rb612
    Apr 25, 2018 at 8:09
  • $\begingroup$ The eigenvector associated with eigenvalue of $1$ is the equilibrium state. For the first question, if the matrix is periodic, the period could be found by the smallest positive $n$ for which $A^n=I$ $\endgroup$ Apr 25, 2018 at 8:19
  • $\begingroup$ thank you - is the only initial condition that converges to the equilibrium state the eigenvector? Is this a theorem or some proven statement? $\endgroup$
    – rb612
    Apr 25, 2018 at 8:25
  • $\begingroup$ yes, you may find the proof in a linear algebra text. $\endgroup$ Apr 25, 2018 at 8:27
  • $\begingroup$ but that statement is true only if the matrix is periodic right? $\endgroup$
    – rb612
    Apr 25, 2018 at 17:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .