Markov chains

A Markov chain is a discrete stochastic process with discrete states and discrete transformations between them. At each time instant the system is in one of the $N$ possible states, numbered from one to $N$. At regularly spaced discrete times, the system switches its state, possibly back to the same state. The initial state of the chain is denoted $M_1$ and the states after each time of change are $M_2, M_3, \ldots$. Standard first order Markov chain has the additional property that the probabilities of the future states depend only on the current state and not the ones before it [48]. Formally this means that

$$p(M_{t+1} = j \vert M_t = i, M_{t-1} = k, \ldots) = p(M_{t+1} = j \vert M_t = i) \quad \forall t,i,j,k.$$ (4.1)

This is called the Markov property of the chain.

Because of the Markov property, the complete probability distribution of the states of a Markov chain is defined by the initial distribution $\pi_i = p(M_1 = i)$ and the state transition probability matrix

$$a_{ij} = p(M_{t+1} = j \vert M_t = i),\quad 1 \le i, j \le N.$$ (4.2)

Let us denote $\boldsymbol{\pi} = ( \pi_i )$ and $\mathbf{A}= ( a_{ij} )$. In the general case the transition probabilities could be time dependent, i.e. $a_{ij} = a_{ij}(t)$, but in this thesis only the time independent case is considered.

This allows the evaluation of the probability of a sequence of states $\boldsymbol{M}= ( M_1, M_2, \ldots, M_T )$, given the model parameters $\boldsymbol{\theta}= (\mathbf{A}, \boldsymbol{\pi})$, as

$$p(\boldsymbol{M}\vert \boldsymbol{\theta}) = \pi_{M_1} \left[ \prod\limits_{t=1}^{T-1} a_{M_t M_{t+1}} \right].$$ (4.3)