Markov Chains

A model that tries to predict the next future state given one future state (one in the case of 1st-order Markov models)

${\pi }_i=P(X_1=i)$

• Called the initial probability

$q_{ij}=P(X_{t+t}=i|X_t=j)$

• Called the transition probability
• The probability that the future state is $i$ given the current state is $j$

$$\pi =\left[\begin{array}{c}{\pi }_1\\ ⋮\\ {\pi }_K\end{array}\right]$$ $$Q=\left[\begin{array}{ccc}{q}_{11}& \dots & q_{1K}\end{array}\right]$$

$p_t(i)=P(X_t=i)=\sum _j{p}_{t-1}(j)q_{ij}=$

$\hat{\theta }=$

Time Complexity

Training

• Viterbi Algorithm