import numpy
# Find the transition matrix for the Markov Chain that encodes
# binary sequences which have no runs of k 0's or 1's in a row
def AddState(a,d):
    i = len(d)
    d[a] = i
def Transition(k):
    # The states are counters -- one series for 0 and one for 1
    # Plus an absorbing state if we generated a run of length k
    d = {}
    states = {}
    for i in range(1,k):
        AddState((0,i),states)
        AddState((1,i),states)
    AddState("absorb",states)
    transitions = []
    for i in range(1,k-1):
        for j in range(2):
            transitions.append(((states[j,i],states[j,i+1]),0.5))
            transitions.append(((states[j,i],states[1-j,1]),0.5))
    for j in range(2):
        transitions.append(((states[j,k-1],states["absorb"]),0.5))
        transitions.append(((states[j,k-1],states[1-j,1]),0.5))
    transitions.append(((states["absorb"],states["absorb"]),1.0))
    return Matrix(dict(transitions))