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, p. 300). Then
 |
(2)
|
The following table gives the triangle of numbers 
for 
, 2, ... and 
, 2, ..., 
(OEIS 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)
|
(OEIS A086253) is the positive root of the above polynomial and
 |  |  |
(7)
|
 |  |  |
(8)
|
 |  |  |
(9)
|
(OEIS 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
![R=log_(1/p)[n(1-p)]](/images/equations/Run/NumberedEquation10.svg) |
(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, ... (OEIS A086439 and A086440).
Normalizing by multiplying by 
gives 495918532948104, 495918532948102, 495891608417946, 483007233529142, ... (OEIS
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)
|
." Commun. Stat.: Th. and Meth. 19,
1291-1301, 1990.Godbole, A. P. and Papastavridis, G. (Eds.).