A battery factory manufactures N types of batteries with each type $i$, $1 \leq i \leq N$, has a life time of $L_i$ seconds. The factory produces only one battery per second, and the battery could be any type with probability $p_i = 1/L_i$, where $p_i$ follows the Zipf's Law.

\begin{equation} p_i = C\cdot i^\alpha \end{equation} where $\alpha>0$ and $C$ is the normalization factor satisfying $Sum(p_i)=1$.

A produced battery is placed into a box, and each box contain exact $S$ batteries. A new box will be used once the current one is full.

Unfortunately, the poor factory has only $T$ boxes, $N<T<\infty$, so each time when running out of box, an automated tool is used to find the box that contains the largest number of dead batteries and discard them, or call it greedy select, leaving only live batteries in the box. In this way, it makes the most room to accommodate subsequent new batteries. This “cleaning” process takes very short time and can be reasonably ignored. Newly produced batteries are continuelly placed into the “cleaned” box until it is full. Obviously, this "select & clean" cycle repeats.

Over the time, the factory empirically finds that the box selected for cleaning always contains $D$ dead batteries. So the room produced by each cleaning cycle is a constant! Assuming this is true, then what's the value of $D$?

I wrote a small program to simulate this and found that $D$ indeed converges to a constant. Anyone can shed a light for the rationale behind?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.