Consider a system which is described at any time as being in one of a set of $N$ distinct states, $1,2,3,...,N$. We denote the time instants associated with state changes as $t = 1,2,...$, and the actual state at time $t$ as $a\_{ij} = p = [s\_{i}=j\ |\ s\_{i-1}=i], 1\le i,j \le N$.

For the special case of a discrete, first order, Markovchain, the probabilistic description for the current state (at time $t$) and the predecessor state is $s\_{t}$. Furthermore we only consider those processes being independent of time, thereby leading to the set of state transition probability $a\_{ij}$ of the form: with the properties $a\_{ij} \geq 0$ and $\sum_{i=1}^{N} A_{ij} = 1 $.

The stochastic process can be called an observable Markovmodel. Now, let us consider the problem of a simple 4-state Markov model of weather. We assume that once a day (e.g., at noon), the weather is observed as being one of the following:

• State $1$: snow
• State $2$: rain
• State $3$: cloudy
• State $4$: sunny

The matrix $A$ of state transition probabilities is:

$A = {a_{ij}}= \begin{Bmatrix} a_{11}& a_{12}& a_{13}&a_{14} \\
a_{21}&a_{22}&a_{23}&a_{24} \\
a_{31}&a_{32}&a_{33}&a_{34} \\
a_{41}&a_{42}&a_{43}&a_{44}
\end{Bmatrix}$

Given the model, several interestingquestions about weather patterns over time can be asked (and answered). We canask the question: what is the probability (according to the given model) thatthe weather for the next $k$ days willbe? Another interesting question we can ask: given that the model is in a knownstate, what is the expected number of consecutive days to stay in that state?Let us define the observation sequence $O$ as O = \left \\{ s\_{1}, s\_{2}, s\_{3}, ... , s\_{k} \right \\}, and the probability of the observation sequence $O$ given the model is defined as $p(O|model)$.

Also, let the expected number of consecutive days to stayin state $i$ be $E\_{i}$. Assume that the initial state probabilities $p[s\_{1} = i] = 1, 1 \leq i \leq N$. Both $p(O|model)$ and $E\_{i}$ are real numbers.

Line $1$~$4$ for the state transition probabilities. Line $5$ for the observation sequence $O\_{1}$, and line $6$ for the observation sequence $O\_{2}$. Line $7$ and line $8$ for the states of interest to find the expected number of consecutive days to stay in these states.

Line $1$: $a\_{11}\ a\_{12}\ a\_{13}\ a\_{14}$
Line $2$: $a\_{21}\ a\_{22}\ a\_{23}\ a\_{34}$
Line $3$: $a\_{31}\ a\_{32}\ a\_{33}\ a\_{34}$
Line $4$: $a\_{41}\ a\_{42}\ a\_{43}\ a\_{44}$
Line $5$: $s\_{1}\ s\_{2}\ s\_{3}\ ...\ s\_{k}$
Line $6$: $s\_{1}\ s\_{2}\ s\_{3}\ ...\ s\_{l}$
Line $7$: $i$
Line $8$: $j$

Line $1$ and line $2$ are used to show the probabilities of the observation sequences $O\_{1}$ and $O\_{2}$ respectively. Line $3$ and line $4$ are for the expected number of consecutive days to stay in states $i$ and $j$ respectively. Line $1$: $p[O\_{1} | model]$ Line $2$: $p[O\_{2} | model]$ Line $3$: $E\_{i}$ Line $4$: $E\_{j}$ Please be reminded that the floating number should accurate to $10^{-8}$.