First, build an HMM simulator so that you have a source of ``observations''
and a target to compare against. To do this, we will build an MM, and then we
will proceed to ``hide'' it from the HMM trainer. I suggest creating code
that can manage *N* states, numbered
0, ... *N* - 1, and
*M* different kinds of observations, numbered
0, ... *M* - 1,
and which produces observations of length *T*. In other words, *N*,
*M* and *T* are parameters of your Markov model. Initially, I suggest
that we attempt to train models where *N* = 3, *M* = 4 and *T* varies
from 3 to 5. Here is an example.

If this above model splits its transition probabilities 3:1 in favor of going ``right'', then the transition probability matrix is as follows.

a_{i, j} |
0 | 1 | 2 |

0 | 0.25 | 0.75 | 0 |

1 | 0 | 0.25 | 0.75 |

2 | 0 | 0 | 1.0 |

Let's assume that this model always starts in state 0.

0 | 1 | 2 | |

1.0 | 0 | 0 |

Finally, there are four observations, 0, 1, 2 and 3, with the following probabilities per state.

b_{i}(k) |
0 | 1 | 2 | 3 |

0 | 0.5 | 0.5 | 0 | 0 |

1 | 0 | 0.5 | 0.5 | 0 |

2 | 0 | 0 | 0.5 | 0.5 |

To build the MM, use a *Monte* *Carlo* simulation. First, you'll need
a random number generator. In C, use the random() function (see manual page),
seeded by srandom() using the data from a call to time() (see manual page).^{1} Once random() is seeded, you can easily define a function randomint(lb, ub)
that returns a random integer *x* in the range lb *x* <ub.^{2}

` int randomint (int lb, int ub) {`
` return lb + random() % (ub - lb);`
` }`

You can also define a function that returns a random
floating point number *x* in the range
0 *x* 1.

` double randomreal () {`
` return ((double) random()) / RAND_MAX;`
` }`

To generate a random choice over a given distribution, simply do the following. Assume we wish to generate the initial state according to .

- Generate a random number
*x*such that 0*x*1. -
*i*0. -
*x**x*- - While
*i*<*N*and*x*> 0 do -
*i**i*+ 1 -
*x**x*- - End while loop.
- If
*i*<*N*then*i*is the randomly selected state else*error*(sum of probabilities is < 1).

- select the initial state of the HMM,
- select the next state, and
- select the observation that appears in each state.

function newsequence (
*N*, *M*,, *a*, *b*, *T*)

- Create an HMM according to the given model.
- Let
*s*be the initial state, chosen according to . - Let
*O*be the empty sequence of observations. - While
*length*(*O*) <*T*do - Let
*o*be the observation for current state*s*, chosen according to*b*_{s}. -
*O*=*concatenate*(*O*,*o*) (i.e., add*o*to the end of*O*). -
*s*next state according to*a*_{s}. - End while loop.
- Return
*O*.