Probabilidad de X ocurrencias en una fila dada Y ensayos (un problema tirón de la moneda)

Question

Estoy buscando para encontrar una fórmula general para el siguiente problema:

Los eventos:

• Que cada evento tiene dos posibles resultados (éxito y fracaso)
• Los eventos son independientes

Escenario:

• Sea el número de ensayos Y
• Que el número de éxitos sea N

Aquí está la parte difícil:

Sobre ensayos Y, ¿cuál es la probabilidad de existencia de X éxitos en una fila teniendo en cuenta que el número total de éxitos es N?

Answer 1

Si p es la probabilidad de éxito la probabilidad de X éxitos en una fila es p ^ X. Para tu problema estos éxitos X pueden ocurrir en muchas ranuras diferentes en la secuencia. Así que tienes que multiplicar por el número de formas se puede elegir X ranuras consecutivas del total de espacios disponibles Y con la exigencia adicional de que éxitos de N X se producen en las restantes ranuras Y-X.

Answer 2

Este es un problema difícil. Vamos a empezar con el N de condición. Como a menudo una forma de simplificar el problema es que en lugar de calcular la probabilidad de que nunca X ocurrencias en una fila, Y los ensayos.

Tenga en cuenta que para $Y < X$ usted nunca tendrá X ocurrencias, y mucho menos en una fila, por lo que la probabilidad de aquí es de 1. Deje que nos indican la probabilidad de que usted NO tiene X ocurrencias en una fila, Y ensayos como $P(X|Y)$.

Desde que asumimos una moneda, vamos a llamar a los dos resultados H y T. T son nuestros éxitos. Permítanos acortar un repetion de n a cara o cruz, como H[n] T[n]. Deje que nosotros además de denotar la probabilidad de que T como p. Mira en los casos en que no se contienen a T[X]. Tienen las siguientes posibles comienza (primeros eventos): $$ H \\ T[1]H \\ T[2]H \\ \vdots \\ T[X-1]H $$

Se nota que le separada de la sala de posibles resultados, no es posible que una serie de empezar con dos de esas opciones, que son mutuamente excluyentes. Así que podemos escribir $$ P(X|Y) = \sum_{i=0}^{X-1} P(\text{serie comienza con $T[i]H$ e no $T[X]$ en el resto de la serie)} $$ debido a la independencia de cada uno de los eventos tenemos $$ P(X|Y) = \sum_{i=0}^{X-1} P(\text{serie comienza con $T[i]H$})P(\text{no $T[X]$ en el resto de la serie}). $$

Note that the rest of the series depends on i; it has length $S-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)$. Representa la probabilidad de tener exactamente n éxitos y sin cadenas de longitud X o más en una secuencia de longitud Y.

Todavía podemos obtener $$ 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 $S \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) $$

Así, obtenemos $$ (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}$.

Usted obtener su probabilidad por

P(exactamente N sucesses) = P(exactamente N éxitos + sin las cadenas de la longitud X) + P(exactamente N éxitos + cadenas de longitud X). La mano izquierda es simplemente dada por el teorema del binomio.

....así que más a la derecha de la probabilidad: $$ \frac{5}{2^5} = \frac{1}{2^5}+P(\text{cadena de longitud X existe},N|Y) $$ así $$ P(\text{cadena de longitud X existe},N|Y)=\frac{4}{2^5}. $$ Ahora solo hay que dividir por la probabilidad de que haya exactamente N éxitos para obtener la probabilidad condicional de a $\frac{4}{5}$, que es la respuesta correcta.

Creo que la periodicidad y la fórmula está bien definido, pero no estoy 100% seguro de que en este punto.

R-Versión, que después de algunas correcciones parece estar de acuerdo con Max, pero podría mí más general, si lento. chance2 da el resultado final. También he probado los resultados de la función y la comparó con la simulación. Parece que dar la respuesta correcta. Almacenamiento en caché de los valores en una matriz de dos dimensiones para L,N podría hacer que el programa relativamente rápido.

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

Answer 3

Creo que esta es sólo una solución parcial para el caso de al $N<2X$.

Definir $A_i$ a ser el conjunto de todas las secuencias de $Y$ eventos con $N$ éxitos que, al menos, $X$ éxitos se producen consecutivamente comenzando en la posición $i$ en la secuencia, y no de cadena de $X$ éxitos es comenzar antes de la posición $i$. Por ejemplo, si $Y=4$, $N=3$, $X=2$, y los éxitos se denota por a$1$, mientras que los fracasos son denotados por una $0$, luego $A_1=\left\{1101,1110\right\}$, $A_2=\left\{0111\right\}$, y $A_3=\left\{1011\right\}$. El índice de $i$ pistas de$1$$Y-X+1$, debido a que necesitamos, al menos, $X$ spots para contener la cadena de $X$ éxitos.

Ahora vamos a contar el tamaño de cada uno de los $A_i$, $i=1,\ldots,Y-X+1$, para genéricos $Y$, $N$, y $X$ con la restricción de que $N<2X$.

• $|A_1|=\binom{Y-X}{N-X}$ porque la cadena de $X$ éxitos comienza en la primera posición y se extiende hasta la posición $X$, y más allá de que no nos importa el orden de el resto de los éxitos y de los fracasos.
• Ahora, para todos los $i\in\left\{2,\ldots,Y-X+1\right\}$, $|A_i|=\binom{Y-X-1}{N-X}$. Podemos pensar acerca de estas secuencias en la siguiente forma: comenzar el $X$ éxitos en la posición $i$ y la fuerza de un fallo en la posición$i-1$, por lo que la cadena de $X$ éxitos no se puede iniciar antes de la posición $i$. Ahora no nos interesa el orden del resto de los éxitos y fracasos en todas las otras posiciones, por lo que podemos colocar simplemente eligiendo donde en el resto de $Y-X-1$ puntos el resto de $N-X$ éxitos ir. Hay $Y-X+1-1=Y-X$ de estos $A_i$, $i\in\left\{2,\ldots,Y-X+1\right\}$.

Esto da un total de $$\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 $S$ with $N$ successes is $\binom{Y}{N}$. Thus, the probability of a sequence of length $S$ 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}}$$

En R, una función simple para calcular estas probabilidades, sería la siguiente.

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 4

Esta solución funciona para todos los valores de $n$.

Puede definir una fórmula recursiva para la probabilidad de $x$ consecutivos éxitos, $y$ ensayos, y $n$ éxitos: \begin{align} f(x,y,n) &= g(x, x, y, n) \end{align} donde \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{casos} \end{align}

El $x'$ parámetros aceptados por $g$ es el número de éxitos consecutivos necesario. El $x$ parámetro es la longitud de un bloque de éxitos consecutivos necesario si el bloque se inicia en la primera posición. Por lo tanto, si $x$ es cero, ya hemos conseguido nuestro objetivo y la probabilidad es de uno. Si no es cierto que la $0 < x \le n \le y$ no podemos lograr nuestro objetivo, así que volvemos a cero. En el último caso, con una probabilidad de $n/y$, podemos observar un éxito, así que tenemos uno menos éxito en una fila para hacer y por lo $x$ disminuye; sin embargo, $x'$ no disminuye a causa de un fallo, se necesitaría $x'$ lograr nuestro objetivo. En el caso de que un fallo ha $\frac{y-n}y$ de probabilidad, y que nos pone a todos el camino de regreso a $x=x'$. En cualquier caso, $y$ disminuye, sino $n$ sólo disminuye en el caso de un éxito.

---

#!/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))

imprime 104/105