We have $n$ boxes. And initially there are $x_1, x_2, x_3, \ldots, x_n$ marbles in each box. We randomly (with equal probabilities) select one of the boxes. We take one marble from it and we put it into another (different from the origin) box chosen randomly (with equal probabilities). We continue this process until one of the boxes become empty. How many operations we do on average?

It is not a homework. I don't know whether a closed form solution exists. My current results are:

\begin{align}{} x_1 x_2 & \text{ for } n=2\\\ \frac{3x_1 x_2 x_3}{x_1 + x_2 + x_3} & \text{ for } n=3 \end{align}

I have crossposted in artofproblemsolving. This problem is related and maybe (or not) useful.

Update2: As i learned: this problem has been studied before. As usual :) It seems very hard even for $n=4$. No explicit solution is known, only asymptotics for the case $f(x,x,x,x)$. Nevertheless the solution is much much more easier if we change slightly the problem. For example.

Big thanks to Viktor for pointing the reference!

  • $\begingroup$ Looking at what you have for $n=2$ and $n=3$, my guess would be $\frac{\binom{n}{2}}{\displaystyle \sum_{i,j,i \neq j}\frac{1}{x_i x_j}}$ $\endgroup$ – user17762 Mar 13 '11 at 20:33
  • 2
    $\begingroup$ It's beautiful but it seems that it does not pass the following test for $n=4$: $f(x,x,x,x)=f(x-1,x+1,x,x)+1$. $\endgroup$ – Roah Mar 13 '11 at 21:21
  • 1
    $\begingroup$ @Tomek The case $n=2$ is the usual one dimensional gambler's ruin problem. It is true, but not intuitively obvious, that for a symmetric random walk the expected number of steps needed to hit 0 is infinite, even starting at 1. Unless we hit 0 very soon, the random walk wanders far into the positives and then takes a long (but finite!) number of steps to reach 0. $\endgroup$ – user940 Mar 15 '11 at 0:22
  • 4
    $\begingroup$ That is N-player ruin problem. See: Y.Swan - A Matrix-Analytic Approach to the N-Player Ruin Problem $\endgroup$ – Viktor Mar 15 '11 at 23:23
  • 5
    $\begingroup$ There is a paper arguing for why this is unlikely to have any closed form solution for N>3. projecteuclid.org/… $\endgroup$ – TROLLHUNTER Mar 18 '11 at 7:42

Here are some results for very small numbers, when there are $n$ variables: $$ \begin{align*} f(1,1,1,\ldots,1) &= 1, \\ f(2,1,1,\ldots,1) &= \frac{n}{n-1}, \\ f(3,1,1,\ldots,1) &= \frac{n^3-2n^2+3n}{n^3-3n^2+4n-2} = \frac{n}{n-1} \cdot \frac{n^2-2n+3}{n^2-2n+2}, \\ f(2,2,1,\ldots,1) &= \frac{n^3-n^2+2n}{n^3-3n^2+4n-2} = \frac{n}{n-1} \cdot \frac{n^2-n+2}{n^2-2n+2}. \end{align*} $$


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.