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.

Improve this question
$\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$
    – Douglas Zare
    Commented 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
    Commented 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$
    – Douglas Zare
    Commented Aug 18, 2014 at 7:34

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .