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

Question

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:

${\displaystyle 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%:

${\displaystyle \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

${\displaystyle \Pr(X_0=sunny) = 1,}$ ${\displaystyle \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?

Answer 1

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$.