Probability after n steps

Question

I have been studying markov chains for my Introductory Stochastic Processes exam, but i am struggling with the following problem:

Question: Consider a matrix with state space $S=\{1,2,3\}$ and the following one step transition matrix: $$P=\left(\begin{array}{ccc}0 & 0.5 & 0.5 \\ 0.5 & 0 & 0.5 \\ 0 & 0 & 1\end{array}\right)$$

Let $X_{n}$ be the state of the chain at time $n$ and suppose that $X_{0} = 1$. Find the probability that $\mathbb{P}\left(X_{n}=2\right)$ for every $n \in \mathbb{N}$.

What have i tried so far? I tried writing $$P\left(X_{n}=j \mid X_{0}=i\right)= P\left(X_{n}=2 \mid X_{0}=1\right) = \left(P^{n}\right)_{12}$$ since we know that for time-homogeneous, discrete markov chains, the following holds: $$ P_{i j}^{n}=P\left(X_{n}=j \mid X_{0}=i\right), \text { for all } i, j $$ However, when raising the transition matrix $P$ to the nth power, entries behave differently depending on the parity of n, which got me a bit confused. Is my approach solid? Is there another way of solving this problem?

Any help is appreciated. Thanks in advance, Lucas

Answer 1

I think it's normal to see changes wrt parity because if in any of the previous states you hit $3$, you'll stay there, and otherwise, you'll end up alternating between 1 and 2. So, for example, for $n=1$, it's impossible to be in state $1$ because $X_0=1$ and you can only go to state $2$ or $3$.

Taking the power of the transition matrix is a straightforward way to calculate what you want. But, given the simplicity of the states, for ending at state $2$ after $n$ steps, you need to have odd parity and always alternate between states 1 and 2, i.e. each step is with $1/2$ prob. So, $P(X_n=2|X_0=1)=(1/2)^n$ if $n$ is odd, o/w it is $0$.

Answer 2

Gunes gives the answer by reasoning (which is probably what you should do for this exam).

A more general and straightforward method (but which requires more computation time) is the following:

You decompose the begin state as a sum of eigenvectors. Then you describe the evolution in terms of the evolution of those eigenvectors.

• Compute the eigenvectors and eigenvalues

  $$v_1 = \begin{bmatrix} 0\\0\\1\end{bmatrix}, \quad v_2 = \begin{bmatrix} 1\\1\\-2\end{bmatrix}, \quad v_3 = \begin{bmatrix} 1\\-1\\0\end{bmatrix}$$

  $$\lambda_1= 1,\quad \lambda_2 = 0.5, \quad \lambda_3 = -0.5$$

• Write the begin state as a linear sum of the eigenvectors

  $$x_0 = a_1 v_1 + a_2 v_2 + a_3 v_3$$

  In the example we got $a_1,a_2,a_3 = 1, 1/2,1/2$ or

  $$\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = 1 \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} + \frac{1}{2} \begin{bmatrix} 1 \\ 1 \\ -2 \end{bmatrix} + \frac{1}{2} \begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix}$$

• The solution will be (the eigenvector components of the begin state each individually multiply with a power of the eigenvalue)

  $$x_n = a_1 \lambda_1^n v_1 + a_2 \lambda_2^n v_2 + a_3 \lambda_3^n v_3 $$

  For the 2nd state this means

  $$x_{n,2} = a_2 0.5^n - a_3 (-0.5)^n$$

  and with the $a_i$ for this case it is

  $$x_{n,2} = 0.5(0.5^n - (-0.5)^n)$$

  Which is like gunes answer $x_{n,2} = 0$ for even $n$ and $x_{n,2} = 0.5^n$ for odd $n$.

I do not think that this is what you are supposed to do in your exam. But, you can use this knowledge to your advantage in the idea that you can use it to verify/check your result. You know of which form the solution must be, namely some sum of powers of the eigenvalues (of which one will equal 1 if it is a probability transition).

Answer 3

The very fact that the Markov chain can be characterized by a constant transition matrix means that it is homogeneous. It may be easier to understand the concepts that you're struggling with with a simpler matrix. Consider

$$A=\frac 1 3\left(\begin{array}{ccc}1 &2 \\ 2 & 1\end{array}\right)$$

This matrix will switch the relative sizes of the two states: if we have $v_2 = Av_1$, the first entry of $v_2$ will be greater than the second iff the first entry of $v_1$ is smaller than the second. So which entry is greater depends on the parity of the power of $A$.

However, remember that homogeneity is about conditional probability. While the behavior of a particular starting state depends on the parity of the power, the conditional behavior doesn't: if the first entry of $A^nv_1$ is greater than the second, then the second entry of $A^{n+1}v_1$ is greater than the first. That statement is true regardless of the parity of $n$. Homogeneity is what we can say about $A^{n+1}v$ conditional on $A^{n}v$. Since $A^{n+1}v$ is by definition equal to $A(A^{n}v)$, we know that the transition probabilities from $A^{n}v$ to $A^{n+1}v$ are constant, and given by $A$.