## Unbiased rack of books

Albert is opening a new library. He wants to keep a special rack of books facing the entrance to give the visitors a glimpse of the kinds of books it has. This special rack can hold only 10 books at a time. Every time a new book arrives at the library, he needs to decide whether to add it to the special rack or just place it in one of the regular racks in the library. A book is removed from this rack only if Albert decides to add a new book to it.

He wants to ensure that at any point in time, each book that has ever arrived at the library will be equally likely to be on the special rack. How is he going to do this?

[SOLVED]

#### Vikram Agrawal solved this puzzle:

For $$10$$ books or less, all books will be placed on the special rack. For $$n$$ books $$(n \geq 10)$$ that have arrived in the library, the probability of each book being on the special rack is $$\frac{10}{n}$$.

Now if an $$(n + 1)$$th book arrives, the new probability of each book being on the special rack should be $$\frac{10}{n + 1}$$, so the new book should be added to the special rack with a probability of $$\frac{10}{n + 1}$$. This can be done by generating a random number between $$1$$ and $$n + 1$$ and adding the new book to the special rack if and only if the number is less than $$10$$. While adding the new book, an old book on the special rack should be picked with a probability of $$\frac{1}{10}$$ and removed.

Let us calculate the probability of an old book being on the rack after the $$(n + 1)$$th book arrives. The probability that $$(n + 1)$$th book is added to the special rack is $$\frac{10}{n + 1}$$. If $$(n + 1)$$th book is being added to the special rack, the probability that an old book on the rack would not be replaced by the $$(n + 1)$$th book is $$\frac{9}{10}$$. The probability that an old book is still on the rack when $$(n + 1)$$th book arrives is $$\frac{10}{n}$$. So, the probability that an old book would not be replaced by $$(n + 1)$$th book when it arrives is the product of these three probabilities, i.e.

$\left(\frac{10}{n + 1}\right) \left(\frac{9}{10}\right) \left(\frac{10}{n}\right).$

Similarly, the probability that an old book remains on the rack when the $$(n + 1)$$th book arrives but is not added to the rack is

$\left(\frac{n + 1 - 10}{n + 1}\right) \left(\frac{10}{n}\right).$

We get the probability of an old book being on the rack when the $$(n + 1)$$th book arrives by adding these two probabilities.

\begin{align*} & \left(\frac{10}{n + 1}\right) \left(\frac{9}{10}\right) \left(\frac{10}{n}\right) + \left(\frac{n + 1 - 10}{n + 1}\right) \left(\frac{10}{n}\right) \\ & = \left(\frac{9}{n + 1}\right) \left(\frac{10}{n}\right) + \left(\frac{n + 1 - 10}{n + 1}\right) \left(\frac{10}{n}\right) \\ & = \left(\frac{n}{n + 1}\right) \left(\frac{10}{n}\right) \\ & = \frac{10}{n + 1}. \end{align*}

Hence, with this method the probability of each book being on the special rack is $$\frac{10}{n + 1}$$ when the $$(n + 1)$$th book arrives.

#### Gemini6Ice solved this puzzle:

When the $$n$$th book arrives in the library, sample a random integer $$x$$ between $$1$$ and $$n$$ with uniform distribution. If $$x$$ is between $$1$$ and $$10$$, inclusive, replace the $$x$$th book with the new book.

#### Mark Brader solved this puzzle:

The probability is $$\frac{10}{n}$$ for any book to be on the special rack after $$n$$ books have arrived. This can be shown by induction.

The base case is trivial. $$n = 10$$ corresponds to the probability $$\frac{10}{n} = 1$$ for each book.

Now assume that before the $$n$$th book arrives, the probability of any book being on the rack is $$\frac{10}{n - 1}$$ for each other book. For the $$10$$ books then on the rack, there is a probability $$\frac{10}{n}$$ that one of them will be replaced upon the arrival of the $$n$$th book. Therefore for each particular book on the rack, there is a probability of $$\frac{1}{n}$$ that it will be replaced, and therefore of $$\frac{n - 1}{n}$$ that it will not.

Therefore the probability of any book being on the rack is

$\left(\frac{10}{n - 1}\right) \left(\frac{n - 1}{n}\right) = \frac{10}{n}.$

### Credit

This puzzle is taken from folklore.