info prev up next book cdrom email home


A run is a sequence of more than one consecutive identical outcomes, also known as a Clump. Given $n$ Bernoulli Trials (say, in the form of Coin Tossings), the probability $P_t(n)$ of a run of $t$ consecutive heads or tails is given by the Recurrence Relation

\end{displaymath} (1)

where $P_t(n)=0$ for $n<t$ and $P_t(t)=2^{1-t}$ (Bloom 1996).

Let $C_t(m,k)$ denote the number of sequences of $m$ indistinguishable objects of type $A$ and $k$ indistinguishable objects of type $B$ in which no $t$-run occurs. The probability that a $t$-run does occur is then given by

P_t(m,k)=1-{C_t(m,k)\over{m+k\choose k}},
\end{displaymath} (2)

where ${a\choose b}$ is a Binomial Coefficient. Bloom (1996) gives the following recurrence sequence for $C_t(m,k)$,

C_t(m,k)=\sum_{i=0}^{t-1} C_t(m-1,k-i)-\sum_{i=1}^{t-1}C_t(m-t,k-i)+e_t(m,k),
\end{displaymath} (3)

1 & if $m=0$\ and $0\leq k<t$\cr
-1 & if $m=t$\ and $0\leq k<t$\cr
0 & otherwise.\cr}
\end{displaymath} (4)

Another recurrence which has only a fixed number of terms is given by
$ -C_t(m-1,k-t)+C_t(m-t,k-t)+e_t^*(m,k),\quad$ (5)
1 & if $(m,k)=(0,0)$\ or $(t,t)$\cr
-1 & if $(m,k)=(0,t)$\ or $(t,0)$\cr
0 & otherwise\cr}
\end{displaymath} (6)

(Goulden and Jackson 1983, Bloom 1996). These formulas disprove the assertion of Gardner (1982) that ``there will almost always be a clump of six or seven Cards of the same color'' in a normal deck of cards by giving $P_6(26,26)=0.46424$.

Given $n$ Bernoulli Trials with a probability of success (heads) $p$, the expected number of tails is $n(1-p)$, so the expected number of tail runs $\geq 1$ is $\approx n(1-p)p$. Continuing,

N_R = n(1-p)p^R
\end{displaymath} (7)

is the expected number of runs $\geq R$. The longest expected run is therefore given by
R=\log_{1/p} [n(1-p)]
\end{displaymath} (8)

(Gordon et al. 1986, Schilling 1990). Given $m$ 0s and $n$ 1s, the number of possible arrangements with $u$ runs is
2{m-1\choose k-1} {n-1\choose k-1} & $u\equiv 2... k-2}+{m-1\choose k-2} {n-1\choose k-1} & $u\equiv 2k+1$\cr}
\end{displaymath} (9)

for $k$ an Integer, where ${n\choose k}$ is a Binomial Coefficient. Then
P(u\leq u') = \sum_{u=2}^{u'} {f_u\over {m+n\choose m}}.
\end{displaymath} (10)

Bloom (1996) gives the expected number of noncontiguous $t$-runs in a sequence of $m$ 0s and $n$ 1s as

E(n,m,t)={(m+1)(n)_t+(n+1)(m)_t\over (m+n)_t},
\end{displaymath} (11)

where $(a)_n$ is the Pochhammer Symbol. For $m>10$, $u$ has an approximately Normal Distribution with Mean and Variance
$\displaystyle \mu_u$ $\textstyle =$ $\displaystyle 1+{2mn\over m+n}$ (12)
$\displaystyle {\sigma_u}^2$ $\textstyle =$ $\displaystyle {2mn(2mn-m-n)\over (m+n)^2(m+n-1)}.$ (13)

See also Coin Tossing, Eulerian Number, Permutation, s-Run


Bloom, D. M. ``Probabilities of Clumps in a Binary Sequence (and How to Evaluate Them Without Knowing a Lot).'' Math. Mag. 69, 366-372, 1996.

Gardner, M. Aha! Gotcha: Paradoxes to Puzzle and Delight. New York: W. H. Freeman, p. 124, 1982.

Godbole, A. P. ``On Hypergeometric and Related Distributions of Order $k$.'' Commun. Stat.: Th. and Meth. 19, 1291-1301, 1990.

Godbole, A. P. and Papastavnidis, G. (Eds.). Runs and Patterns in Probability: Selected Papers. New York: Kluwer, 1994.

Gordon, L.; Schilling, M. F.; and Waterman, M. S. ``An Extreme Value Theory for Long Head Runs.'' Prob. Th. and Related Fields 72, 279-287, 1986.

Goulden, I. P. and Jackson, D. M. Combinatorial Enumeration. New York: Wiley, 1983.

Mood, A. M. ``The Distribution Theory of Runs.'' Ann. Math. Statistics 11, 367-392, 1940.

Philippou, A. N. and Makri, F. S. ``Successes, Runs, and Longest Runs.'' Stat. Prob. Let. 4, 211-215, 1986.

Schilling, M. F. ``The Longest Run of Heads.'' Coll. Math. J. 21, 196-207, 1990.

Schuster, E. F. In Runs and Patterns in Probability: Selected Papers (Ed. A. P. Godbole and S. Papastavridis). Boston, MA: Kluwer, pp. 91-111, 1994.

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein