1

Let the transition matrix of a two-state Markov chain be

$$P = \begin{bmatrix}p& 1-p\\ 1-p& p\end{bmatrix}$$

Questions:

a. Use mathematical induction to find $P^n$.

b. When n goes to infinity, what happens to $P^n$?

Attempt: i'm able to find

$$P^n = \begin{bmatrix}1/2 + 1/2(2p-1)^n& 1/2 - 1/2(2p-1)^n\\ 1/2 - 1/2(2p-1)^n & 1/2 + 1/2(2p-1)^n\end{bmatrix}$$

I don't know how to use induction to get there even though I know induction step. i.e n=1 true. suppose it's true for n = k, we need to prove it's also true for k+1...

jkn
  • 5,129
  • 25
  • 53
Michael
  • 11

1 Answers1

3

Your initial $P^1$ matrix is has first row $[p,1-p]$ and second row the reverse of that. Your goal matrix for $P^n$ also has its entries in the same form, with first row say $[a_n,b_n]$ and second row the reverse of that. So an approach would be to multiply the matrix for $P^n$ by the matrix $P$, and its top row will be $$[pa_n+(1-p)b_n,(1-p)a_n+pb_n],$$ with bottom row the reverse of that. Now you just have to check that when $$a_n=1/2+(1/2)(2p-1)^n, \\ b_n = 1/2-(1/2)(2p-1)^n,$$ and the above calculations are done, you obtain the formulas for $a_{n+1}$ and $b_{n+1}$ in the new version of row one of $P^{n+1}$. That is, the form where the above vlues of $a_n,b_n$ have their $n$ replaced by $n+1$. It seems this should be just simple algebra, though admittedly I didn't check, I'm just suggesting an approach.

ADDED: Actually the algebra is very simple, if you do the $1/2$ part separately from the $\pm (2p-1)^n$: $p\cdot (1/2)+(1-p)\cdot(1/2)=1/2$, while $$p\cdot (1/2)(2p-1)^n +(1-p) \cdot (-1/2)(2p-1)^n = \\ p \cdot (1/2)(2p-1)^n +(p-1) \cdot(1/2)(2p-1)= \\ (2p-1)\cdot(1/2) (2p-1)^n,$$ which is of course $(1/2)(2p-1)^{n+1}.$

Parcly Taxel
  • 103,344
coffeemath
  • 29,884
  • 2
  • 31
  • 52