Expected distribution of maximum runs in a sequence of coin flips

run_distribution_in_coin_tosses_2.py

# -*- coding: utf-8 -*-
"""
Let a[n; c, r] = number of sequences of n coin flips
                 ending with a streak of c heads or tails
                 and having a longest streak of r heads or tails.

We can show that 
    a[n; 1, r] = sum (i=1 to r) a[n-1; i, r]
and
    a[n; r, r] = a[n-1; r-1, r-1] + a[n-1; r-1, r]

If 1 < c < r then a[n; c, r] = a[n-1; c-1, r]


"""

def run_distribution(N):
    a = [[0]*N for _ in range(N)]
    a[0][0] = 2
    for n in range(2, N+1):
        b = [[0]*N for _ in range(N)]
        for r in range(n):
            b[r] = [sum(a[r])] + a[r][:r]
            if r > 0:
                b[r][r] += a[r-1][r-1]
        a = b
    return [sum(a[r][c] for c in range(r+1)) for r in range(N)]

if __name__ == '__main__':
    result = run_distribution(10)
    expected = [2, 176, 370, 254, 126, 56, 24, 10, 4, 2]
    print 'Result:   ', result
    print 'Expected: ', expected
    if result == expected:
        print 'Passed'
    else:
        print 'Failed'