1
$\begingroup$

I can represent stochastically-articulated sequences of states using a transition matrix M where a given entry in cell (i,j) corresponds to the probability of state j given that the current (or, most recently settled on) state is i.

For example, a coin has two possible states that are equiprobable no matter what the current state is. Its transition matrix has two rows and two columns, with every cell (i,j) containing the number .5. The expected frequency of Heads in a sequence defined by this transition matrix (where the first state is chosen randomly) is .5 * n where n is the length of the sequence.

When the rows of a transition matrix are all equal, it seems that for a given state you can derive the factor to be multiplied by n by just averaging the values of its corresponding column. Even with a unfair coin where heads has a probability of .6 (making the coin's 2x2 transition matrix's rows equal [.6 .4]), this method accurately expects a produced sequence to be 60% heads and 40% tails.

But suppose what produces the Heads and Tails isn't a coin, and that it has a transition matrix with first row [.5 .5] and second row [.4 .6]. My method described before expects 45% heads and 55% tails, but simply simulating the sequence production mechanism for a few states suggests that this isn't quite correct.

After the first state is decided randomly, if we don't presume that it has settled on any value, I at least believe we find that the probability of a Heads in the next state is (.5 * .5 + .5 * .4) = .45. But the probability of Heads on the next state without presuming anything about the sequence's past is (.5*.5*.5 + .5*.5*.4 + .5*.4*.5 + .5*.6*.4) = .445. And so I suspect that because of the bias for Tails when already at Tails, a smaller proportion of heads can be expected than just .45.

My problem is a bit more abstract than this particular one - I handle transition matrices for state spaces much greater than 2 (up to 50, actually). But my hope is that there is some formula or algorithm that will allow me to calculate the expected frequency of any state in a sequence of length n given a transition matrix that guides its articulation. Can you help me find it?

$\endgroup$
1
$\begingroup$

Let's say you know where you start, and it's in state $i$. Let's also name the transition matrix $Q$. The expected count of how many times you hit state $j$ in $n$ steps will be $$\sum_{t=1}^{n} Q^{t}_{i,j}$$ and therefore the expected frequency will be that number, divided by $n$.

Just as an interesting addition: when $n\rightarrow \infty$, the expected count is only finite for absorbing markov chains (otherwise you will be in any state an infinite number of times), and the answer is, as expected, the appropriate entry of $$N= \sum_{t=1}^{\infty} Q^{t}$$ The matrix $N$ is called the fundamental matrix of an absorbing markov chain, and it is well-studied. See, for example https://hips.seas.harvard.edu/blog/2013/02/15/the-fundamental-matrix-of-a-finite-markov-chain/.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.