## Run

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

 (1)

where for and (Bloom 1996).

Let denote the number of sequences of indistinguishable objects of type and indistinguishable objects of type in which no -run occurs. The probability that a -run does occur is then given by

 (2)

where is a Binomial Coefficient. Bloom (1996) gives the following recurrence sequence for ,

 (3)

where
 (4)

Another recurrence which has only a fixed number of terms is given by
 (5)
where
 (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 .

Given Bernoulli Trials with a probability of success (heads) , the expected number of tails is , so the expected number of tail runs is . Continuing,

 (7)

is the expected number of runs . The longest expected run is therefore given by
 (8)

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

for an Integer, where is a Binomial Coefficient. Then
 (10)

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

 (11)

where is the Pochhammer Symbol. For , has an approximately Normal Distribution with Mean and Variance
 (12) (13)

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 .'' 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.