Run

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

$$P_t(n)=P_t(n-1)+2^{-t}[1-P_t(n-t)],$$ (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}},$$ (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),$$ (3)

where

$$e_t(m,k)\equiv\cases{ 1 & if $m=0$\ and $0\leq k<t$\cr -1 & if $m=t$\ and $0\leq k<t$\cr 0 & otherwise.\cr}$$ (4)

Another recurrence which has only a fixed number of terms is given by

$C_t(m,k)=C_t(m-1,k)+C_t(m,k-1)-C_t(m-t,k-1)$
$-C_t(m-1,k-t)+C_t(m-t,k-t)+e_t^*(m,k),\quad$	(5)

where

$$e_t^*(m,k)\equiv\cases{ 1 & if $(m,k)=(0,0)$\ or $(t,t)$\cr -1 & if $(m,k)=(0,t)$\ or $(t,0)$\cr 0 & otherwise\cr}$$ (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$$ (7)

is the expected number of runs $\geq R$. The longest expected run is therefore given by

$$R=\log_{1/p} [n(1-p)]$$ (8)

(Gordon et al. 1986, Schilling 1990). Given $m$ 0s and $n$ 1s, the number of possible arrangements with $u$ runs is

$$f_u=\cases{ 2{m-1\choose k-1} {n-1\choose k-1} & $u\equiv 2... ...se k-2}+{m-1\choose k-2} {n-1\choose k-1} & $u\equiv 2k+1$\cr}$$ (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}}.$$ (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},$$ (11)

where $(a)_n$ is the Pochhammer Symbol. For $m>10$, $u$ has an approximately Normal Distribution with Mean and Variance

$$\mu_u = 1+{2mn\over m+n}$$ (12)

$${\sigma_u}^2 = {2mn(2mn-m-n)\over (m+n)^2(m+n-1)}.$$ (13)

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

References

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.