4 ms·

This is timely! I have an assignment on these coming up soon. Can anyone with knowledge about this explain something. From what I can tell, many matrix multipli

This is timely! I have an assignment on these coming up soon. Can anyone with knowledge about this explain something. From what I can tell, many matrix multiplications move vectors so they are more inline with eigenvectors if they exist. So Markov Chains are just a continual movement in this direction. Some examples that don't do this that I can think of are the Identity matrix and rotations.. Is there a way to test if a matrix will have this effect? Is it just testing for existence of eigenvectors?

brosco 2y ago
That's a good observation, and it is indeed true for many Markov chains. But your counterexample of the identity matrix is not quite right; every vector is an eigenvector of the identity, so there is no "realignment" needed. More generally speaking, you're asking when the iteration `x_+ = Ax` converges to a fixed point which is an eigenvector of A. This can happen a few different ways. The obvious way is that A has an eigenvector `v` with eigenvalue 1, and all other eigenvalues with magnitude < 1. Then those other components will die out with repeated application of A, leaving only `v` in the limit. For Markov chains, we can get this exact property from the Perron-Frobenius theorem, which applies to non-negative irreducible matrices. Irreducible means that the transition graph of the Markov chain is strongly connected. If that's the case, then there is a unique eigenvector called the stationary distribution (with eigenvalue 1), and all initial conditions will converge to it. In case A is not irreducible, you may have different connected components, and the stationary distribution may depend on which component your initial condition is in. Going back to the n x n identity matrix, it has n connected components (it's a completely disconnected graph with all the self-transition probabilities = 1). So every initial condition is stationary, because you can't change anything after the initial step.
- globalnode 2y ago
  Thank you, some really good info to go on and research.
festivitymn 2y ago
This is close to some of my favorite stuff in math! Beyond just markov chains, matrices do “move” vectors towards eigenvectors sometimes. If a matrix A has eigenvectors x1 and x2 with eigenvalues r1 and r2, A(x1+x2)= r1x1+r2x2 because matrix multiplication is a linear transformation. If we repeatedly multiply x1+x2 by A, A^n(x1+x2)=r1^nx1+ r2^nx2. Then, if r1>r2, all of the terms are growing exponentially but the contribution of x1 to the result grows exponentially faster than the contribution of x2 so for some large n, A^n(x1+x2) = r1^nx1 + some irrelevant error term. This means the largest eigenvalues sort of dominate, and you might especially care about eigenvalues of 1, because those mean Ax=x so x is a steady state and if you can write down A as a matrix you can solve for non zero x and learn about the steady state solutions.
- globalnode 2y ago
  Thanks for that, you made my day.

brosco 2y ago

That's a good observation, and it is indeed true for many Markov chains. But your counterexample of the identity matrix is not quite right; every vector is an eigenvector of the identity, so there is no "realignment" needed. More generally speaking, you're asking when the iteration `x_+ = Ax` converges to a fixed point which is an eigenvector of A. This can happen a few different ways. The obvious way is that A has an eigenvector `v` with eigenvalue 1, and all other eigenvalues with magnitude < 1. Then those other components will die out with repeated application of A, leaving only `v` in the limit. For Markov chains, we can get this exact property from the Perron-Frobenius theorem, which applies to non-negative irreducible matrices. Irreducible means that the transition graph of the Markov chain is strongly connected. If that's the case, then there is a unique eigenvector called the stationary distribution (with eigenvalue 1), and all initial conditions will converge to it. In case A is not irreducible, you may have different connected components, and the stationary distribution may depend on which component your initial condition is in. Going back to the n x n identity matrix, it has n connected components (it's a completely disconnected graph with all the self-transition probabilities = 1). So every initial condition is stationary, because you can't change anything after the initial step.

globalnode 2y ago
Thank you, some really good info to go on and research.

festivitymn 2y ago

This is close to some of my favorite stuff in math! Beyond just markov chains, matrices do “move” vectors towards eigenvectors sometimes. If a matrix A has eigenvectors x1 and x2 with eigenvalues r1 and r2, A(x1+x2)= r1x1+r2x2 because matrix multiplication is a linear transformation. If we repeatedly multiply x1+x2 by A, A^n(x1+x2)=r1^nx1+ r2^nx2. Then, if r1>r2, all of the terms are growing exponentially but the contribution of x1 to the result grows exponentially faster than the contribution of x2 so for some large n, A^n(x1+x2) = r1^nx1 + some irrelevant error term. This means the largest eigenvalues sort of dominate, and you might especially care about eigenvalues of 1, because those mean Ax=x so x is a steady state and if you can write down A as a matrix you can solve for non zero x and learn about the steady state solutions.

globalnode 2y ago
Thanks for that, you made my day.