# Odds of X occurrences in a row given Y trials (A coin flip problem)

I 'm looking to find a general formula for the following problem:

The events:

• Let each event have two possible outcomes (e.g. success and failure)
• The events are independent

Scenario:

• Let the number of trials be Y
• Let the number of successes be N

Here's the tough part:

Over Y trials, what is the probability of there being X successes in a row given that the total number of successes is N?

I believe this is only a partial solution for the case when $N<2X$.

Define $A_i$ to be the set of all sequences of $Y$ events with $N$ successes such that at least $X$ successes occur consecutively beginning at position $i$ in the sequence, and no string of $X$ successes is to begin before position $i$. For example, if $Y=4$, $N=3$, $X=2$, and successes are denoted by a $1$ while failures are denoted by a $0$, then $A_1=\left\{1101,1110\right\}$, $A_2=\left\{0111\right\}$, and $A_3=\left\{1011\right\}$. The index $i$ runs from $1$ to $Y-X+1$ because we require at least $X$ spots to contain the string of $X$ successes.

Now let's count the size of each of the $A_i$, $i=1,\ldots,Y-X+1$, for generic $Y$, $N$, and $X$ with the constraint that $N<2X$.

• $|A_1|=\binom{Y-X}{N-X}$ because the string of $X$ successes begins in the first position and runs until position $X$, and beyond that we don't care about the ordering of the remaining successes and the failures.
• Now for all $i\in\left\{2,\ldots,Y-X+1\right\}$, $|A_i|=\binom{Y-X-1}{N-X}$. We can think about these sequences in the following way: begin the $X$ successes at position $i$ and force a failure in position $i-1$ so the string of $X$ successes cannot start before position $i$. Now we don't care about the ordering of the remaining successes and failures in all other positions, so we can place them by simply choosing where in the remaining $Y-X-1$ spots the remaining $N-X$ successes will go. There are $Y-X+1-1=Y-X$ of these $A_i$, $i\in\left\{2,\ldots,Y-X+1\right\}$.

This gives a total of $$\sum_{i=1}^{Y-X+1}|A_i|=\binom{Y-X}{N-X}+(Y-X)\binom{Y-X-1}{N-X}$$ sequences with a sequence of at least $X$ successes. The total number of sequences of length $Y$ with $N$ successes is $\binom{Y}{N}$. Thus, the probability of a sequence of length $Y$ with $N<2X$ successes containing at least $X$ consecutive successes is $$\frac{\binom{Y-X}{N-X}+(Y-X)\binom{Y-X-1}{N-X}}{\binom{Y}{N}}$$

In R, a simple function to calculate these probabilities would be the following.

f <- function(params) {
# params is a numeric vector of length 3 with Y, the length of the
# sequence, in the first position, N, the number of successes in the
# sequence, in the second position, and X, the minimum number of
# consecutive successes, in the third position.

Y <- params
N <- params
X <- params

num <- choose(Y-X,N-X) + (Y-X) * choose(Y-X-1,N-X)
den <- choose(Y,N)
return(num/den)
}

• +1: This agrees with my recursive solution for smaller values of $N$, but breaks down as $N$ gets large. – Neil G May 9 '12 at 6:33

This solution works for all values of $n$.

