Dada una distribución de probabilidad discreta con resultados posibles$n$ y la tarea de muestrear repetidamente hasta obtener cada resultado al menos una vez, ¿la distribución uniforme proporciona el menor valor esperado para el número total de muestras?
Respuestas
¿Demasiados anuncios?
Sí. Esto se muestra por ejemplo en [1], bajo el nombre de Colector de la desigualdad:
El resultado que deseo señalar es que el $A(\mathbf{p})$ es un Schur-convexo función de la probabilidad de vectores $\mathbf{p}$. Es decir, si $\mathbf{p} \gg \mathbf{q}$,$A(\mathbf{p}) > A(\mathbf{q})$. Por lo tanto, el valor mínimo de $A(\mathbf{p})$ se produce cuando $\mathbf{p}$ es la distribución uniforme $\mathbf{u} = (1/n,\dots,1/n)$.
[1] Clevenson, M. Lawrence y William Watkins. Majorization y el Cumpleaños de la Desigualdad. Las matemáticas de la Revista, vol. 64, no. 3, 1991, pp 183-188. JSTOR, JSTOR, www.jstor.org/stable/2691301.
saulspatz
Puntos
116
En el papel de "la paradoja de Cumpleaños, cupón los coleccionistas, los algoritmos de almacenamiento en caché y la auto-organización de la búsqueda de" la ecuación de $(13b)$ da el número esperado de sorteos para conseguir una completa colección de $m$ cupones, donde cupón $i$ probabilidad de $p_i$ $$\int_0^{\infty}\left(1-\prod_{i=1}^m(1-e^{-p_it})\right)\mathrm{dt}$$ Clearly it is enough to show that for every $t\ge0,$the maximum value of $\prod_{i=1}^m(1-e^{-p_it}),$ subject to $0\le p_i,\ i=1,\dots,m$ and $\sum_{i=1}^mp_i=1,$ occurs when all the $p_i=1/m.$ Esto es fácil, tomar el logaritmo del producto y el uso de multiplicadores de Lagrange.
JiminyCricket
Puntos
143
Ignora todos menos dos de los tipos de cupones. Condicional en el número combinado$n$ de cupones de estos dos tipos que se han dibujado, la probabilidad de que ambos tipos se hayan dibujado es$1-p^n-(1-p)^n$, donde$p$ es la probabilidad de que un cupón de uno de estos dos tipos son del primer tipo. Esto es máximo para$p=\frac12$. Por lo tanto, una distribución solo es óptima si$p=\frac12$ para todos los pares de tipos, es decir, si es uniforme.
