Markov chain with extras?

[tiissa]

temp at mclift.fsnet.co.uk wrote:
> I think is more easy explained as two linked markov chains. So given
> one list the other can be generated.

'Given one list sounds' like an observation (and this sound like an 
order 2 hmm).
But I'm not sure what exactly you want to do with your markov chain. Do 
you want the probability distribution at each time step or some value ?
In this case, I'd do something like:

#### hmm.py
from random import random

def St_given_St1_St2_Ot(St1,St2,Ot):
	p0=0.5*St1*St2+0.25*St1+0.125*St2+0.0625
	return Ot and p0 or 1-p0

def decision(p):
	return (random()>p) and 1 or 0

def hmm(LO,LS):
	for ot in LO[2:]:
		p=St_given_St1_St2_Ot(LS[-1],LS[-2],ot)
		LS.append(decision(p))
	return LS

LO1=(-1,-1,1,0,0,0,1,1)
LS1=[1,0]
print ''.join(map(str,hmm(LO1,LS1)))

LO2=(0,)*50
LS2=[1,1]
print ''.join(map(str,hmm(LO2,LS2)))

LO3=(1,)*50
LS3=[1,1]
print ''.join(map(str,hmm(LO3,LS3)))
####


Which gives hours of fun looking at random numbers:

$ python hmm.py
10111101
11111111111111111111111111100000000000001000000000
11011011011011011011010110011011011011011010101101
$ python hmm.py
10101011
11111111111111111111111111111111000000000000000111
11011010011010100011010110110011001101101101011010
$ python hmm.py
10100011
11111111111111111111111111111111111111111111111111
11011010110011001101011011011101010110101101101011
$ python hmm.py
10111101
11101010000000000000000000000000000000000000000001
11011001101101011010110111010101010110110110011101
$ python hmm.py
10100011
11111111111111111111111111111111111111111111111111
11010110110110110011011010110011010011011011011010
$


Instead of generating the whole sequence, you can wrap it in an 
iterator. And the observations list can also be an iterator (generated 
with another chain if you like).

HTH