I am asking your help for a question I couldn't find the answer on the internet.

I am considering a markov chain with 3 states. The transition probability matrix is pij, i, j from 1 to 3. pij is the probability for the markov chain to be in state i at time t knowing it is in state j at time t-1.

I'm a looking for the non conditional probability: P(state in t=j).

I know the formula in the case where there are 2 states, but I can't find a general formula, for n states (3 states in my case). I guess I found the answer in some academic articles, but I don't understand it and how to apply it.

  • $\begingroup$ Unconditional probabilities like this are expressable as a two-way contingency table (with 3 levels or states) based on the current status at time, t, classified against the object's status at time t-1, summarized across all time periods, T, as t vs t-1, t-1 vs t-2, t-2 vs t-3, and so on. Obviously, this can easily be written as a formula but for the fact that I don't know the CV version of Latex. There is a wide literature on this. So, I'll leave it as a comment. One additional note, log-linear models would provide a functional form for expressing conditional probabilities. $\endgroup$ Nov 25 '16 at 14:52
  • $\begingroup$ There is no unique definition for an unconditional probability: do you mean, e.g., the stationary distribution? $\endgroup$
    – Xi'an
    Nov 25 '16 at 15:52
  • $\begingroup$ Making two identical rows in the transition matrix, indicates it doesn't matter which of two states was visited last. A Markov chain does not require 'one step' dependence, a completely independent process is Markovian (but, if so, perhaps the extra notation is then not worth the trouble) $\endgroup$
    – BruceET
    Sep 17 '19 at 6:21

The answer depends on the probabilities of the initial state.

You can work it out from basic axioms of probability. It's helpful as well as insightful to use matrix notation, but you only need to know two things about matrices: how to multiply them and the fact that multiplication is associative. Specifically, when $\mathbf{x}$ is a vector and $\mathbb{A},\mathbb{B}$ are matrices, then $$(\mathbf{x}\mathbb{A})\mathbb{B} = \mathbf{x}(\mathbb A \mathbb B)$$ whenever either expression is defined.

Let the initial state correspond to time $t=0.$ At any time $t\ge 0$ let the unconditional probability of state $j$ be $p_t(j),$ forming a row vector $\mathbf{p}_t$ with one component for each state in the set of all states $S.$ At time $t\in\{0,1,2,\ldots\}$ the answer in terms of the transition matrix $$\mathbb{P} = (p_{ij})$$ is

$$\mathbf{p}_t = \mathbf{p}_0\mathbb{P}^t.$$

These matrix powers are defined recursively as

$$\mathbb{P}^0 = \mathbb{I}_S$$

(the identity matrix on the states $S$) and

$$\mathbb{P}^t = \mathbb{P}^{t-1}\mathbb{P}$$

for $t=1,2,3,\ldots.$

Because $\mathbb{P}^0$ is defined to be the identity matrix, the formula is true at $t=0.$ Suppose inductively that this formula is still correct at some arbitrary time $t-1.$ We need only show it will then be correct at time $t.$

To this end, decompose the event $\mathcal{P}_{t}(j):$ "the system is in state $j$ at time $t$" into a union of events of the form $\mathcal{P}_t(i\to j):$ "the system made a transition from state $i$ to state $j$ at time $t$" where $i$ ranges over all the states.

Being a Markov chain means these transitions are independent of the probabilities of their starting states, and independence only means the probabilities multiply:

$$\Pr(\mathcal{P}_t(i\to j)) = p_{t-1}(i)\, p_{ij}.$$

Because these transitions all start from different states, they have nothing in common. Thus, it is axiomatic that their probabilities add, giving

$$p_t(j) = \Pr(\mathcal{P}_{t}(j)) = \sum_{i\in S} \Pr(\mathcal{P}_{t}(i\to j)) = \sum_{i\in S} p_{t-1}(i)\, p_{ij}.$$

But that sum merely expresses the law of matrix multiplication when computing $\mathbf{p}_{t-1}$ times $\mathbb{P},$ and so can be written in vector form as

$$\mathbf{p}_t = \mathbf{p}_{t-1}\,\mathbb{P} = \left(\mathbf{p}_{0}\,\mathbb{P}^{t-1}\right)\mathbb{P} = \mathbf{p}_{0}\left(\mathbb{P}^{t-1}\mathbb{P}\right) = \mathbf{p}_{0}\,\mathbb{P}^t$$

as claimed, QED.

For example, suppose the transition matrix is $$\mathbb{P} = \pmatrix{\frac{1}{2} & \frac{1}{2} & 0 \\ 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 1}.$$

Then you can work out that

$$\mathbb{P}^t = 2^{-t}\pmatrix{1 & t & 2^t-t-1 \\ 0 & 1 & 2^t-1 \\ 0 & 0 & 2^t}.$$

If, say, all states are equally likely initially, that means $$\mathbf{p}_0 = \pmatrix{\frac{1}{3}, & \frac{1}{3}, & \frac{1}{3} }$$

and therefore the chances at time $t$ are

$$\mathbf{p}_t = 2^{-t} \pmatrix{\frac{1}{3}, & \frac{1}{3}, & \frac{1}{3} } \pmatrix{1 & t & 2^t-t-1 \\ 0 & 1 & 2^t-1 \\ 0 & 0 & 2^t} = \pmatrix{\frac{1}{3\,2^t}, & \frac{1+t}{3\,2^t}, & 1 - \frac{2+t}{3\,2^t} }.$$

Wikipedia has an example in its article on Markov chains with links to an entire article on Markov chain examples.


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.