Espera que el número de cartas en la pila?

Question

Supongamos que tenemos una baraja de cartas, ordenó [1,52] (utilizando, por ejemplo, el puente de pedido). Baraja las cartas (uniformemente al azar). Voltee la parte superior de la tarjeta, tiene valor $v_0$.

Vamos a convertir a través de tarjetas una por una y ponerlos en la pila o en el descarte.

La pila comienza vacía. Deje $v_t$ es el valor de la carta superior de la pila (o $\infty$ cuando la pila está vacía).

Ahora podemos comenzar a voltear las tarjetas adicionales. Para cada tarjeta de $i$ con valor de $v_i$, si $v_0 < v_i < v_t$ a continuación, colocamos la tarjeta de $i$ sobre la parte superior de la pila, por lo que ahora $v_t = v_i$. De lo contrario, coloque la tarjeta de $i$ en el descarte.

Después de cumplir más de $k$ tarjetas, lo que se espera que el número de cartas en la pila?

Answer 1

En un círculo con $53$ tarjetas, elija una tarjeta ficticia uniformemente al azar y el número de las cartas restantes a partir de esa posición, digamos, hacia la derecha. A continuación, dibuje a partir de las cartas numeradas como usted la describe. La condición para poner la tarjeta de $v_i$ en la pila se cumple si y sólo si la tarjeta es el de las agujas del reloj vecino de la primera tarjeta de $v_0$ entre todas las cartas que se han elaborado hasta ese momento (incluyendo la tarjeta ficticia), y por simetría, la probabilidad de que se $1/(i+1)$. Por lo tanto, la previsión del número de cartas en la pila después de cumplir más de $k$ tarjetas (además de la primera carta) es

$$\sum_{i=1}^k\frac1{i+1}=\sum_{j=2}^{k+1}\frac1j=H_{k+1}-1\;,$$

donde $H_k$ $k$- ésimo número armónico. Tenga en cuenta que la probabilidad de cada tarjeta para ser considerado como un registro de la baja es exactamente la misma que en el caso estándar sin necesidad de tratamiento especial de la primera tarjeta, el resultado en ese caso sería $H_{k+1}$, e $1$ se resta porque la primera tarjeta no cuenta como un registro de la baja.

Answer 2

1. Creo $v_0$ nunca cambia, por lo que son una especie restringida a las tarjetas más grande que $v_0$ a la derecha en el inicio
2. Si $v_0$ es 0 (lo que me doy cuenta de que no es) , poner una nueva tarjeta en la pila si se trata de un registro bajo, y por simetría la probabilidad de que el $j^{th}$ vuelta es un registro de la baja es $\frac 1 j$, por lo que el número esperado de tarjetas después de haber convertido más de n cartas es como $log(n)$.
3. al $v_0$ no 0, este argumento más o menos funciona, pero el de la tarjeta de vuelta tiene que ser $ > v_0$, y una nueva baja entre todas las demás tarjetas de $> v_0$. Este consiste en el acondicionamiento en el número de este tipo de tarjetas , que creo que es hipergeométrica, y algo que puede ser de tierra.
4. Si sólo desea saber cuántas cartas después de que haya pasado a través de toda la baraja, luego condicional en $v_0$ como $log(53 - v_0)$

Answer 3

Puedo utilizar una estrategia similar a la de mike uno, pero la obtención de un cerrado fórmula.

Primera resolver un problema más sencillo, usted tiene $v_0=0$ $n$ tarjetas, se espera que el número de registro de la baja, como dice mike, es $\sum_{i=1}^{n} 1/i$.

Ahora el aumento de $v0$, podemos descartar todas las cartas por debajo de $v_0$, por lo que podemos resolver el subproblem con $v_0=0$$n=N-v_0$. Haciendo la sumatoria de cada uno de los $v_0$: $$\sum_{j=1}^N \frac{1}{N}\sum_{i=1}^{N-j}\frac{1}{i}=\frac{1}{N}\sum_{i=1}^N\frac{N-i}{i}=\frac{1}{N}\sum_{i=1}^N(\frac{N}{i}-1)=\sum_{i=1}^N\frac{1}{i}-1$$

Para $N=52$, la solución es $\simeq3.538$.

EDIT: he de ver ahora que me he olvidado de que estamos interesados en la expectativa después de $k$ tarjetas, se debe hacer la sumatoria sólo la primera $k-1$ términos. $$\mathbb{E}(k,N)=\frac{1}{N}\sum_{i=1}^{k-1}(\frac{N}{i}-1)=\sum_{i=1}^{k-1}\frac{1}{i}-\frac{k-1}{N}$$