6
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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)
}
$\endgroup$
  • $\begingroup$ +1: This agrees with my recursive solution for smaller values of $N$, but breaks down as $N$ gets large. $\endgroup$ – Neil G May 9 '12 at 6:33
1
$\begingroup$

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

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – assumednormal May 6 '12 at 15:26
  • $\begingroup$ And another potential trap to consider is the case when $N\geq2X$. $\endgroup$ – assumednormal May 6 '12 at 15:35
  • $\begingroup$ @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. $\endgroup$ – Michael R. Chernick May 6 '12 at 16:36
  • 3
    $\begingroup$ 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. $\endgroup$ – assumednormal May 6 '12 at 18:10
  • $\begingroup$ 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. $\endgroup$ – assumednormal May 6 '12 at 18:14
0
$\begingroup$

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)
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.