# Markov models

## Markov chains

### Estimating the Markov chain stochastic matrix

#### Introduction

Given a sequence: \(x_1,...x_n\).

The likelihood is:

\(L=\prod_{i=2}^n p_{x_{i-1},x_i}\)

If there are \(k\) states we can rewrite this as:

\(L=prod_{i=1}^k\prod_{j=1}^k n_{ij}p_{ij}\)

Where \(p_{ij}\) is the chance of moving from state \(i\) to state \(j\), and \(n_{ij}\) is the number of transtions between \(i\) and \(j\).

The log likelhood is:

\(\ln L=\sum_{i=1}^k\sum_{j=1}^kn_{ij}\ln p_{ij}\)

#### Constrained optimisation

Not all parameters are free. All probabilities must sum to \(1\).

\(\ln L=\sum_{i=1}^k\sum_{j=1}^kn_{ij}\ln p_{ij}-sum_{i=1}\lambda_i (\sum_{j=1}p_{ij}-1)\)

This gives us:

\(\hat p_{ij}=\dfrac{n_{ij}}{\sum_k n_{ik}}\)

## Hidden Markov Models (HMMs)

### Defining Hidden Markov Models (HMMs)

We donâ€™t see state

Each state produces a visible output. this output is drawn from a distribution for each state.

We observe a sequence of outputs, not states.

### Estimating HMMs with the Viterbi algorithm

Assume we know transition matrix. and starting probls

Given we observe sequence of outputs, what were most likely actual paths?

Virbiti returns this

### Estimating HMMs with the forward algorithm

Given we have observed outputs, what is the chance of being in a certain state at a certain time?

### Estimating HMMs with the forward-backward algorithm

We calculate state x at time t given all obs.

### Baum-Welch algorithm

## Kalman filters

### Kalman filters

## Dynamic Bayesian Network

### Dynamic Bayesian Network