apagado por 1 de la lotería de probabilidad

Question

Una lotería, donde 6 bolas de 50 son extraídos de forma aleatoria sin reemplazo, permite a los jugadores de la lotería a estar fuera por un máximo de 1 por cada número que aparece en su billete de lotería. Reglas adicionales de la lotería son como sigue:

• Las bolas están numeradas de la 1 a la 50 y son todos la misma probabilidad de ser dibujado.

• Tanto los números ganadores del sorteo y los jugadores de las entradas contienen números aleatorios (de 1 a 50). Es decir, el jugador no selección, elegir sus propios números, que se realiza de forma aleatoria para ellos a través de la computadora.

• Tanto los números ganadores y los números en los billetes de lotería están ordenados en orden ascendente y ganar los boletos deben coincidir con los mapas, en ese orden. Por ejemplo, si los números ganadores del sorteo son (ordenados) 5, 10, 15, 16, 20, y el 30 y el titular del pasaje que ha 5, 10, 16, 17, 20, y 30 (también clasificado), el 16s no mapa. La coincidencia de los números son (5:5), (10:10), (15:16), (16:17), (20:20), y (30:30). Que es un boleto ganador.

Así que la pregunta es cuánto más probable es un solo billete de la lotería de espera para ser un ganador mediante el apagado por 1 regla de versos de una similar, pero mucho más estricta de la lotería (también 6 de 50 bolas), pero que no permite el apagado por 1 regla (los números deben coincidir exactamente)?

El trabajo realizado hasta la fecha:

La estricta de la lotería de posibilidades de ganar en un solo boleto es de 1 en acerca de 15.9 millones, lo que es 1 / (50 elija 6).

El apagado por 1 de la lotería fue simulado en el ordenador y estoy viendo 503 aumento de la probabilidad (alrededor de 1 en 31,600 oportunidad de ganar).

Me gustaría saber si este tipo de problema se puede hacer matemáticamente o si es demasiado difícil. También, estaba esperando que alguien podría hacer una simulación también para ayudar a verificar mi búsqueda de 503x aumento de posibilidades de ganar.

Información adicional que puede ser útil para el análisis de... El peor de los casos impulso en espera probabilidad de ganar es de 7x si (por ejemplo), el empate bolas son 1,2,3,4,5,6. Esto coincidiría con las siguientes entradas: (1,2,3,4,5,6), (1,2,3,4,5,7), (1,2,3,4,6,7), (1,2,3,5,6,7), (1,2,4,5,6,7), (1,3,4,5,6,7), y (2,3,4,5,6,7). Mejor de los casos boost es 729x donde el empate bolas son algo así como 5, 10, 15, 20, 23, 30. Los 3 más frecuentes impulsar escenarios (a partir de los resultados de la simulación) son 486x, 648x, y 729x. Estos son 3 de 137 escenarios estoy viendo en la simulación de 100.000.000 de decisiones. Aún no estoy seguro de si hay más.

Si algo no está claro, por favor pregunte antes de intentar responder a la pregunta y voy a aclarar.

Answer 1

He aquí una rápida derivación que da la misma solución a la que se ofrece por gar, aunque un poco diferente de la recursividad.

Ganadora $k$ bola de combinación se compone de secuencias de enteros $0<x_1<\cdots<x_k$$0<y_1<\cdots<y_k$, de modo que $|x_i-y_i|\le1$.

Deje $A_k(n)$ el número de formas de seleccionar la ganancia de $k$ bola de combinaciones para que $x_k,y_k\le n$. Este es el mismo que $T(n+1,k)$ definido por gar.

Igualmente, os $B_k(n)$ el número de formas de seleccionar $k$ bola de combinaciones para que $x_k\le n$$y_k\le n+1$. Obtendríamos el mismo número de lugar requerimos $x_k\le n+1$ $y_k\le n$ debido a la simetría.

