¿Qué proporción de mi amigo ' calzones de s fueron los mejores que había hecho hasta ahora?

Question

(Historia verdadera:) Un amigo mío estaba haciendo un calzone y dijo que no era el mejor que jamás había hecho. Me preguntaba, ¿qué fracción de los calzones que hizo fueron lo mejor que había hecho en el momento tiene?

Asumir que hace $n$ calzones, cada uno con una calidad elegida i.i.d. de una distribución normal (él no mejora en absoluto). Asintóticamente, ¿qué proporción de los calzones que hace son de lo mejor que había hecho hasta ahora?

¿Mi intuición dice que debería ser algo así como $1/\sqrt{n}$?

Answer 1

Hacemos un cálculo que responde a su pregunta, al menos en el sentido de la expectativa. Supongamos que tomamos $n$ calzones en una fila. Supongamos que para cualquier par de calzones $C_1$$C_2$, $C_1$ es mejor que el de $C_2$ o de la otra manera (sin ataduras).

Para cualquier $i$$1$$n$, vamos variable aleatoria $X_i$ ser igual a $1$ si $i$-th calzone es el mejor hasta ahora, y ser igual a $0$ lo contrario.

Deje $Y=X_1+X_2+\cdots+X_n$. Nos encontramos con la expectativa de $Y$, que por la linealidad de la expectativa es $E(X_1)+E(X_2)+\cdots+E(X_n)$.

La probabilidad de que $X_i=1$$\dfrac{1}{i}$. Esto requiere la suposición de que uno no aprende de la experiencia, por lo que todos los pedidos de calidad entre los primeros a $i$ calzones son igualmente probables. Bajo ese supuesto, se deduce que $$E(Y)=1+\frac{1}{2}+\cdots+\frac{1}{n}.$$

Por lo $E(Y)$ $n$- ésimo número armónico $H_n$. Es bien aproximada por $\ln n$.

La espera proporción de calzones que son "la mejor hasta el momento" es, por tanto,$\dfrac{H_n}{n}$, que es aproximadamente de $\dfrac{\ln n}{n}$.

Answer 2

Podemos suponer sin pérdida de generalidad que nunca hay un momento donde hace un calzone exactamente el mismo.

A continuación, podemos hacer la simplificación del problema que de la $n$ calzones, cada uno de ellos está etiquetada $1,2,3,\dots,n$ en términos de valor.

Reformulación de la pregunta, se podría preguntar "En una permutación $\sigma\in S_n$, ¿cuántas $i$ satisfacer $\sigma(i)>\sigma(j)$ todos los $j<i$?"

Deje $X_i$ ser un indicador de la variable aleatoria $X_i=\begin{cases}1&\text{if}~\sigma(i)>\sigma(j)~\text{for all}~ j<i\\ 0&\text{otherwise}\end{cases}$

Tenemos entonces $X=\sum\limits_{i=1}^n X_i$ es la variable aleatoria contando cuántos "mejor hasta ahora".

$\mathbb{E}[X]=\mathbb{E}[\sum\limits_{i=1}^n X_i]=\sum\limits_{i=1}^n \mathbb{E}[X_i]$ por la linealidad de las expectativas.

En el cálculo de cada uno de estos, tenga en cuenta que dado lo $i$ aparecen los números, cada permutación de dicho $i$ números tienen la misma probabilidad. Si $X_i=1$, lo que implica que la mayor de las cuales estarán en la final.

Tenemos entonces $\mathbb{E}[X_i]=\frac{(i-1)!}{i!}=\frac{1}{i}$

Por eso, $\mathbb{E}[X]=\sum\limits_{i=1}^n \frac{1}{i}=H(n)$ $n^{th}$ número armónico.