4
$\begingroup$

Given a markov chain where the next state is related to the previous state by the following matrix: $$\begin{array}{c|ccc} & A & B & C\\ \hline A & p_1 & q_1 & r_1\\ B & p_2 & q_2 & r_2\\ C & p_3 & q_3 & r_3\\ \end{array}$$ Where the system of equations is given by

A$_{n+1} = p_1A_n + p_2B_n+p_3C_n$

B$_{n+1} = q_1A_n + q_2B_n+q_3C_n$

C$_{n+1} = r_1A_n + r_2B_n+r_3C_n$

How can the final relationships be found? (i.e. the limit of each function as n $\rightarrow \infty$, assuming A$_0 = B_0 = C_0$).

1 Answers 1

3

If there is a limit, it will satisfy $$\eqalign{A&=p_1A+p_2B+p_3C\cr B&=q_1A+q_2B+q_3C\cr C&=r_1A+r_2B+r_3C\cr}$$ so it's just a matter of solving a system of three linear equations in three unknowns.

  • 3
    The linear system you give is underdetermined, since all the columns of the transition matrix (had better) sum to one. To get a unique solution, you need to drop one of the equation and replace it with a normalization condition, e.g. $A + B + C = 1$.2012-03-05
  • 2
    Also, of course, even that doesn't guarantee that the solution is unique, nor does uniqueness of the solution guarantee that the chain actually converges. For example, the chain given by $p_1 = q_3 = r_2 = 1$ and $p_2 = p_3 = q_1 = q_2 = r_1 = r_3 = 0$ neither has a unique stationary distribution _nor_ converges to any stationary distribution from most starting points.2012-03-05
  • 0
    Quite right. I didn't want to write a complete treatise on Markov chains, just enough to get OP started, especially since OP has put no effort into letting us know what level of response is required.2012-03-05
  • 0
    But you can't solve the system of equations, because you have six unknowns, since we don't know A, B, C or A$_{n+1}$, B$_{n+1}$, or C$_{n+1}$2012-03-05
  • 0
    The ones with the subscripts - where do you see those in the equations I wrote? The only unknowns are $A$, $B$, and $C$.2012-03-06
  • 0
    I understand what you're saying now - as n approaches infinity, S$_n$ = S$_{n+1}$ and so on, so that's how you don't have different unknowns. Thanks Ilmari for the tip on including the normalization condition. I couldn't solve my problem until I used that.2012-03-07