Supongamos que usted tiene una cubierta de $y$ tarjetas. En primer lugar, seleccionar aleatoriamente $y-x$ cartas distintas y firmar la cara de cada uno, baraja todas las cartas en el mazo. Proceda de la siguiente manera:
Roba una carta. Si ya está firmado, reemplace la tarjeta y baraja el mazo. Si todavía no está firmado, la firma, a continuación, vuelva a colocar la tarjeta y baraja el mazo. Mi pregunta es ¿cuál es la probabilidad de que saques un unsigned tarjeta como una función del tiempo? Por ejemplo, cuando se $t=1$, la probabilidad es $x/y$. Al $t=2$, la probabilidad es $\frac{x(x-1)}{y^2}+\frac{(y-x)(x)}{y^2}$ y así sucesivamente. He escrito un programa en Python que calcular las probabilidades para valores pequeños de a $t$, pero el tiempo de ejecución es $O(2^t)$ y pregunto si hay una manera más sencilla de resolver este problema
Mi solución:
El número de sumandos para el tiempo de $t$$2^{t-1}$, y cada uno es de la forma $\frac{a_1a_2\dots a_t}{y^t}$. El conjunto de $t$-tuplas $a_1a_2\dots a_t$ que aparecen en la suma se puede poner en bijection con el conjunto de los impares cadenas binarias de longitud $t$ como sigue: Si el $i$-ésimo dígito de la cadena es 1, $a_i$ $x$ menos la suma de las cifras anteriores de la cadena; de lo contrario, $a_i$ es igual a $y-x$ además de la suma de las cifras anteriores. Por ejemplo, $1101$ se corresponde con $x(x-1)(y-x+2)(x-2)$ $1011$ se corresponde con $x(y-x+1)(x-1)(x-2)$. Es bastante sencillo escribir un algoritmo que va a recorrer todas esas cadenas binarias para encontrar la probabilidad.
