Probabilidad de que todas las cartas hayan sido robadas.

Question

Digamos, tengo un mazo de $m$ tarjetas de la que voy a dibujar $n$ tarjetas al azar, de ver y poner de nuevo en el mazo. Quiero saber; ¿qué es el cambio después de la $k$ sorteos que he visto todas las cartas en la baraja.

En realidad, es una variante del problema descrito aquí, sin embargo, en este y en este caso el número de elementos por sorteo es sólo uno.

simulación

He hecho una simulación en el que el decksize es de 10 y el número de tarjetas de cada sorteo es de 4, los resultados se grafican a continuación (aquí está el código de python).

intento personal

Yo sólo tengo hasta el punto a calcular la probabilidad de que una sola tarjeta no está en un único sorteo:

$\displaystyle P = (1 - \frac{1}{m})(1 - \frac{1}{m-1})(1 - \frac{1}{m-2})(1 - \frac{1}{m-3}) = \sum_{i=1}^n (1 - \frac{1}{m-i+1}) $

Answer 1

Creo que la solución sería algo como esto:

Deje $P(m, n, k, x, y)$ ser la probabilidad de ver exactamente $x$ tarjetas de, al menos, una vez a través de $k$ sorteos, una vez $y$ tarjetas ya se han visto.

A continuación, $P(m, n, k, x, 0) = \sum_{i=0}^{x}P(m, n, k-1, x-i, 0) * P(m, n, 1, i, x-i)$

Creo que las posibilidades de la suma signo son únicas, por lo que podemos sumar en ellos.

La solución entonces es $P(m, n, k, m, 0)$. Lo que queda es definir $P(m, n, 1, i, x-i)$ y debemos ser capaces de resolver el problema de forma recursiva.

Edit: completa solución en Python, la aplicación del método anterior:

import numpy as np
from scipy.special import comb
import matplotlib.pyplot as plt
m = 10
n = 4
def P(k, x, y):
    if k == 1:
        return (comb(m-y, x) * comb(y, n-x))/comb(m, n)
    else:
        prob = 0
        for i in range(x):
            prob += P(k-1, x-i, y) * P(1, i, y+x-i)
        return prob

def P_MC(k, x, y):
    sims = 10000
    good = 0
    for s in range(sims):
        ar = np.arange(m)
        seen = set(np.arange(y))
        for draw in range(k):
            np.random.shuffle(ar)
            for el in ar[:n]:
                seen.add(el)
        if len(seen) == (x+y):
            good += 1
    return good/sims

ests = []
acts = []
for k in range(1,16):
    ests.append(P_MC(k, m, 0))
    acts.append(P(k, m, 0))

plt.plot(range(1,16), ests)
plt.plot(range(1,16), acts)
plt.grid()
plt.legend(['Simulated', 'Actual'], loc='lower right')

Answer 2

Esta es una simple variante de la cupón del colector problema, que utiliza la clásica de la ocupación de distribución. Deje $K$ el número de cartas distintas que han sido elaborados, distribuidos de acuerdo a la clásica de la ocupación de distribución. Con $m$ distintas cartas en la baraja, y $n \geqslant m$ aleatorio con reemplazo, la probabilidad de sacar cada tarjeta al menos una vez es:

$$\mathbb{P}(\text{All cards drawn}) = \mathbb{P}(K=m) = \frac{m! \cdot S(n,m)}{m^n},$$

en función de las $S$ indica los números de Stirling del segundo tipo. Esto puede ser escrito en forma explícita como:

$$\mathbb{P}(K=m) = \sum_{i=0}^m (-1)^i {m \choose i} \bigg( 1-\frac{i}{m} \bigg)^n.$$