Coin Toss Run Probabilities.pdf

fn = probability the run occurs for the first time on toss n
fr−1 = 0
fr = pr
fn = qpr for r < n ≤ 2r
fn = q Pr
k=1 pk−1fn−k for n > 2r
F(z) = generating function for fn
F(z) = P∞
n=0 fnzn
F(z) =
przr(1−pz)
1−z+qprzr+1
µ = mean number of tosses required for a run
µ = F ′(1) = 1−pr
qpr
σ2 = variance of number of tosses required for a run
σ2 =
1
(qpr)2 −2r+1
qpr −p
q2
gn = conjugate probability (not a true probability)
gn = fn
pn
gr−1 = 0
gr = 1
gn = α(α + 1)n−r−1 for r < n ≤ 2r
gn = α Pr
k=1 gn−k for n > 2r
α = q
p = 1
p −1
G(z) = generating function for gn
F(z) = P∞
n=0 gnzn
G(z) =
zr(1−z)
1−(α+1)z+αzr+1
G(pz) = F(z)
Example: r = 1
G(z) =
z
1−αz
gn = αn−1 for n > 0
fn = pngn = pqn−1 = geometric distribution
Example: r = 2
G(z) =
z2
1−αz−αz2
g2 = 1
g3 = α
g4 = α(α + 1)
g5 = α2(α + 2)
g6 = α2(α2 + 3α + 1)
g7 = α3(α + 1)(α + 3)
g8 = α3(α3 + 5α2 + 6α + 1)
gn = αgn−1 + αgn−2
gn = zn−1
1
−zn−1
2
z1 = 1
2(α +
√
α2 + 4α)
z2 = 1
2(α −
√
α2 + 4α)
fn = pngn
Example: r = 3
G(z) =
z3
1−αz−αz2−αz3
g3 = 1
g4 = α
g5 = α(α + 1)
g6 = α(α + 1)2
g7 = α2(α2 + 3α + 3)
g8 = α2(α3 + 4α2 + 6α + 2)
gn = αgn−1 + αgn−2 + αgn−3
fn = pngn
Multiple Runs of r Consecutive Heads
f (k)
n
= probability the run occurs for the kth time on toss n
f (2)
n
= Pn−1
i=1 fifn−i
f (k)
n
= Pn−1
i=1 fif (k−1)
n−i
F (k)(z) = generating function for f (k)
n
F (k)(z) = P∞
n=0 f (k)
n zn
F (k)(z) = F k(z)
µ(k) = mean number of tosses required for k runs
µ(k) = kµ
see previous section for µ
(σ(k))2 = variance of number of tosses required for k runs
(σ(k))2 = kσ2
see previous section for σ2
g(k)
n
= f(k)
n
pn
G(k)(z) = generating function for g(k)
n
G(k)(z) = P∞
n=0 g(k)
n zn
G(k)(z) = Gk(z)
see previous section for G(z)
G(k)(pz) = F (k)(z)
Example: r = 1
G(k)(z) =
zk
(1−αz)k
g(k)
n
=
n−1
k−1


αn−k
f (k)
n
= png(k)
n
=
n−1
k−1


qn−kpk = negative binomial distribution
Example: r = 2
G(k)(z) =
z2k
(1−αz−αz2)k
g(k)
2k−1 = 0
g(k)
2k = 1
g(k)
2k+1 = kα
(n −2k)g(k)
n
= (n −k −1)αg(k)
n−1 + (n −2)αg(k)
n−2
f (k)
n
= png(k)
n
f (k)
2k−1 = 0
f (k)
2k = p2k
f (k)
2k+1 = kqp2k
(n −2k)f (k)
n
= (n −k −1)qf (k)
n−1 + (n −2)qpf (k)
n−2
For k = 2:
g(2)
3
= 0
g(2)
4
= 1
g(2)
5
= 2α
g(2)
6
= α(3α + 2)
g(2)
7
= α2(4α + 6)
g(2)
8
= α2(5α2 + 12α + 3)
For k = 3:
g(3)
5
= 0
g(3)
6
= 1
g(3)
7
= 3α
4
g(3)
8
= 3α(2α + 1)
g(3)
9
= 2α2(5α + 6)
g(3)
10 = 3α2(5α2 + 10α + 2)
For k = 4:
g(4)
7
= 0
g(4)
8
= 1
g(4)
9
= 4α
g(4)
10 = 2α(5α + 2)
g(4)
11 = 20α2(α + 1)
g(4)
12 = 5α2(7α2 + 12α + 2)
Run Probability for r Consecutive Heads
an = probability of a run on the nth toss
an + pan−1 + p2an−2 + · · · + pr−1an−r+1 = pr
an = fna0 + fn−1a1 + fn−2a2 + · · · + f1an−1
an = fn + f (2)
n
+ f (3)
n
+ · · ·
A(z) = generating function for an
A(z) = P∞
n=0 anzn
A(z) =
1
1−F(z)
A(z) −1 =
przr
(1−z)(1+pz+p2z2+···+pr−1zr−1)
A(z) −1 =
przr(1−pz)
(1−z)(1−przr)
A(z) =
1−z+qprzr+1
(1−z)(1−przr)
Let k = n mod r and µ = 1−pr
qpr then
µan = 1 + pn−r+1(1 −pr−1)/(1 −p)
k = 0
µan = 1 −pn−k
k ̸= 0