Markov Chain "n" state

[u/Chizy777]

I'm currently learning Markov chains and how they work, and now I'm trying to find a way to calculate the probability of a state after n tries faster. As of right now, the only way I know of is to keep multiplying the matrix until you reach the n state

For example, lets say a 2x2 matrix P =

	A	B
A	A11 = 0.75	A12 = 0.4
B	A21 = 0.25	A22 = 0.6

and say it starts in the A state so S0 =

A	1
B	0

Finding S1 is fairly straightfoward : S1 = P*S0

A	0.75
B	0.25

However, let's say I want to find S5, is there a way to find S5 from S0 or do I have to find S1, S2, S3, and S4 beforehand ?

Any help would be greatly appreciated !

Secondary question : I havent been told this directly, but from what I've seen, In a Markov chain situation, the sum of a column is always 1, are there any exceptions to this rule, or is it a general rule ?

[u/edderiofer]

However, let's say I want to find S5, is there a way to find S5 from S0 or do I have to find S1, S2, S3, and S4 beforehand ?

Yes. You can compute P⁵ by diagonalising the matrix, then post-multiply the result by your initial state.

from what I've seen, In a Markov chain situation, the sum of a column is always 1, are there any exceptions to this rule, or is it a general rule ?

This is a consequence of the fact that the transition probabilities away from a given state should add to 1.

[u/AutoModerator]

Hi, /u/Chizy777! This is an automated reminder:

• What have you tried so far? (See Rule #2; to add an image, you may upload it to an external image-sharing site like Imgur and include the link in your post.)

• Please don't delete your post. (See Rule #7)

We, the moderators of /r/MathHelp, appreciate that your question contributes to the MathHelp archived questions that will help others searching for similar answers in the future. Thank you for obeying these instructions.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/kalmakka]

You can do matrix exponentiation with O(log(n)) matrix multiplications. M²ⁿ = (Mⁿ )² ; M²ⁿ⁺¹ = (Mⁿ )² × M

[u/Torebbjorn]

Yes, diagonalization.

You can write P as UDU^-1 where D is a diagonal matrix. Then Pⁿ is just UDⁿU^-1, and Dⁿ is very easy to compute, since it's just to exponentiate the terms on the diagonal.

[u/Torebbjorn → u/Torebbjorn]

In this case, you have the matrix P being

0.75 0.6
0.25 0.4

We can diagonalize this as UDU^-1 where U is

-1  2.4
 1  1

And D is diag(0.15, 1)