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

## 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: