A run is a sequence forming a maximal nonempty block of 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), where 
is a positive integer and 
is a nonnegative integer.
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 formula for 
given in terms of the coefficients of the generating
function
 |
(1)
|
(Feller 1968, p. 300). Then
 |
(2)
|
The sum is zero when 
.
The following table gives the number triangle
of numbers 
for 
, 2, ... and 
, 2, ..., 
(OEIS A050227).
| Sloane | A000225 | A008466 | A050231 | A050232 | ||||
 | 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 and 
is a positive integer.
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)
|
For an unfair coin with 
and 
,
let 
be the unique positive root of the reduced polynomial
 |
(12)
|
and set
 |
(13)
|
Then ^(n+1)->beta_k^'](/images/equations/Run/Inline43.svg)
as 
(Feller 1968, pp. 322-325;
Finch 2003, p. 339). The unreduced polynomial 
always has
a root at 
. This root is removable
from the avoidance generating function, so
choosing the smallest positive root
of the unreduced polynomial fails to identify the
decay rate when 
.
Let 
be the expectation
value of the number of maximal head runs of length at least 
in 
independent Bernoulli trials, with 
, 
,
and 
a positive
integer. Counting possible starting positions gives
![N_R={p^R[1+(n-R)q] if n>=R; 0 if n<R.](/images/equations/Run/NumberedEquation9.svg) |
(14)
|
For fixed 
and 
as 
,
this is approximately 
.
The expectation value of the longest head run
has leading logarithmic growth
 |
(15)
|
where 
is big-O
notation and 
is fixed as 
(Gordon et al. 1986,
pp. 283-284; Schilling 1990, pp. 201-202).
For positive integers 
and 
,
choose uniformly from the arrangements of 
0s and 
1s. The number of such arrangements with 
runs is
 |
(16)
|
for 
a positive
integer, where 
is a binomial coefficient, taken to be zero
for 
or 
(Johnson and Kotz 1968, p. 268). Then
 |
(17)
|
Now consider drawing all 
objects without replacement in uniformly random order from a collection containing
indistinguishable
objects of one type and 
indistinguishable objects of another, where
and 
are nonnegative integers.
Let 
denote the number of permutations
of these objects in which no run of length at least 
occurs, where 
is a positive integer.
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 at least 
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 uniformly chosen sequence
of 
0s and 
1s, for nonnegative integers 
and 
with 
and 
, as
 |
(24)
|
where 
is the falling
factorial. For positive integers 
and 
,
the number of runs 
has exact mean and variance
 |  |  |
(25)
|
 |  |  |
(26)
|
As 
and 
tend to infinity with 
fixed strictly between 0 and 1, 
approaches a normal
distribution with mean 0 and variance
1 (Mood 1940, pp. 378-382).
."
Commun. Stat.: Th. and Meth. 19, 1291-1301, 1990.