Obviamente, $A_k(n)=B_k(n)=0$$n<k$. De lo contrario, $A_0(n)=B_0(n)=1$.

Vamos a considerar en primer lugar $A_k(n)$. Si $(x_k,y_k)=(n,n)$, lo que queda es escoger el restante $k-1$ bolas con $x_{k-1},y_{k-1}\le n-1$, que se puede hacer en $A_{k-1}(n-1)$ maneras. Si $(x_k,y_k)=(n,n-1)$, el resto de las $k-1$ pelotas deben tener $x_{k-1}\le n-1$$y_{k-1}\le n-2$, que se puede hacer en $B_{k-1}(n-2)$ maneras; lo mismo se aplica a $(x_k,y_k)=(n-1,n)$. De lo contrario, $x_k,y_k\le n-1$, lo que deja a $A_k(n-1)$ alternativas. Por lo tanto, $$ A_k(n)=A_{k-1}(n-1)+2B_{k-1}(n-2)+A_k(n-1). $$

Que se derivan de una recursividad para $B_k(n)$ en una manera similar. Si $(x_k,y_k)=(n,n+1)$, el resto de las $k-1$ bolas requieren $x_{k-1}\le n-1$, $y_{k-1}\le n$, dejando $B_{k-1}(n-1)$ alternativas. De lo contrario, $x_k,y_k\le n$, dejando $A_k(n)$ alternativas. Por lo tanto, $$ B_k(n)=B_{k-1}(n-1)+A_k(n). $$

Conectar $k=6$, $n=50$ da $A_6(50)=8000567708$. Desde cada una de las dos secuencias de enteros son extraídos al azar con una probabilidad de $1/\binom{n}{k}$, esto le da la probabilidad de ganar $$ \frac{A_6(50)}{\binom{50}{6}^2} =\frac{8000567708}{15890700^2}\approx 0.00003168361647. $$

Answer 2

Ya has visto que hay diferentes casos de los números ganadores $a_1 < \dots < a_6$. Es decir, el número de boletos ganadores bajo el off-by-one regla varía en función de las brechas entre los números ganadores. Usted puede modelar los diferentes casos $7$-tuplas $(x_0, x_1, x_2, x_3, x_4, x_5, x_6)$. Aquí $x_i$ denota la diferencia entre el $i$-th y $i+1$-ésimo número de $1 \leq i \leq 5$, lo $x_i = a_{i+1} - a_i$. El $x_0$ $x_6$ denotar la brecha entre los "bordes", es decir, los números 1 y 50, por lo $x_0 = a_1 - 1$$x_6 = 50 - a_6$.

Para alcanzar el número máximo de boletos ganadores tenemos dos "espacios vacíos" en torno a cada una de las $a_i$ que no se superpongan con los de otros lugares vacíos. A continuación, para cada una de las $a_i$ tenemos 3 números iguales bajo el off-by-one de la regla, de forma independiente, por lo que el número de boletos ganadores es $3^6 = 729$. La condición en la $x_i$ es que para $1 \leq i \leq 5$ tenemos $x_i \geq 2$ (por si $x_i = 1$, entonces tenemos una "superposición de la brecha" entre dos números), y tenemos $x_0, x_6 \geq 1$. De lo contrario, queremos que la $x_i$ a la suma de a $50-6 = 44$. El número de los números ganadores que cumple estas condiciones es ${44 - 5-1\choose 7-1} = {38 \choose 6}$ (Estrellas y las barras, donde vemos por primera vez resta 1 de cada $x_i$$1 \leq i \leq 5$, por lo que estamos buscando 7-tuplas de números enteros positivos que se suma a $44-5 = 39$)

La respuesta completa puede ser calculada considerando todas las condiciones diferentes de la $x_i$ . Para $1 \leq i \leq 5$ tenemos 3 condiciones: $x_i = 0 \vee x_i = 1 \vee x_i \geq 2$. Para $i \in \{0, 6\}$ le tienen o $x_i = 0$ o $x_i \geq 1$.

