Markov process representation

[Scott David Daniels]

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
scott.daniels at acm.org