2
$\begingroup$

Let there be $m$ indistinguishable balls, $k$ bins, $C$ capacity. Let $X_j$ denote the total balls in bin $j$. I've seen ways to calculate the total number of combinations, but I'm not sure how to go about calculating the mean and variance of $X_j$. It is understood that the ball is always thrown into one of the empty bins with uniform probability. edit: nonfull bins not empty bins sorry.

$\endgroup$
  • $\begingroup$ You say balls are always thrown into an empty bin, but allow for multiple balls in a bin. This is contradictory. Also, the capacity $C$ does not seem to enter in. Did you perhaps mean to say that balls are thrown into bins with fewer than $C$ balls? $\endgroup$ – saulspatz Feb 16 at 3:43
  • $\begingroup$ Yeah that's right. My bad. I edited the question. $\endgroup$ – jc141414 Feb 16 at 3:46
  • $\begingroup$ You said the balls are indistinguishable, but are they thrown one after another? E.g. in the case of $m=k=C=2$, there are only 3 final configurations (both in bin 1, both in bin 2, one per bin), but if you throw the balls one by one then P(one per bin) = 1/2, not 1/3. $\endgroup$ – antkam Feb 16 at 6:11
  • $\begingroup$ i dont know how to calculate variance, but shouldnt mean be trivial? by symmetry all $E[X_j]$ are equal, and they sum to $m$, so each mean is $m/k$. am i right or am i missing something? $\endgroup$ – antkam Feb 17 at 3:13
  • $\begingroup$ Yeah they're thrown in one by one, and yes I agree mean is trivial. $\endgroup$ – jc141414 Feb 17 at 17:25
1
$\begingroup$

This seems computationally very difficult to me. You might do better with simulation.

It $C\ge m$ then the constraint has no effect, and we are just looking for the mean and variance of the number of balls in bin $j.$ This has a binomial distribution, and the answer is well known.

When ${m\over k}\leq C< M,$ the situation is much more complicated, because the result depends on the sequence in which the balls were thrown into the bins. Before any bin fills up, a ball has probability $1/k$ of landing in bin $j.$ After some other ball fills up, it has probability $1/(k-1)$ of landing in bin $j$. The situation is even more complicated if it's possible for more than one ball to fill up.

Consider the case $k=3, j=1.$ Let $P(x_1,x_2,x_3)$ be the probablity that at some point there are $x_i$ balls in bin $i$ for $i=1,2,3.$ To compute the expectation, we have to sum up terms of the form $aP(a,b,c)$ where $a+b+c=m.$ If $\max\{a,b,c\}<C,$ we have simply $$P(a,b,c)={m\choose a,b,c}3^{-n}\tag{1}$$ But suppose $c=C.$ Then $$P(a,b,c)=P(a,b,C)=\frac12P(a-1,b,C)+\frac12P(a,b-1,C)+\frac13P(a,b,C-1)\tag{2}$$ taking account of all bins the last ball might have been thrown into.

The last term on the right-hand side of $(2)$ can be computed directly from $(1),$ but the first two have to be computed recursively from $(2)$. It won't take many bins, or many balls, before this computation becomes unwieldy, if the capacity constraint is effective.

There are so many possible sequences of throws that memoization is unlikely to be effective, so far as I can see. I've been tying to think of ways to simplify the calculations, but so far, I don't have a glimmer.

$\endgroup$
0
$\begingroup$

Here's some a Monte Carlo simulation in Python for the problem. Disclaimer: it's not efficient.

import numpy as np
import sys

def simulate(num_balls, num_bins, capacity, num_sims):
    assert(capacity * num_bins >= num_balls)
    results = np.empty((num_sims,))
    for i in xrange(num_sims):
        unfilled_bins = set(range(num_bins))
        bin_counts = np.zeros((num_bins,))
        for _ in xrange(num_balls):
            chosen_bin = np.random.choice(list(unfilled_bins))
            bin_counts[chosen_bin] += 1
            if bin_counts[chosen_bin] >= capacity:
                unfilled_bins.remove(chosen_bin)
                if chosen_bin == 0:
                    break  # Stop the simulation prematurely.
        results[i] = bin_counts[0]
    return results

if __name__ == '__main__':
    try:
        num_balls, num_bins, capacity, num_sims = map(int, sys.argv[1:])
    except:
        sys.stderr.write(('usage: {} NUM_BALLS NUM_BINS CAPACITY '
                          'NUM_SIMS\n').format(sys.argv[0]))
        sys.exit(1)
    total_capacity = capacity * num_bins
    if total_capacity < num_balls:
        sys.stderr.write(('error: parameters must satisfy'
                          'CAPACITY * NUM_BINS >= NUM_BALLS`.\n'))
        sys.exit(2)
    results = simulate(num_balls, num_bins, capacity, num_sims)
    mean = results.mean()
    var = results.var()
    sys.stdout.write('mean = {}\tvar = {}\n'.format(mean, var))
```
$\endgroup$
  • $\begingroup$ I'm not sure this is right. The OP clearly says "THE ball IS thrown into a non-full bin with equal probability", so I would read that as each ball is thrown one by one. E.g. consider the case $m=k=C=2$. Your $f[2,2] = 3, f[1,1] =1$ but $P(X_1 = 1) = 1/2$ if the balls were indeed thrown one after another. $\endgroup$ – antkam Feb 16 at 6:07
  • $\begingroup$ You are right. I didn't interpret OP's meaning correctly. $\endgroup$ – parsiad Feb 16 at 6:16
  • $\begingroup$ @antkam: I edited my answer to something slightly more useful. $\endgroup$ – parsiad Feb 17 at 1:11

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.