1

Calculate:

$P_{11}(n)=P(X_n=1|X_0=1)$

where the transition matrix is of the form:

$$\left[\begin{matrix}0 & 1 &0 \\ 0 & \dfrac{1}{2} & \dfrac{1}{2} \\ \dfrac{1}{2} & 0 & \dfrac{1}{2}\end{matrix}\right]$$

okay so I worked out my eigenvalues of the matrix, and got $\lambda = 1, \pm \dfrac{i}{2}$

$P_n$ should have the form $P_n=C_1(\lambda _ 1)^n + C_2\bigg(\dfrac{i}{2}\bigg)^n + C_3\bigg(\dfrac{-i}{2}\bigg)^n$

Then as we want $P_{11}(n)$ to be real we know that: $\bigg(\pm\dfrac{i}{2}\bigg)^n=\bigg(\dfrac{1}{2}\bigg)^n \bigg(\cos\bigg(\dfrac{n \pi}{2} \bigg) \pm i \sin\bigg(\dfrac{n \pi}{2} \bigg) \bigg)$

Subbing this all back in I get the equation: $$P_{11}(n)=C_1 + \bar{C_2}\bigg(\dfrac{1}{2}\bigg)^n \cos\bigg(\dfrac{n \pi}{2}\bigg) + \bar{C_3}\bigg(\dfrac{1}{2}\bigg)^n \sin\bigg(\dfrac{n \pi}{2}\bigg)$$

I am then stuck as to how to calculate the values of my coefficients. Any guidance would be great, thank you

Alex
  • 19,262
sarahusher
  • 834
  • 1
    Try the initial condition $n = 0$. – Tunococ May 23 '14 at 09:29
  • But how do I know what $P_{11}(0)$ is to compare it to? – sarahusher May 23 '14 at 09:31
  • 1
    From its definition, which is your second line up there. – Tunococ May 23 '14 at 09:31
  • I'm getting myself confused. So if for $P_{11}(2)=P(X_2=1 | X_0=1)$ what does that actually mean? – sarahusher May 23 '14 at 09:36
  • That is a good question. You should think about what the expression $P(X_2 = 1 \mid X_0 = 1)$ means. You should be able to compute, without the method you are trying to follow now, $P(X_n = 1 \mid X_0 = 1)$ manually for any $n$. – Tunococ May 23 '14 at 09:39
  • Is it something to do with the probability of being in state $1$ after $n$ steps? – sarahusher May 23 '14 at 09:41
  • 1
    I'll read $P(X_n = 1 \mid X_0 = 1)$ for you. It's the probability of $X_n = 1$ given that $X_0 = 1$. A longer version of the same thing is the probability of ending up at location $1$ after moving $n$ steps (this is what is meant by $X_n = 1$) starting from location $1$ (this is what is meant by $\mid X_0 = 1$), where each move is taken at random according to the transition matrix. – Tunococ May 23 '14 at 09:44
  • so $P(X_0=1|X_0=1)$ has to be $1$ because you're told that's where it is, is that right? Then $P(X_1=1|X_0=1)$ has to be $0$ because you can't get back to State 1 from state 1 in one step? But then, I'm sorry, I'm still confused how you determine $P(X_2=1|X_0=1)$ just from reading the matrix? – sarahusher May 23 '14 at 09:50
  • 2
    I guess now is a good time for you to understand what it means to multiply a matrix with a vector in this context. As a first example, let me write out everything: $P(X_2 = 1 \mid X_0 = 1) = P(X_2 = 1 \mid X_1 = 1)P(X_1 = 1 \mid X_0 = 1) + P(X_2 = 1 \mid X_1 = 2)P(X_1 = 2 \mid X_0 = 1) + P(X_2 = 1 \mid X_1 = 3)P(X_1 = 3 \mid X_0 = 1)$. Note that you need to know $P(X_1 = k \mid X_0 = 1)$ for $k = 1, 2, 3$. I hope you can see the pattern and relate it to matrix-vector multiplication by yourself. – Tunococ May 23 '14 at 09:57
  • The values of the three constants $C_i$ are fully determined by the three initial conditions $P_{11}(0)=1$, $P_{11}(1)=0$, $P_{11}(2)=0$. – Did May 23 '14 at 10:56

1 Answers1

0

Since the matrix $P$ has $3$ distinct eigenvalues it is diagonalizable. So, $\exists$ an invertible matrix $U$ such that $P=U\Lambda U^{-1}$ where $\Lambda$ is a diagonal matrix. Here, $U$ will be formed with columns as the eigenvectors of the of the matrix $P$. So say if the eigenpairs are $(\lambda_i,v_i),\ 1\le i\le 3$, then the matrices $U$ and $\Lambda$ will be $$U=[v_1\quad v_2\quad v_3]\\ \Lambda=diag(\lambda_1\lambda_2,\lambda_3)$$ Then, $$P=U\Lambda U^{-1}\Rightarrow P^n=U\Lambda^n U^{-1}$$. So, now, $P_{ij}(n)$ is just the element in the $(i,j)$ entry of $P^n$.

Samrat Mukhopadhyay
  • 16,277