# Expected value of randomly filling buckets until conflict

The problem is directly related to the famous birthday paradox, but with a twist/complication.

### problem

We have $$n$$ buckets and we randomly put balls into them. What’s the expected value of balls to be put if we stop after the first collision—attempt to put a ball into an already filled bucket?

What if we have $$s$$ tries for every ball?

### context

What makes things easier, is that I need only an approximate solution and I can use computer to do the heavyweight calculus. What makes things harder is that I’d like to solve that for values $$n$$ somewhere around $$[2^{32};2^{64}]$$ so calculating the sum the most straightforward way isn’t feasible.

### XY problem, alternatives

The actual problem behind is evaluating efficiency of a [kind of] hash-table implementation. So if there’s a way to estimate efficiency, by calculating another function of distribution, I’m OK with that. Actually, in the birthday problem we find a number of items $$k$$ such that collision probability is $$\approx 0.5$$. I was able to “experimentally” find that for $$s = 1$$, $$k \propto n^{1/2}$$ and for $$s = 2$$ $$k \propto n^{2/3}$$ which leads to extrapolation for $$s = 4$$: $$k \propto n^{4/5}$$, but that’s too speculative and I’m not sure finding that $$k$$ is meaningful for my case.

### where I am currently with solving

In the case $$s = 1$$ The value would be:

$$\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$$ or $$\frac{1}{n}\sum_{k=1}^{n} \frac{n!}{(n-k)!}k^{2}\frac{1}{n^{k}}$$ which is not very hard to solve approximately. E.g. by turning a sum into an integral with factorial expressed by Stirling’s approximation and then it might be solved symbolically (haven’t tried TBH).

I actually wanted to solve the problem for $$s = 4$$, but generic solution would be better.

$$\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$$ or $$\frac{1}{n^s}\sum_{k=1}^{n} k^{s+1}\prod_{j=0}^{k-1}\frac{n^s - j^s}{n^s}$$

For $$s = 2$$ we are getting $$a^2 - b^2 = (a-b)(a+b)$$, which easily collapses into pretty simple factorials combinations like for $$s = 1$$, but for $$s = 4$$ I found no way to simplify the expression.

• For $s=1$, Wikipedia gives a good approximation for $Q(M)$ though you want $1+Q(M)$ as your expected number. What does "$s$ tries" mean? If you have a collision with a particular ball you can try again up to $s-1$ more times? Commented Nov 11, 2018 at 19:54
• @Henry yes, that’s exactly how collisions fallback works: up to $s - 1$ tries. In reality I have $s$ hashing algorithms, I try them and I store hash as well as index of algorithm used with $\log s$ extra bits. Commented Nov 11, 2018 at 20:06

For the first collision, we have the generalized birthday problem. To get a $$\frac 12$$ chance of a collision (not the same as the expected number, but not far off) you need $$\sqrt {2 \ln 2 n}$$ balls.

For $$s$$ tries per ball, I will assume for each ball you pick a random bucket. If the bucket is occupied, you again pick a random bucket, which could be the same as the one you just tried. If you get $$s$$ occupied buckets for a single ball you stop.

The first ball succeeds. The second fails with probability $$\frac 1{n^s}$$ because you have to hit the one occupied bucket $$s$$ times. Assuming the second succeeded, the third fails with probability $$\frac {2^s}{n^s}$$ because there are two occupied buckets to hit. The chance you succeed out to $$k$$ balls is $$\prod_{i=1}^k\left(1-\frac {(i-1)^s}{n^s}\right)$$

I wrote a quick program. With $$s$$ down the first column and $$n$$ across the top, I find the number of balls to have a $$\frac 12$$ chance of collision is as follows $$\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}$$ The first line checks against the Wikipedia formula.

I also measured with a program, but this time it was the mean value:

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;
}


warning: measuring $$n=2^{30}$$ takes a whole minute

Results fit empirical formula $$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}$$