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

Question

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?

Answer 1

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[1]
  N <- params[2]
  X <- params[3]

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

Answer 2

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.

Answer 3

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

Answer 4

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 \\ T[1]H \\ T[2]H \\ \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}$.

You get your probability by

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)
}