Skip to main content
2 of 2
Trivial formatting changes.
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

Steady state expectation of dynamic system of urns & balls

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.

JHD
  • 101
  • 2