Expectativa de máxima frecuencia

Question

Vi esta pregunta en un blog pero no sé cómo solucionarlo.

Pregunta: Hay K bolas en un saco numeradas 1 a K. Bob elige una bola al azar y observa su número y luego lo pone en el saco. Hace este proceso N veces. ¿Cuál es el valor esperado de la frecuencia del elemento más frecuente?

Answer 1

Esto no es exactamente una solución, pero es demasiado largo para un comentario. También, por las razones expuestas a continuación, creo que es raro para obtener una solución de forma cerrada.

Este problema es equivalente a encontrar la duración esperada de la más larga de la cadena en una tabla hash. Como tal, parece que el problema ha sido ampliamente estudiado, sin embargo, nadie ha encontrado una solución de forma cerrada. El mejor resultado parece ser que si $N, K \to \infty$ de tal manera que $N/K = \alpha$ $\alpha$ constante, entonces el promedio de ocupación máxima (es decir, la frecuencia de la mayoría de los elemento frecuente, en su formulación del problema) es asintótica a $\ln N / \ln \ln N$.

Referencia: Sección 9.4 en Una Introducción al Análisis de Algoritmos, Segunda Edición por Robert Sedgewick y Philippe Flajolet. El documento original parece ser por G. H. Gonnet, "longitud Esperada de los más largos de la sonda de secuencia en código hash de la búsqueda," Diario de la ACM 28, 1981, 289-309.