A run is a sequence of more than one consecutive identical outcomes, also known as a clump.

Let be the probability that a run of or more consecutive heads appears in independent tosses of a coin (i.e., Bernoulli trials). This is equivalent to repeated picking from an urn containing two distinguishable objects with replacement after each pick. Let the probability of obtaining a head be . Then there is a beautiful formula for given in terms of the coefficients of the generating function

(1)

(Feller 1968, 2nd ed. p. 300). Then

(2)

The following table gives the triangle of numbers for , 2, ... and , 2, ..., (Sloane's A050227).

Sloane	A000225	A008466	A050231	A050233
	1	2	3	4	5	6	7	8
1	1	0	0	0	0	0	0	0
2	3	1	0	0	0	0	0	0
3	7	3	1	0	0	0	0	0
4	15	8	3	1	0	0	0	0
5	31	19	8	3	1	0	0	0
6	63	43	20	8	3	1	0	0
7	127	94	47	20	8	3	1	0
8	255	201	107	48	20	8	3	1

The special case gives the sequence

(3)

where is a Fibonacci number. Similarly, the probability that no consecutive tails will occur in tosses is given by , where is a Fibonacci k-step number.

Feller (1968, pp. 278-279) proved that for ,

(4)

where

			(5)
			(6)

(Sloane's A086253) is the positive root of the above polynomial and

			(7)
			(8)
			(9)

(Sloane's A086254) is the positive root of the above polynomial. The corresponding constants for a run of heads are , the smallest positive root of

(10)

and

(11)

These are modified for unfair coins with and to , the smallest positive root of

(12)

and

(13)

(Feller 1968, pp. 322-325).

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

(14)

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

(15)

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

(16)

for an integer, where is a binomial coefficient (Johnson and Kotz 1968, p. 268). Then

(17)

Now instead consider picking of objects without replacement from a collection of containing indistinguishable objects of one type and indistinguishable objects of another. Let denote the number of permutations of these objects in which no -run occurs. For example, there are 6 permutations of two objects of type and two of type . Of these, , , , and contain runs of length two, so . In general, the probability that an -run does occur is given by

(18)

where is a binomial coefficient. Bloom (1996) gives the following recurrence sequence for ,

(19)

where for or negative and

(20)

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

(21)

where

(22)

(Goulden and Jackson 1983, Bloom 1996).

These formulas can be used to calculate the probability of obtaining a run of cards of the same color in a deck of 52 cards. For , 2, ..., this yields the sequence 1, 247959266474051/247959266474052, ... (Sloane's A086439 and A086440). Normalizing by multiplying by gives 495918532948104, 495918532948102, 495891608417946, 483007233529142, ... (Sloane's A086438). The result

(23)

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

Bloom (1996) gives the expected number of noncontiguous -runs (i.e., split the sequence into maximal clumps of the same value and count the number of such clumps of length ) in a sequence of 0s and 1s as

(24)

where is the falling factorial. For , has an approximately normal distribution with mean and variance

			(25)
			(26)

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.

Feller, W. An Introduction to Probability Theory and Its Application, Vol. 1, 3rd ed. New York: Wiley, 1968.

Finch, S. R. "Feller's Coin Tossing Constants." §5.11 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 339-342, 2003.

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 Papastavridis, 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.

Johnson, N. and Kotz, S. Discrete Distributions. New York: Wiley, 1968.

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.

Sloane, N. J. A. Sequences A000225/M2655, A008466, A050227, A050231, A050232, A050233, A086253, A086254, A086438, A086439, and A086440 in "The On-Line Encyclopedia of Integer Sequences."

CITE THIS AS:

Weisstein, Eric W. "Run." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Run.html