¿Cómo encontrar el número esperado de inserciones antes de que se llene una tabla Hash?

Question

Si tengo una tabla hash con $m$ ranuras y cada ranura tiene $1/m$ probabilidad de ser elegido para la inserción de un elemento. ¿Cuál es el número esperado de inserciones antes de que se llenen todas las ranuras?

Yo pensaría que el número esperado de inserciones de elementos es $m$ pero no estoy seguro porque un elemento también puede hacer hash a la ranura de otro elemento? La razón de este pensamiento es: $$\mathbb{E}[X]=\sum_x^{m}Pr[X=x] = \sum_x^{m}\frac{1}{m}=1$$ Dónde después $m$ inserciones donde cada inserción tiene $1/m$ probabilidad, la tabla hash está llena. No me importa qué hacer con los elementos que colisionan. Para simplificar podemos descartarlos.

Answer 1

Esta pregunta es conocida como Problema con el cobrador de cupones de modo que el número esperado de inserciones hasta que se llenen todas las ranuras es: $$\mathbb{E}[X]=m H_m $$ donde $H_m$ es el número armónico: $$ H_m=\sum_{k=1}^m\frac1k. $$