Imagine the following. You are a borrower of books from a library. Books are normally due back 14 days after they have been borrowed but you are allowed to renew your loan (once only) for an additional 14 days provided that no one else has requested the book. You don’t have to wait until the end of the loan period to renew the book but if you renew it part way through the initial 14 days then you will only get an additional 14 days from the point of renewal. So, if you get nervous about someone else requesting the book after you’ve had it for only 6 days, and you renew it on day 6 (assuming you can, of course), then you will be able to keep the book for a total of 20 days—the six days that have gone plus an additional 14 days. On the other hand, if someone requests the book at any time prior to you renewing it, then you will be able to keep it for only the initial 14 days.
If you’ve borrowed “A History of the South-Moldovian Peasant Worker’s Revolution” (in 15 exciting volumes) and you think that it’s unlikely to appeal to anyone else, then you might simply wait out the 14 days and see if you can renew the book at the end, in the expectation of being able to keep it for 28 days in total. Contrarily, if you notice that the book rockets into the best-seller list only a few days after you’ve borrowed it, then you might try to renew it after only four days, in the hope that you might at least be able to hold onto your reading matter for a total of 18 days rather than just fourteen.
So, here’s the problem: is there an optimal day on which to (try to) renew your loan, and if so, what day? Of course, the problem isn’t sufficiently well specified in what I’ve already described, so let me be more specific and introduce some terminology that should at least make talking about the problem somewhat easier.
Let’s say that the loan period is L-days and let’s designate the days of the loan (from first to last) as dL-1, dL-2 … d2, d1, d0. To make the renewal and requesting processes a bit more specific, assume that on any day, and prior to midnight (00:00 hrs) on the following day, you can register your wish to renew the book. Likewise, another reader can register their request for the book. Assume that requests take precedence over wishes to renew. If, on day dL-n, there is a registered request then you will have to return the book at the end of d0. On the other hand, if there is no registered request and you have registered an intention to renew, then you will be able to keep the book for a total of L+n days. Finally, assume that you know, a priori, the probability of a request for the book being registered on any particular day, and denote the probabilities as pL-1, pL-2 … p2, p1, p0.
When should you try to renew the book? Another way of putting the question is, can you describe an appropriate algorithm for deciding, on any particular day, whether you should try to renew the book on that day? I’d really like to know the answer!