Here's one way (convert each set of transition percentages to
a running sum up to one):
import random
class SingleStateMarkov(object):
def __init__(self, probabilities, initial=None):
self._states = states = sorted(probabilities)
self._fromstate = dict([(name, n) for n, name in
enumerate(states)])
self._all_states = set(states)
self.transition = dict()
for name, row in probabilities.iteritems():
self.transition[name] = self.add_transitions(name, row)
if initial is None:
initial = self._states[0]
elif initial not in self._all_states:
raise ValueError('Invalid initial state %s' % initial)
self.state = initial
def add_transitions(self, name, row):
if set(row) - self._all_states:
raise ValueError('%s: moves to unknown states %s' % (
name, set(row) - self._all_states))
if min(row.values()) < 0:
raise ValueError('%s: bad odds for states %s' % (name,
[nm for nm,odds in row.iteritems() if odds < 0]))
total = float(sum(row.values())) # Sum of the odds.
if total <= 0:
raise ValueError('%s: No Transitions allowed' % name)
running_total = 0.
cumulative = []
for name in self._states:
running_total += row.get(name, 0.0)
cumulative.append(running_total / total)
return cumulative
def move(self):
v = random.random()
for index, entry in enumerate(self.transition[self.state]):
if v <= entry:
break
self.state = self._states[index]
return self.state
class MultiStateMarkov(SingleStateMarkov):
def __init__(self, probabilities, initial=None, order=2):
if [key for key in probabilities if len(key) != order]:
raise ValueError('State keys wrong size: %s' %
[key for key in probabilities
if len(key) != order])
self._all_states = set()
for i in range(order):
self._all_states |= set(key[i] for key in probabilities)
self._states = states = sorted(self._all_states)
self._fromstate = dict([(name, n) for n, name in
enumerate(states)])
self.transition = dict()
for key, row in probabilities.iteritems():
self.transition[key] = self.add_transitions(key, row)
if initial is None:
initial = (self._states[0],) * order
elif len(initial) != order or set(initial)-self._all_states:
raise ValueError('Invalid initial state %s' % initial)
self.state = initial
def move(self):
v = random.random()
for index, entry in enumerate(self.transition[self.state]):
if v <= entry:
break
state = self._states[index]
self.state = self.state[1:] + (state,)
return state
c = SingleStateMarkov(dict(A=dict(A=20, B=50, C=30),
B=dict(A=35, B=25, C=40),
C=dict(A=70, B=14, C=16)))
d = MultiStateMarkov(dict([(('A', 'A'), dict(A=15, B=55, C=30)),
(('A', 'B'), dict(A=20, B=45, C=35)),
(('A', 'C'), dict(A=60, B=30, C=10)),
(('B', 'A'), dict(A=35, B=25, C=40)),
(('B', 'B'), dict(A=49, B=48, C=3)),
(('B', 'C'), dict(A=60, B=20, C=20)),
(('C', 'A'), dict(A=5, B=75, C=20)),
(('C', 'B'), dict(A=0, B=90, C=10)),
(('C', 'C'), dict(A=70, B=14, C=16))]))
--Scott David Daniels
sc***********@acm.org
