Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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}}$ –  user17762 Mar 13 '11 at 20:33
2  
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$. –  Roah Mar 13 '11 at 21:21
1  
@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. –  Byron Schmuland Mar 15 '11 at 0:22
2  
That is N-player ruin problem. See: Y.Swan - A Matrix-Analytic Approach to the N-Player Ruin Problem –  Viktor Mar 15 '11 at 23:23
5  
There is a paper arguing for why this is unlikely to have any closed form solution for N>3. projecteuclid.org/… –  user1708 Mar 18 '11 at 7:42

1 Answer 1

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*} $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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