4
$\begingroup$

Suppose there are $m$ balls and $n$ bins. We use the Power of Two Choices except we pick the heavier bin instead of the lighter bin: i.e. given a set of $n$ bins, the balls are thrown sequentially and two bins are picked uniformly at random (with replacement) and the ball is thrown into the bin with more balls out of the picked bins each time. I want to know what is the expected number of empty bins in this case.

Does anyone know if the behavior of the Power of Two Choices has been studied in the context of picking the heavier instead of the lighter bin?

$\endgroup$
2
$\begingroup$

You only put a ball in an empty bin if both selected bins were empty. I think there is a recursion for finding the probability of $k$ empty bins when you have $n$ bins and $m$ balls and $n$ bins. Let's call this probability $p(k,m,n)$. Then

$$p(k,m,n) = \frac{(k+1)k}{n(n-1)}p(k+1,m-1,n) + \left(1-\frac{k(k-1)}{n(n-1)}\right)p(k+1,m-1,n)$$

starting with $p(n,0,n)=1$ and $p(k,0,n)=0$ when $k \not=n$, and clearly there must be at least one empty bin at all times and no more than $n$ so $p(k,m,n)=0$ when $k \lt 1$ or $k \gt n$.

The expected number of empty bins is then $\sum\limits_{k=1}^n k\, p(k,m,n)$, and in a sense this provides an answer for any specific values of $n$ and $m$, but I suspect it is possible to do better.

Some empirical calculations suggest (with $0^m$ being $1$ when $m=0$ and $0$ when $m \gt 0$) that

  • for $n=2$ the expectation is $0^m+1$
  • for $n=3$ the expectation is $\frac12 0^m + \frac32 \left(\frac23\right)^m + 1$
  • for $n=4$ the expectation is $\frac15 0^m + \left(\frac12\right)^m + \frac95 \left(\frac56\right)^m + 1$
  • for $n=5$ the expectation is $\frac1{14} 0^m + \frac12\left(\frac25\right)^m + \frac{10}7 \left(\frac7{10}\right)^m + 2 \left(\frac9{10}\right)^m + 1$

which can be rewritten as

  • for $n=2$ the expectation is $\frac1{1\cdot1^m}\left(1(1-1)^m+1(1-0)^m\right)$
  • for $n=3$ the expectation is $\frac1{2\cdot3^m}\left(1(3-3)^m+3(3-1)^m+2(3-0)^m\right)$
  • for $n=4$ the expectation is $\frac1{5\cdot6^m}\left(1(6-6)^m+5(6-3)^m+9(6-1)^m+5(6-0)^m\right)$
  • for $n=5$ the expectation is $\frac1{14\cdot10^m}\left(1(10-10)^m+7(10-6)^m+20(10-3)^m+28(10-1)^m+14(10-0)^m\right)$

and it looks as if it should be possible to find the expected number of empty bins for your question by following this pattern, at least as the sum of $n+1$ terms involving triangle numbers, Catalan numbers and values from the Catalan triangle (all of which can be expressed as binomial coefficients). I would be surprised if there were a more closed form

For example, for $n=6$ this pattern suggests $\frac1{42\cdot15^m}\left(1(15-15)^m+9(15-10)^m+35(15-6)^m+75(15-3)^m+90(15-1)^m+42(15-0)^m\right)$ which could also be written as $\frac1{42} 0^m + \frac3{14}\left(\frac13\right)^m + \frac56 \left(\frac35\right)^m + \frac{25}{14} \left(\frac45\right)^m + \frac{15}{7}\left(\frac{14}{15}\right)^m + 1$ and this seems to be correct

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.