A real world word problem from my life:
I often check out books and DVDs from my local library. The standard check-out period is three weeks. Using the library's website, I can renew any checked out item at any time before it's due to extend the due date to three weeks after the time of renewal. I am allowed to renew an item twice before I must return it.
This encourages me to renew items only when they are near their due dates so that I can get the maximum amount of time with my items before running out of renewals. However, the rule is I can't renew an item if another library patron places a hold on it. If someone does, I must return the item by its current due date. This encourages me to renew items early before anybody has a chance to place a hold on it.
So if I renew too early, I won't extend the initial three week check-out period by very much. If I renew too late, my item has a greater chance of acquiring a hold, in which case I won't extend the initial check-out period at all.
So that leads to the following question: When during a given three week check-out period is the best time for me to renew an item so that I can keep the item for the longest possible time with the lowest risk that a hold will be placed on it before I can renew?
I suppose we may assume the probability on any given day that a checked-out item of mine will get a hold placed on it is constant and independent of which day it is during the three week period. Beyond that I have no idea what the actual value of that probability is, except that I know from experience that, for a popular item, it is pretty likely that a hold will get placed on it within, say, $10$ days after I check it out.
I'd be interested if anyone can answer my question in general where the probability per day of a hold is $p$. Intuitively, if $p$ is small, then I should renew late; if $p$ is large, then I should renew early.
Additionally, I'm also interested if anyone can offer some good estimates of what $p$ might actually be either using my own (very rough) description, or their own experience or analysis.
First assume that I may extend only once by $n$ days.
If I have held the item for $1\le k\le n$ days (since the beginning or my last successfull renewal), and I try to extend, then this will succeed with probability $(1-p)^k$ and hence my total time (since the beginning or my last successfull renewal) will be $=n+k$ with probability $(1-p)^k$ and $=n$ with probability $1-(1-p)^k$. Hence the expected value is $n+k(1-p)^k$, and I want to maximize this. Clearly, $k+1$ is better than $k$ iff $(k+1)(1-p)^{k+1}>k(1-p)^k$, i.e., $k<\frac1p-1$. Hence the (or a) best $k$ is
In other words, $k$ is given by $\frac1{k+1}\le p<\frac1k$ if possible.
At any rate, this will give me an expected time of $n'= n+k(1-p)^k$. Note that if the optimal $k$ is $\gg1$ (and $p$ not much smaller than $\frac1n$) then we will have $n'\approx n+\frac ke$.
Next assume we still have two attempts to extend by $n$ days available. If I have held the item for $1\le k'\le n$ days and try to extend, this will again succeed with $(1-p)^{k'}$. but as the extension will be $n'$ (in expectation9 instead of just $n$, the total expected lease time will be $n$ with probability $1-(1-p)^{k'}$ and $k'+n'=n+k'+k(1-p)^k$ with probability $(1-p)^{k'}$, i.e., $$n+(1-p)^{k'}(k'+k(1-p)^k). $$ This time, $k'+1$ is better than $k'$ iff $ \frac1p-1-k(1-p)^k>k'$. Hence we will pick $$k'=\left\lceil \frac1p-1-\left\lceil\frac1p-1\right\rceil^{\vphantom|}(1-p)^{\left\lceil\frac1p-1\right\rceil}\right\rceil $$ for "moderate" $p$, but $$ k'=\min\left\{\left\lceil\frac1p-1-n(1-p)^n\right\rceil,n\right\} $$ for small $p<\frac1n$.