# Repeatedly Toss Balls into Bins

$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.

• a quite hard problem, pls help:-) – platinum Mar 2 '13 at 10:05
• Can you do some small problems, like $n=m=2$, $k=1$, to see if any patterns develop? – Gerry Myerson Mar 2 '13 at 11:20
• 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! – platinum Mar 2 '13 at 11:26

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.