Expected Workload

Question

I can produce 1 widget per day. I have a full materials bin which allows me to produce exactly N widgets. On a given day my bin may be refilled (so I again have the capacity to make N widgets) with probability P. This refill can only happen once on a given day. What is the average number of days I work until I have used all my materials (how many widgets will I make on average)?

Answer 1

Here's an extended hint.

The only way to be depleted is if the final $N$ days of a period are not replenished. The probability of that happening is $(1-P)^N$. Moreover, the day immediately before those final $N$ must be a replenish day (otherwise you would be depleted earlier), and this happens with probability $P$. So we are certain that the "end game" or termination criterion is $N+1$ days in which a replenishment day is followed by the final $N$ days having no replenishment. So there will be a factor of $P(1-P)^N$ for all sequences longer then $N$. (The probability for terminating in exactly $N$ days is of course $(1-P)^N$.

(We see immediately that the minimum number of days of working is $N$. After all, that's how many days we have parts at the beginning.)

Now we have to consider longer sequences. Let's call the full candidate length of days $k$, and define $k_s = k - (N+1)$ (for the preliminary sequence). We will be working for the full $k$ days so long as we have any number of days before the final $N+1$ so long as there is no consecutive set of $N$ days with no replenishment. (That ensures we're still working $N+1$ days from the end.) Thus we are interested in the $k_s = k-(N+1)$ "non-terminating" days.

Let's call $k_r$ the number of replenished days (in the "non-terminating" days) and $k_n$ the number of non-replenished days. Of course $k_r + k_n = k_s$. It is a straightforward application of the binomial theorem to specify the probability of getting any given number of $k_r$ (and thus $k_n$) of the $k_s$ days. We also know (from the binomial theorem) what the probability of that sequence will be.

The tricky part is to subtract off the anomalous "terminating" sequences occuring within the $k_s$ days, that is, ones that have $k_u \geq 5$. You need to use combinatorics to find this value (and then its probability, which is straightforward).

At the end, you'll have an expression for the probability of having a sequence of length $k_s$, and thus the full duration of $k$. Call that probability $P_k$. To find the average number of days, calculate:

$${\cal E}(x) =\sum\limits_{k= N+1}^\infty k P_k P(1-P)^N$$

Hope this helps.