Por ejemplo, la fijación de $x_i = 1$ por una sola $1 \leq i \leq 5$ y dejando el resto de condiciones como en el máximo de la situación que acabamos de calcular, tenemos un solo "superposición de la brecha" entre dos números, por lo tanto el número de coincidencia de los boletos será de $3^4 \cdot 8 = 648$. El número de los números ganadores que este partido va a ser ${39 \choose 5} \cdot 5$, donde la multiplicación con 5 sigue a partir de la que podemos elegir el $i \in \{1, 2, 3, 4, 5\}$.

Como vimos aquí, el $x_i$ no juegan un papel único, es decir, son básicamente simétrica (además de la diferencia entre el "interior" y en los bordes). Sin embargo, la fijación de los dos adyacentes $x_i$ es diferente de la fijación de dos no adyacentes $x_i$.

Answer 3

La probabilidad de ganar es dada por \begin{align*} P(win) &= \frac{T(n+1,k)}{\dbinom{n}{k}^2} \end{align*} donde $T(n,k)$ se calcula por la relación de recurrencia \begin{align*} T(n,k) &= T(n-1,k) + 2*T(n-1,k-1) + T(n-2,k-1) - T(n-2,k-2)\\ T(0,0) = T(1,0) = T(2,0) = T(2,1) &= 1\\ T(1,1) = T(2,2) &= 0 \\ T(n,k) &= 0 \;\;\;\;\;\;\text{if %#%#% or %#%#%} \end{align*} como se ha dado en A209414

Por lo tanto, para $k<0$, la probabilidad resultante es \begin{align*} P(win) &= \frac{8000567708}{\dbinom{50}{6}^2}\approx 0.0000316836 \end{align*}

He emparejado con simulaciones para valores pequeños y ellos parecen estar de acuerdo.

Por ejemplo, en J:

   n=: 9
   k=: 5
   sim=: 3 : 0
a=:/:~k?n
win=:/:~k?n
k=(+/0=|a-win)+(+/1=|a-win)
)
   (+/%#)(sim"0)1e6#0

que dio acerca de 0.28, cerca de real de la $k>n$

Actualización

Algunas implementaciones,

En python:

def memoize(f):
    """ Memoization decorator for functions taking one or more arguments. """
    class memodict(dict):
        def __init__(self, f):
            self.f = f
        def __call__(self, *args):
            return self[args]
        def __missing__(self, key):
            ret = self[key] = self.f(*key)
            return ret
    return memodict(f)

@memoize
def T(n,k):
    if n == 0 and k == 0:
        return 1
    if n == 1 and k == 0:
        return 1
    if n == 2 and k == 1:
        return 1                
    if n == 2 and k == 0:
        return 1   
    if n == 1 and k== 1:
        return 0
    if n == 2 and k == 2:
        return 0
    if n < k or k< 0:     
        return 0
    return T(n-1,k) + 2*T(n-1,k-1) + T(n-2,k-1) - T(n-2,k-2)
nn = 50
kk = 6
print T(nn+1,kk)

El memoization decorador está tomada de aquí

Si un CAS se utiliza, es más fácil de implementar. E. g., en FriCAS:

)set fun cache all A
T(0,0) == 1
T(1,0) == 1
T(2,0) == 1
T(2,1) == 1
T(1,1) == 0
T(2,2) == 0
T(n,k) == 
  if k<0 or k>n then 0
  else T(n-1,k) + 2*T(n-1,k-1) + T(n-2,k-1) - T(n-2,k-2)
T(51,6)

y Einar Rødland la fórmula:

)set fun cache all A
)set fun cache all B
A(n,0) == 1
B(n,0) == 1
A(n,k) == 
    if k>n then 0
    else A(n-1,k-1)+2*B(n-2,k-1)+A(n-1,k)
B(n,k) == 
    if k>n then 0
    else B(n-1,k-1)+A(n,k)
A(50,6)