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:
My Books
