Math Is Fun Forum

Macy

Guest

markov chain

Hi All,

Is there any way we can find axactly how many transitions needed before the 2 by 2 matrix of markov chain reaching the steady state?. I know that we can find the steady state using iterative method but I doubt there is another method less time consuming. Any idea, guys??

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: markov chain

Hi Macy;

As far as I know you can find the steady state using simple matrix operations but I do not know of a way offhand to compute the number of transitions to produce it.
Do you have an example?

It can be done with an absorbing chain. In other words expected times to absorption.

While it is a true that a regular markov chain P  may approach a steady state for some n,

.
n may not be a finite value. In other words it may be the limit of P^n as n appraoches infinity.
So computing n in those cases would be meaningless.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Macy

Guest

Re: markov chain

Hello Bobbym,

How r u?. Long time no see :)
It is obviously when we have transition matrix normally if we want to find the steady state, we just use the limit when n -> infinitive, Or we just say n = 8, 9 ,10 and observe what is happening. That is time consuming, and we do not have the exact value of n when it starts going the steady state. I like to know is there any numerical method to get answer straight away.

Perhaps NO

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: markov chain

Hi Macy, I am okay. How are you?

That is what I am saying above, in some cases it will happen at say n = 10, at some others n = 13.
But for some it is a  limiting process. In other words for n = 1287 you will be close to the steady state but not exactly there.
If you say P^10000 you will get closer but still not there. To get to the steady state you will have to go p^∞.
That is why you can use the simultaneous set of equations to get the exact steady state rather than P^n.
Especially for a 2x2.

So in answer to your question, I do not think there is.

Here is an example:

This is the steady state:

This is the result of P^100 to 100 digits of precision.

As you can see it still has not converged to the steady state even with n = 100.
It will not for any finite n. It will get closer and closer without ever arriving.
To a calculator with less digits it might look like this has converged to the steady state
but that is an illusion.

Of course if you wish to know what n is so that it appears to converge on your calculator
then I can do a fairly simple error analysis and tell you for your technology what n is. Just as
long as you remember it is not really true.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

soroban

Member

Registered: 2007-03-09

Posts: 452

Re: markov chain

. .

. . .

. .

.