Markov Chain - finding $P^{n}$ from graph

50 Views Asked by At

given the following graph enter image description here

I was tasked with finding $P^{(n)}$, my initial instinct was to find $P$, which i had. $$P =\begin{pmatrix} 1 & 0 & 0 \\\tfrac{1}{6} & \tfrac{1}{2} & \tfrac{1}{3} \\ 0 & 0 & 1 \end{pmatrix}$$ afterwards I was wondering if there’s a good method for finding $P^{(n)}$ other than multiplying $P$ by itself and trying to notice a pattern.
Solution: enter image description here

1

There are 1 best solutions below

3
On BEST ANSWER

It depends on what you mean by a "good" method. One that works here? Or one that may be useful in some other cases? Or one which can always be applied?

Looking at the graph, you never leave states $1$ or $3$, while you stay in state $2$ with probability $\frac12$ at each step and when you leave you are twice as likely to go to state $3$ as to state $1$. So:

  • You never leave state $1$ so the first row of $P^n$ must be: $\quad 1 \quad \quad 0 \quad \quad 0$

  • You stay in state $2$ after $n$ steps with probability $\frac1{2^n}$, so leave at at some stage with probability $1-\frac1{2^n}$, and if you leave then the conditional probability of going to state $1$ (and staying there) is $\frac13$ and of going to state $3$ (and staying there) is $\frac23$, so the second row of $P^n$ must be: $\quad \frac13\left(1-\frac1{2^n}\right) \quad \frac1{2^n} \quad \frac23\left(1-\frac1{2^n}\right)$

  • You never leave state $3$ so the third row of $P^n$ must be: $\quad 0 \quad \quad 0 \quad \quad 1$