$n$ balls are randomly tossed into $m$ bins, each bin can hold $k$ balls. If a ball is tossed into a full bin (already has $k$ balls in it), it can be tossed repeatedly and randomly into the $m$ bins again until an empty or partly loaded bin is met. The question is that what is the expectation of the toss times for the $n$ balls, and what is the distribution of the number of balls in the $m$ bins ($n \leq mk$). For the first question, a simplified version can also be: when there are already $n$ balls accumulated in the $m$ bins according to the above toss rule, what is the average toss times for another ball tossed into the bins (we could discuss the case in this stable state rather than the build process).

I know without the re-toss process, the number of balls in the bins must follow the binomial distribution; however, when the re-toss is added, it turns to be quite different.

  • $\begingroup$ a quite hard problem, pls help:-) $\endgroup$ – platinum Mar 2 '13 at 10:05
  • $\begingroup$ Can you do some small problems, like $n=m=2$, $k=1$, to see if any patterns develop? $\endgroup$ – Gerry Myerson Mar 2 '13 at 11:20
  • $\begingroup$ I once attempted to build recurrence relation from bottom up like what you've mentioned, but the state explosion is beyond my ability to handle it, thank you for your advice! $\endgroup$ – platinum Mar 2 '13 at 11:26

If you know about random walks, I would formalize this as follows :

Let $X_N$ be a discrete time process in the state space $(\mathbb N \cup \{0\})^{m}$. We let $X_0 = (0,0,\dots,0)$ and we say that $$ e_i = (0,\dots,1,\dots, 0), \quad \mathbb P(X_{N+1} = X_N + e_i) = 1/m. $$ So you add a ball in a bin and the model assumes that the bins can store infinitely many balls. Now you're interested in some events, so we need to define them properly in terms of random variables we can study. Write $$ X_N = (X_{N,1},\dots, X_{N,m}) $$ and consider $$ T_{N,i} = \min \{ X_{N,i}, k \}, $$ so that $$ T_N = (T_{N,1}, \dots, T_{N,m}) $$ would represent what is actually in your bins. If $$ \tau_n = \inf \left \{ N \in \mathbb N \, \left| \, \sum_{i=1}^m T_{N,i} \ge n \right. \right \}, $$ then using stochastic process theory one can show that this defines a stopping time (you need to define the filtrations and everything but that will work out just fine). This was too big for a comment, because I didn't actually work out the details, but having a formal setting always gives a good start. Note that what you want to look for would be :

For the expected toss of the $n$ balls, you want $\mathbb E[\tau_n]$ ;

For the distribution of $X_N$, well you can readily compute it using this model.

I hope this setting will help you get started.

  • $\begingroup$ thanks, random walks seems kind of advanced mathematics for me, I will try to learn something about it. If there is any solution using elementary mathematics? $\endgroup$ – platinum Mar 3 '13 at 10:04
  • $\begingroup$ @platinum : I don't know, but the problem doesn't seem very elementary to me. But that's just me ; there might be a very clever elementary solution to the problem, I just don't expect it. $\endgroup$ – Patrick Da Silva Mar 8 '13 at 17:53

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.