0
$\begingroup$

So I have been learning about Markov-Chains lately when I stumbled across something that got me thinking. I was working on the relatively simple Markov-Chain where the transition matrix is

$A=\begin{bmatrix}0.5&0.3&0.2\\0.1&0.1&0.2\\0.4&0.6&0.6\end{bmatrix}$ and the inital state is $V=\begin{bmatrix}17'000\\12'000\\3'000\end{bmatrix}$ So, in order to find out how the system is when it has stabilized, I would calulate $\lim_{n\to \infty}A^nV$. However, I could also just find the steady state vector V* off the get go by row reducing $[A-I|0]$ and save a huge ton of work. (But i will need to scale it.) Will this always work? Is there any instance where I have to actually diagonalize the steady state matrix (given that this is possible) in order to find the stable state of the system? This is what i have learned to do initially, but it just seems like a huge waste of time if I can be guaranteed to get the solution by just doing 1 simple row reduction and scaling instead. :)

$\endgroup$

2 Answers 2

1
$\begingroup$

If the limit exists, then it will be a solution to $Ax=x$. But it is possible for this to not have a unique solution. In this case you need to expand the initial condition in the whole eigenvector basis (or generalized eigenvector basis, perhaps) in order to extract the limit. It turns out that "generically" this does not happen: if you have an irreducible Markov chain and the limit exists, then the limit is unique. You can ensure that the limit exists by assuming aperiodicity.

$\endgroup$
4
  • $\begingroup$ So if the limit exists, I am guaranteed to find it by solving Ax=x? This sounds resonable. If Ax=x has two solutions or three, does this mean that different inital vectors might result in different stable states? Or for example an endstate which alternates between too or three states every term. Im not qyite sure what you mean about ekpanding the initial condition tho, do you mean vriting it as a sum weighted sum of solutions of Ax=x? I'm not that experienced you see, but I really want to understand it 😜 $\endgroup$
    – AfterMath
    Mar 22, 2018 at 14:41
  • $\begingroup$ @AfterMath $Ax=x$ is a homogeneous linear system of equations (once you move the $x$ to the other side). So if it has any nontrivial solutions, then it has infinitely many. If it has only a one-dimensional space of solutions, then it will only have one normalized solution, which is the unique steady state distribution. It may have a 2 or higher dimensional space of solutions, in which case there are infinitely many steady state distributions. In this case $\lim_{n \to \infty} A^n x$ depends on $x$, even when $x$ is constrained to be a probability vector. $\endgroup$
    – Ian
    Mar 22, 2018 at 14:58
  • $\begingroup$ @AfterMath (Cont.) To extract this dependence, you need the Jordan form of $A$ (the entire thing, not just the eigenvectors with eigenvalue $1$). $\endgroup$
    – Ian
    Mar 22, 2018 at 15:01
  • $\begingroup$ Okay, thanks. I'll check into it! $\endgroup$
    – AfterMath
    Mar 22, 2018 at 15:02
1
$\begingroup$

In a markov chain matrix, all its eigenvalues are less or equal than 1 ( i.e. $\lambda_i\leq 1$, you can prove this theorem) . Then, the stable state only depends on $\lambda=1$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .