Valor esperado de llenar aleatoriamente los cubos hasta el conflicto

Question

El problema está directamente relacionado con el famoso paradoja de cumpleaños pero con un giro/complicación.

problema

Tenemos $n$ cubos y ponemos al azar bolas en ellos. ¿Cuál es el valor esperado de las bolas que se ponen si nos detenemos después de la primera colisión -¿Intentar meter una bola en un cubo ya lleno?

¿Y si tenemos $s$ ¿Intentos por cada balón?

contexto

Lo que facilita las cosas es que sólo necesito una solución aproximada y puedo usar el ordenador para hacer el cálculo pesado. Lo que hace las cosas más difíciles es que me gustaría resolverlo para los valores $n$ en algún lugar alrededor de $[2^{32};2^{64}]$ por lo que calcular la suma de la manera más directa no es factible.

Problema XY, alternativas

El problema real que hay detrás es la evaluación de la eficiencia de un [tipo de] implementación de tablas hash. Así que si hay una forma de estimar la eficiencia, calculando otra función de distribución, me parece bien. En realidad, en el problema del cumpleaños encontramos una serie de elementos $k$ tal que la probabilidad de colisión es $\approx 0.5$ . He podido comprobar "experimentalmente" que para $s = 1$ , $k \propto n^{1/2}$ y para $s = 2$ $k \propto n^{2/3}$ lo que lleva a la extrapolación para $s = 4$ : $k \propto n^{4/5}$ pero eso es demasiado especulativo y no estoy seguro de encontrar ese $k$ es significativo para mi caso.

donde estoy actualmente con la resolución

En el caso $s = 1$ El valor sería:

$$\frac{1}{n}\cdot1 + \frac{n-1}{n}\frac{2}{n}\cdot2 + \frac{n-1}{n}\frac{n-2}{n}\frac{3}{n}\cdot3+\cdots$$ o $$\frac{1}{n}\sum_{k=1}^{n} \frac{n!}{(n-k)!}k^{2}\frac{1}{n^{k}}$$ que no es muy difícil de resolver aproximadamente. Por ejemplo, convirtiendo una suma en una integral con factorial expresado por la aproximación de Stirling y luego podría ser resuelto simbólicamente (no he probado TBH).

En realidad quería resolver el problema para $s = 4$ pero sería mejor una solución genérica.

$$\frac{1}{n^s}\cdot1 + \frac{n^s-1}{n^s}\frac{2^s}{n^s}\cdot2 + \frac{n^s-1}{n^s}\frac{n^s-2^s}{n^s}\frac{3^s}{n^s}\cdot3+\cdots$$ o $$\frac{1}{n^s}\sum_{k=1}^{n} k^{s+1}\prod_{j=0}^{k-1}\frac{n^s - j^s}{n^s}$$

Para $s = 2$ estamos recibiendo $a^2 - b^2 = (a-b)(a+b)$ , que se reduce fácilmente a combinaciones factoriales bastante sencillas como para $s = 1$ pero para $s = 4$ No he encontrado ninguna forma de simplificar la expresión.

Answer 1

Para la primera colisión, tenemos el problema de cumpleaños generalizado . Para obtener una $\frac 12$ probabilidad de colisión (no es el mismo que el número esperado, pero no está muy lejos) necesita $\sqrt {2 \ln 2 n}$ bolas.

Para $s$ intentos por bola, voy a suponer que para cada bola eliges un cubo al azar. Si el cubo está ocupado, vuelves a elegir un cubo al azar, que podría ser el mismo que acabas de probar. Si obtienes $s$ cubos ocupados por una sola bola que paras.

La primera bola tiene éxito. La segunda falla con probabilidad $\frac 1{n^s}$ porque tienes que golpear el único cubo ocupado $s$ veces. Asumiendo que la segunda tuvo éxito, la tercera falla con probabilidad $\frac {2^s}{n^s}$ porque hay dos cubos ocupados para golpear. La posibilidad de tener éxito a $k$ bolas es $$\prod_{i=1}^k\left(1-\frac {(i-1)^s}{n^s}\right)$$

He escrito un programa rápido. Con $s$ en la primera columna y $n$ por la parte superior, me parece que el número de bolas para tener un $\frac 12$ La probabilidad de colisión es la siguiente $$\begin {array} {r|r|r|r} \ &10^6&10^7&10^8\\ \hline 1&1,178&3,724&11,775 \\2&12,765&59,245&274,990\\3&40,807&229,468&1,290,392\\ 4&80,903&510,458&3,220,766\\5&126,814&863,966&5,886,125\end {array}$$ La primera línea comprueba la fórmula de Wikipedia.

Answer 2

También medí con un programa, pero esta vez fue el valor medio:

function mean(s, n) {
  var sum = 0;
  var prod_log = 0;
  for (var k = 1; k <= n; k++) {
    sum += k ** (s+1) * Math.exp(prod_log);
    prod_log += Math.log1p(-1 * (k/n) ** s);
  }
  return sum / n**s;
}

advertencia: la medición $n=2^{30}$ tarda un minuto entero

Los resultados se ajustan a la fórmula empírica $$k \propto n^{\frac{s}{s+1}+\varepsilon}$$

$$\begin {array} {r|r} \ s&2^{10}&2^{15}&2^{20}&2^{25}&2^{30}&k=f(n)\\ \hline 1&5.314&7.824&10.325&12.826&15.325&\log k\approx\frac{1}{2}\log n+0.325 \\2&7.028&10.365&13.698&17.032&20.365&\log k\approx\frac{2}{3}\log n+0.365 \\ 4&8.340&12.341&16.341&20.341&24.341&\log k\approx\frac{4}{5}\log n+0.341\\9&9.260&13.760&18.260&22.760&27.260&\log k\approx\frac{9}{10}\log n+0.260\end {array}$$