Token bucket consumption There is a bucket with tokens.
Initially, all the tokens in the bucket are old tokens.
Whenever someone picks up a token from the bucket, he replaces that token with a new token.
The rate of token consumption is R tokens per second.
After what time, 90% of the tokens in the bucket will be new tokens.
 A: If there are $N$ tokens in the bucket and $M$ of them are new the next transaction increases the number of new ones with probability $\frac {N-M}N$, so the rate of expected increase is $\frac {N-M}NR$ per second.  This gives a differential equation $$\frac {dM}{dt}=\frac {N-M}NR\\M(0)=0$$ Can you solve that?
A: This problem is equivalent to the coupon collector's problem.  This problem asks for the expected number of trials it takes to collect some number $k$ of coupons out of a set of $n$ if you randomly draw one each trial.
To make the connection between the problems a little more clear, consider the following procedure:


*

*Lay out all $n$ coupons in a row.

*Each trial, select one at random.

*If you have not collected this one yet, mark it as collected.

*Once $k$ of the coupons have been marked, the test ends.


Now do the same thing with tokens:


*

*Lay out all $n$ tokens in a row.

*Each trial, select one at random.

*Replace it with a new token.

*Once $k$ of the tokens are new, the test ends.


The difference between the two is just the third step.  However, replacing the third step with "if the token is not new, replace it with a new token" is equivalent, since either way the token is new at the end of the step.
Now for the solution: the details are in the linked article, but here's the gist.  The number of old tokens will either remain the same, or decrease by one with each replacement.  The probability for an old token to be replaced when there are $i$ new tokens is just $\frac{n-i}{n}$, the number of old tokens over $n$.
Therefore the expected number of trials for the number of new tokens to increase from $i$ to $i+1$ is one over the probability, $\frac{n}{n-i}$.  Since expectations add linearly, we have the expected time for the number of new tokens to increase from $0$ to $k$ as:
$$
\sum_{i=0}^{k-1}\frac{n}{n-i}=n\left(H_{n}-H_{n-k-1}\right)\approx n\log\frac{n}{n-k-1}\approx -n\log f
$$
Where $f$ is the desired fraction of new tokens, equal to $\frac{n-k}{n}$.  You can compute the variance in a similar way, see the article for details.