You can define a recursive formula for the probability of $x$ consecutive successes, $y$ trials, and $n$ successes: \begin{align} f(x,y,n) &= g(x, x, y, n) \end{align} where \begin{align} g(x,x',y,n) &= \begin{cases} 1 & \text{if }x = 0 \\ \frac{n}{y}g(x-1,x',y-1,n-1)+\frac{y-n}yf(x',y-1,n) & \text{if }0 < x \le n \le y \\ 0 & \text{otherwise.} \end{cases} \end{align}

The $x'$ parameter accepted by $g$ is the number of consecutive successes required. The $x$ parameter is the length of a block of consecutive successes required if the block starts at the first position. So, if $x$ is zero, we have already achieved our goal and the probability is one. If it's not true that $0 < x \le n \le y$ we cannot achieve our goal, so we return zero. In the final case, with probability $n/y$, we observe a success, so we need one fewer success in a row to make it and so $x$ decreases; however, $x'$ does not decrease because on a failure, we would still need $x'$ to achieve our goal. The case of a failure has $\frac{y-n}y$ probability, and sets us all the way back to $x=x'$. In either case $y$ is decremented, but $n$ only decreases in the case of a success.

#!/usr/bin/env python
from tools.decorator import memoized
from fractions import Fraction

@memoized
def g(x, x_prime, y, n):
if x == 0:
return Fraction(1)
elif 0 < x <= n <= y:
return (Fraction(n, y) * g(x - 1, x_prime, y - 1, n - 1) +
Fraction(y - n, y) * f(x_prime, y - 1, n))
else:
return Fraction(0)

def f(x, y, n):
return g(x, x, y, n)

print(f(30, 100, 97))


prints 104/105

• Would you mind explaining the recursive formula? Even a short explanation about the $g(x,x',y,n)$ function would be helpful. – assumednormal May 9 '12 at 22:07
• @Max: Please let me know if more explanation would be helpful. – Neil G May 9 '12 at 23:53

If p is the probability of success the probability of X successes in a row is p^X. For your problem these X successes can occur in many different slots in the sequence. So you have to multiply by the number of ways you can pick X consecutive slots out of the total of Y available slots with the additional requirement that N-X successes occur in the remaining Y-X slots.

• That's certainly the right idea, but you have to be very careful not to over-count the number of sequences with $Y$ events, $N$ successes, and $X$ successes in a row. For example, suppose the $X$ consecutive successes begin on the first event and another success follows on event $X+1$. That will also be counted when considering a success on the first event followed by the $X$ consecutive successes beginning on the second event. – assumednormal May 6 '12 at 15:26
• And another potential trap to consider is the case when $N\geq2X$. – assumednormal May 6 '12 at 15:35
• @Max I read the question differently from you. It asks what is the probability of there being X successes in a row given that the total number of successes is N? I interpret that as at least X in a row while you seem to interpret it as exact X in a row and no more. – Michael R. Chernick May 6 '12 at 16:36
• My comments are just warnings that double-counting specific sequences can easily happen if you think of just placing the $X$ successes at some point in the $Y$ trials regardless of the remaining successes. Let's say $Y=5$, $N=4$, and $X=2$. Using your suggestion, $11011$ (with $1$ being success and $0$ being failure) would be counted twice. This is because we can begin the $X$ successes in the first position, or we can begin the $X$ successes in the fourth position. Either way, we can place the remaining $N-X=2$ successes together beginning in the fourth or first position, respectively. – assumednormal May 6 '12 at 18:10
• And my suggestion is to specify where in the sequence the $X$ successes begin, and it doesn't matter what happens beyond that. So, for example, you could have a string of more than $X$ successes, so long as it occurs after the $X$ successes that we must observe. – assumednormal May 6 '12 at 18:14

This is a difficult problem. Let's start with the N condition. As often a possible way to simplify the problem is to instead calculate the chance of never X occurences in a row given Y trials.

Note that for $Y < X$ you will never have X occurences, much less in a row, so the probability here is 1. Let us denote the probability that you do NOT have X occurences in a row given Y trials as $P(X|Y)$.

Since we assume a coin, let's call the two outcome H and T. T are our successes. Let us shorten a repetion of n heads or tails as H[n] respectively T[n]. Let us furthermore denote the chance of T as p. Look at the cases which do not contain a T[X]. They have the following possible starts (first few events): $$H \\ TH \\ TH \\ \vdots \\ T[X-1]H$$

Note that they seperate the room of possible outcomes, it's not possible for a series to start with two of those options, they are mutually exclusive. So we can write $$P(X|Y) = \sum_{i=0}^{X-1} P(\text{series starts with T[i]H and no T[X] in rest of series)}$$ because of independence of the individual events we get $$P(X|Y) = \sum_{i=0}^{X-1} P(\text{series starts with T[i]H})P(\text{no T[X] in rest of series}).$$

Note that the rest of the series depends on i; it has length $Y-i-1$. So finally we get

$$P(X|Y) = \sum_{i=0}^{X-1} (1-p)p^{i-1}P(X|Y-1-i).$$

This is a well-defined recurrent formula given $P(X|Y) = 1$ for $Y < X$. While there is (as far as I know) no general closed form, it is easy enough to calculate. Remember that the chance you seek is actually $1-P(X|Y)$.

Now if could still condition on the total number of sucesses... This could probably be carried along with the Y. I will try to complete that part later. The number of reamining sucesses in the recurrence part of the formula will decrease by i but the inversion part will be tricky...

Okay, let's give this a try. We now look at $P(X,N|Y)$. It stands for the probability of having exactly n successes and no chains of length X or more in a sequence of length Y.

We still get $$P(X,N|Y) = \sum_{i=0}^{X-1} (1-p)p^{i-1}P(X,N-i|Y-1-i).$$

Do we have enough boundary conditions on $P(X,N|Y)$ to make this work? We do know that $P(X,N|Y)$ is $\binom{Y}{N}p^N(1-p)^{N-Y}$ for $Y < X$ and $N \leq Y$. It's also 0 if $Y=N$ AND $Y \geq X$.Is that enough? Let's look at an easy example $X=2$,$Y=4$,$N=3$,$p=0.5$.

We get

$$P(2,3|4) = (1-p)P(2,3|3)+p(1-p)P(2,2|2)$$

So we get $$(1-p)0+p(1-p)0=0.$$

Works in this case.

Let's try $N=4$, $Y=5$, $X=3$, $p=0.5$.

$$P(3,4|5) = (1-p)P(3,4|4)+p(1-p)P(3,3|3)+p^2(1-p)P(3,2|2)$$

The first two terms are zero (see above), so what remains is $2^{-5}\binom{2}{2}$.

P(exactly N sucesses) = P(exactly N successes + no chains of length X) + P(exactly N successes + chains of length X). The left hand is simply given by the binomial theorem.

....so the right-most probability: $$\frac{5}{2^5} = \frac{1}{2^5}+P(\text{chain of length X exists},N|Y)$$ so $$P(\text{chain of length X exists},N|Y)=\frac{4}{2^5}.$$ Now just divide by the probability of exactly N successes to get the conditional probability of $\frac{4}{5}$, which is the correct answer.

I think the recurrency and the formula is well defined, but I am not 100% certain at this point.

R-Version, which after some bug-fixes seems to agree with Max, but might me more general, if slow. chance2 gives the final result. I have also tested the results of the function and compared it to simulation. It seems to provide the correct answer. Caching the values in a two-dimensional array for L,N could make the program relatively fast.

chance <- function(x,L,N)
{
print(c(x,L,N))
if (L < 0) return(0)
if (N <0) return(0)
if (L < N) return(0)
if (L == 0)
{
if (N!=0) return(0)
return(1)
}
if (L < x)
{
return(0.5^(L)*choose(L,N))
}
result <- 0
for (i in 0:(x-1))
{
result <- result + 0.5^(i+1)*chance(x,L-i-1,N-i)
}

return(result)
}

chance2 <- function(x,L,N)
{
result1 <- chance(x,L,N)
left.hand <- choose(L,N)*(0.5)^L
result2 <- (left.hand-result1)/left.hand
return(result2)
}