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 [EMAIL PROTECTED] -- http://mail.python.org/mailman/listinfo/python-list