## Description

This article is from the Puzzles FAQ,
by Chris Cole chris@questrel.questrel.com and Matthew Daly
mwdaly@pobox.com with numerous contributions by others.

# 403 probability/flips/once.in.run.p

What are the odds that a run of one H or T (i.e., THT or HTH) will occur

in n flips of a fair coin?

probability/flips/once.in.run.s

References:

John P. Robinson, Transition Count and Syndrome are Uncorrelated, IEEE

Transactions on Information Theory, Jan 1988.

First we define a function or enumerator P(n,k) as the number of length

"n" sequences that generate "k" successes. For example,

P(4,1)= 4 (HHTH, HTHH, TTHT, and THTT are 4 possible length 4 sequences).

I derived two generating functions g(x) and h(x) in order to enumerate

P(n,k), they are compactly represented by the following matrix

polynomial.

_ _ _ _ _ _
| g(x) | | 1 1 | (n-3) | 4 |
| | = | | | |
| h(x) | | 1 x | |2+2x |
|_ _| |_ _| |_ _|

The above is expressed as matrix generating function. It can be shown

that P(n,k) is the coefficient of the x^k in the polynomial

(g(x)+h(x)).

For example, if n=4 we get (g(x)+h(x)) from the matrix generating

function as (10+4x+2x^2). Clearly, P(4,1) (coefficient of x) is 4 and

P(4,2)=2 ( There are two such sequences THTH, and HTHT).

We can show that

mean(k) = (n-2)/4 and sd= square_root(5n-12)/4

We need to generate "n" samples. This can be done by using sequences of length

(n+2). Then our new statistics would be

mean = n/4

sd = square_root(5n-2)/4

Similar approach can be followed for higher dimensional cases.

Continue to: