Variación de bolas y bins (rondas múltiples)

Question

Considere el siguiente bolas y cubos de experimento: que en repetidas ocasiones que tirar un número fijo de bolas aleatoriamente en una disminución del conjunto de las papeleras. El experimento comienza con $n$ bolas y $n$ papeleras. En cada ronda $k,$ tiramos $n$ bolas en el resto de los recipientes, y luego descartar cualquier no-vacío papeleras; por lo tanto, sólo recipientes vacíos al final de la vta $k$ sobrevivir a la ronda de $k + 1$. ¿Cuál es el número esperado de rondas antes de cada bin entre la inicial $n$ es no vacío?

En general, suponiendo que estamos llevando a cabo el estándar de bolas y cubos de experimento, entonces dado $m$ bolas y $n$ papeleras, sabemos que el número esperado de contenedores vacíos es $n(1 - \frac{1}{n})^m$. Con esto en mente, he intentado considerar cada ronda en el anterior experimento como una instancia de la norma de bolas en cajas problema, y han reformulado la pregunta a un equivalente de uno, así:

Supongamos que para cada ronda, exactamente el número esperado de contenedores están vacíos. Luego, después de cuántas rondas hace el experimento final?

Sin embargo, el número esperado de la fórmula que se hace difícil de manejar. Pero consideremos la función definida para cualquier entero $i \geq 0$:

$f(i+1) = 2^{f(i)}$ $i \geq 1$ $f(0) = 1$

¿Puedo utilizar una inducción argumento para demostrar que, después de la ronda $i$ y antes de la ronda de $i + 1$ (suponiendo que exactamente el número esperado de contenedores están vacíos para cada ronda), tenemos que $\frac{n}{f(i+1)} \leq \textit{number of empty bins} < \frac{n}{f(i)}$ e intentar estrechamente vinculado a la solución de arriba?

Answer 1

Demasiado largo para un comentario:

Un rápido (desactivada) intento me sugirió que para $n=1$ el número esperado de rondas para llegar a $0$ papeleras restante es$1$$n=2$$\frac32$$n=3$$\frac{65}{36}$$n=4$$\frac{845}{432}$, así que aún menos de $2$ rondas de espera.

Yo habría pensado que $n$ podría tener que ser muy grande para el número esperado de rondas exceder $4$ sustancialmente, posiblemente algo relacionado con el logaritmo iterado pero tal vez más cerca de la base de $e$ más que su sugerencia de base $2$.

Supongamos que hay $n$ bolas y $k$ papeleras. A continuación, el número esperado de bandejas vacías después de una ronda es $k\left(1-\frac1k\right)^n$ que para un gran $n$ $k$ es de alrededor de $k\exp(-n/k)$. Si $k=n$ esto es acerca de la $n\exp(-1)$. Y, a continuación, usted puede necesitar más rondas.

Si usted tiene una secuencia a partir de a $a_0=0$$a_{m+1} = a_{m}-\exp(-a_m)$, entonces, por muy grande $n$, después de $m$ rondas que usted puede esperar tener sobre $n\exp(a_m)$ bandejas vacías a la izquierda. Creo que el número de los restantes contenedores podría ser de alrededor de $n\exp(-1)$ después de una ronda, acerca de $n\exp(-1-\exp(1))$ después de dos rondas, acerca de $n\exp(-1-\exp(1)-\exp(1+\exp(1)))$ después de tres, y acerca de la $n\exp(-1-\exp(1)-\exp(1+\exp(1)) -\exp(1+\exp(1)+\exp(1+\exp(1))) )$ después de cuatro. La primera ronda se multiplica $n$ sobre $0.368$, el segundo por sobre $0.0243$, la tercera por sobre $3\times 10^{-20}$ y el cuarto se multiplica $n$ por un número menor que $10^{-10000000000000000000}$