# How many Markov chains are there for 2 states in 1, 2 and 3 steps?

wiki uses this example to illustrate Markov chains.

The probabilities of weather conditions (modeled as either rainy or sunny), given the weather on the preceding day, can be represented by a transition matrix:

$$P={\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}}$$

The matrix P represents the weather model in which a sunny day is 90% likely to be followed by another sunny day, and a rainy day is 50% likely to be followed by another rainy day. The columns can be labelled "sunny" and "rainy", and the rows can be labelled in the same order.

The weather on day 1 is known to be sunny. This is represented by a vector in which the "sunny" entry is 100%, and the "rainy" entry is 0%:

$$\mathbf {x} ^{(0)}={\begin{bmatrix}1&0\end{bmatrix}}}$$

for day n + 1(Note: the original value on wiki is n, which seems to be incorrect)

$${\mathbf {x}}^{{(n)}}={\mathbf {x}}^{{(0)}}P^{n}$$

The superscript (n) is an index, and not an exponent.

In the particular case, the state space of the chain is {rainy , sunny}

how many Markov chains are there respectively on day1, day2 and day3?

for example, on day1

$$\Pr(X_0=sunny) = 1,}$$ $$\Pr(X_0=rainy) = 0,}$$ how many Markov chains are there on day1, 1 or 2?

how many Markov chains are there on day2 and day3 respectively?

• are you wanting to know how many sequence-permutations to expect depending on how long the chain is? Aug 5, 2019 at 12:57
• @ReneBt Yes. and how to compute how long. does day 1 count 1 or 0? Aug 5, 2019 at 14:11
• Your question is worded that day 1 is non-probabilistic, but would you always want to start the chain on a sunny day or will you sometimes start it on a rainy day with some probability of occurrence? That would influence how you count day 1 and determine possible permutations. Aug 5, 2019 at 15:26
• @ReneBt Your comments is very helpful! To make things unambiguous, I would like to have the chain always start with a sunny day (day 1 is non-probabilistic), day 2 and next are probabilistic. Aug 5, 2019 at 22:38

Let $$\{X_n:n=0,1,2\ldots\}$$ be a Markov chain with transition matrix $$P$$. Then the $$(i,j)$$-entry of $$P$$ is the probability of transitioning from state $$i$$ to state $$j$$ in $$n$$ steps: $$P_{ij} = \mathbb P(X_n = j\mid X_0 = i).$$ Here we have
$$P = \left( \begin{array}{cc} \frac{9}{10} & \frac{1}{10} \\ \frac{1}{2} & \frac{1}{2} \\ \end{array} \right),\quad P^2 = \left( \begin{array}{cc} \frac{43}{50} & \frac{7}{50} \\ \frac{7}{10} & \frac{3}{10} \\ \end{array} \right),$$ and in general $$P^n = \left( \begin{array}{cc} \frac{1}{6} \left(\left(\frac{2}{5}\right)^n+5\right) & \frac{1}{6} \left(1-\left(\frac{2}{5}\right)^n\right) \\ \frac{5}{6} \left(1-\left(\frac{2}{5}\right)^n\right) & \frac{1}{3} \left(\frac{2}{5}\right)^{n-1}+\frac{1}{6} \\ \end{array} \right),$$ so that $$\lim_{n\to\infty} P^n = \begin{pmatrix} \frac56&\frac16\\\frac56&\frac16. \end{pmatrix}$$ Hence $$X_n$$ has limiting distribution $$\lim_{n\to\infty} \mathbb P(X_n = j) = \begin{cases}\frac56,&j=\mathrm{sunny}\\ \frac16,&j=\mathrm{rainy} \end{cases},$$ independent of the distribution of $$X_0$$.