10
$\begingroup$

We have a large number of urns $N+1$. (Large means that the relative difference between $N$ and $N+1$ is well within the error bounds that I care about. The reason for the $+1$ will be apparent momentarily.) Designate them $U_1, U_2,\ldots U_N$, plus $U_E$ for the extra one.

Each urn has a capacity of $C$ balls.

There are $B$ balls in the system, $B \le NC$.

Assume to begin that the "extra" urn $U_E$, is empty. At a fixed rate, a ball is chosen at random and moved to $U_E$. This continues until $U_E$ is full, at which point the urn with the fewest balls is chosen as the new $U_E$ and the process continues.

I want to find an expression or estimate for the expected number of balls in the new $U_E$ at steady state.

Disclaimer: I am not a mathematician, although I have some appreciation for its intrinsic beauty, and admiration for those who are. This is a practical question, not an academic one. Also, even if a solution isn't apparent, help in reformulating or the problem in language that will be more broadly familiar to others would be helpful.

$\endgroup$
3
  • $\begingroup$ There is a deterministic continuous dynamical system which might be helpful. To fill $U_E$ with $C-x$ balls, the contents of the other urns decrease by a factor of $ \frac{B-C}{B-x}$. This has a fixed point in which the urn's counts form a geometric series connecting $C$ to $x$ so that the sum is $B$. I think it might help to analyze the stability of this fixed point, to see if this acts as a potential well near which the process gets stuck for a long time, in which case the expected value of $U_E$ will be close to $x$. $\endgroup$ Aug 17, 2014 at 8:12
  • $\begingroup$ Douglas: Thanks for your answer, but I'm afraid I'm not able to grasp it. Specifically, I don't understand why the contents of the other urns decrease by (B-C)/(B-x). If we choose the specific example N=10, C=10, B = 50, and x=9, so we're moving the first of the 50 balls to the empty urn, then your statement is that the contents of the other urns decrease by a factor of 40/41. Can you explain further? $\endgroup$
    – JHD
    Aug 18, 2014 at 5:44
  • $\begingroup$ You have to solve for $x$. It is not a free parameter. If you choose $N=10, C=10, B=50$ then this determines $x$ by the property that there is a geometric series $C+Cr+Cr^2+...+Cr^N = B$. This determines $r=0.823679$, and then $x=Cr^N=1.43741$. $\endgroup$ Aug 18, 2014 at 7:34

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.