Problema de caída de huevo - minimizar el caso de AVERAGE

Question

En el huevo caída problema, tienes dos huevos y se desea determinar a partir de la cual pisos en un $n$ - piso edificio en el que puede caer un huevo tal que no se rompa. Estás a determinar el mínimo número de intentos que usted necesita para encontrar la crítica de piso en el peor de los casos, mientras que el uso de la mejor estrategia.

Algunas hipótesis :

• Si el huevo no se rompe en un determinado suelo, no va a romper en cualquier piso de abajo.
• Si los huevos se rompe en un determinado piso, se va a romper en cualquier piso por encima de.
• El huevo se puede romper en el primer piso.
• El huevo no puede romper en el último piso.

Este problema es muy popular y hay muchas maneras de resolverlo. Me estoy preguntando cómo resolverlo con la siguiente modificación : en lugar de minimizar el peor de los casos, ¿cómo se podía minimizar el promedio de caso ? Consideramos que el huevo tiene igual probabilidad de $1/n$ a romper en un piso (y por encima).

---

Un intento :

Deje $f(2,n)$ denotar el mínimo número de gotas necesarias para cubrir $n$ pisos, con el $2$huevos. Para el peor de los casos, la siguiente ecuación recursiva tiene

$$ f(2,n) = 1 + \min_{1 \le x \le n} \bigl\{ \max\{f(1,x-1),f(2,n-x \} \bigr \} $$

A grandes rasgos, al lanzar el primer huevo de un determinado suelo $x$, hay dos escenarios :

1. Si el huevo se rompe, nos quedamos con $1$ huevo y comprobar el $x-1$ pisos más abajo
2. Si el huevo no se rompe, el $n-x$ pisos por encima del $x$ tiene que ser comprobado con la $2$ huevos

Dado que el número de ensayos en el peor de los casos se reduce al mínimo, tomamos el máximo de estos dos casos por cada piso y elegir la planta que produce el mínimo número de gotas. El extra $1$ cuentas de la caída antes de saber si el huevo se rompió o no. La base de los casos son trivialmente $f(1,0)=f(2,0)=0$ (sin gotas necesario si no hay plantas), $f(1,1)= f(2,1) = 1$ (una gota es suficiente si sólo hay un piso), y $f(1,x) = x$ ($x$ gotas necesario si sólo un huevo está disponible - cada piso debe ser probado uno por uno).

Para el caso promedio, creo que el recurrente ecuación se convierte en

$$ f(2,n) = 1 + \min_{1 \le x \le n} \bigl\{ p(x)f(1,x-1)+(1-p(x))f(2,n-x) \bigr \}, $$ donde $p(x)$ es la probabilidad de que el huevo se rompe en el suelo $x$, es decir, la probabilidad de que $x$ está por encima de la crítica piso. Si esta crítica piso está representada por una variable aleatoria discreta $Y$ con una distribución uniforme en $[1,n]$: $$ p(x) = P(x\ge Y) $$

No estoy seguro de si esta correcta. Y si es así, ¿cómo puede esta expresión simplificada?

También, la base de los casos permanecen $f(1,0)=f(2,0)=0$, $f(1,1)=f(2,1)=1$, pero $f(1,x)$ ya no es igual a $x$, ya que estamos interesados en el caso promedio.

Cualquier ayuda es bienvenida, cualquier otro enfoque es bienvenida. Gracias.

Answer 1

Desde que un huevo puede romper en el primer piso, la planta puede ser la planta cero así que supongo que la probabilidad de que la crítica piso es $k$-th floor es igual a $\frac 1{n+1}$ por cada $k=0,\dots, n$. La observación de que $f(1,0)$ significa que un huevo abandonado desde el cero de piso no se rompe.

Cuando sólo queda un huevo, a continuación, ya que tienen que encontrar la crítica de piso y piso tiene una probabilidad distinta de cero de ser crítica, que todavía debe probar cada piso, uno por uno. Así que si un crítico piso es $k$th con $k\le n-1$ entonces tenemos $k$ intentos para llegar a este piso y uno adicional en el intento de quitar el huevo de la $(k+1)$th floor, lo que nos indicará que hemos llegado a la crítica de piso en el intento anterior. Si $k=n$ entonces tenemos que colocar el huevo de todas las plantas. El espera que el número de intentos es

$$f(1,n)=\sum_{k=0}^{n-1} \frac {k+1}{n+1}+n\frac 1{n+1}=\frac 1{n+1}\left(\frac{n(n+1)}{2}+n\right)=\frac n2+1-\frac{1}{n+1}.$$

Ahora la ecuación recursiva es

$$ f(2,n) = 1 + \min_{1 \le x \le n} \left\{\frac{x}{n+1}f(1,x-1)+ \frac{n+1-x}{n+1}f(2,n-x) \right\}=$$ $$1+ \frac 1{n+1}\min_{1 \le x \le n} \left\{\frac{x(x+1)}2-1 + (n+1-x)f(2,n-x) \right\}.$$

O, sustituyendo $g(n)=(n+1)f(2,n)$, tenemos $g(0)=0$, $g(1)=2$, y

$$g(n)=n+1+ \min_{1 \le x \le n} \left\{\frac{x(x+1)}2-1 + g(n-x)\right\}.$$

Yo escribí un programa para calcular la secuencia de $\{g(n)\}$ para $n\le 15000$. Resultó que una secuencia $\{g(n)-g(n-1)\}$ tiene un patrón simple:

2, 3, 3, 4, 4, 4, 5, 5, 5, 5,...

Esto sugiere que la $g(n)=g(n-1)+\left\lfloor\frac {\sqrt{8n-7}+3}2\right\rfloor$, y

$$\frac{6-4\sqrt{2}}{6}n^{1/2}\le g(n)-\frac{4\sqrt{2}}6n^{3/2}-n\le \frac{\sqrt{2}}{6}n^{1/2}.$$

A continuación la gráfica de una función de $$\left(g(n)-\frac{2\sqrt{2}}3n^{3/2}-n\right)n^{-1/2}$$