next up previous contents
Next: Stochastic Dynamic Programming Up: A Tutorial on Dynamic Previous: The Traveling Salesperson Problem

Nonadditive Recursions

Not every recursion must be additive. Here is one example where we multiply to get the recursion.

A student is currently taking three courses. It is important that he not fail all of them. If the probability of failing French is tex2html_wrap_inline1154 , the probability of failing English is tex2html_wrap_inline1156 , and the probability of failing Statistics is tex2html_wrap_inline1158 , then the probability of failing all of them is tex2html_wrap_inline1160 . He has left himself with four hours to study. How should he minimize his probability of failing all his courses? The following gives the probability of failing each course given he studies for a certain number of hours on that subject, as shown in Table 6.

Table 6: Student failure probabilities.

(What kind of student is this?) We let stage 1 correspond to studying French, stage 2 for English, and stage 3 for Statistics. The state will correspond to the number of hours studying for that stage and all following stages. Let tex2html_wrap_inline1084 be the probability of failing t and all following courses, assuming x hours are available. Denote the entries in the above table as tex2html_wrap_inline1168 , the probability of failing course t given k hours are spent on it.

The final stage is easy:


The recursion is as follows:


We can now solve this recursion:

Stage 3.


Stage 2.


So, the optimum way of dividing time between studying English and Statistics is to spend it all on Statistics.

Stage 1.


The overall optimal strategy is to spend one hour on French, and three on Statistics. The probability of failing all three courses is about 29%.

Michael A. Trick
Sun Jun 14 13:05:46 EDT 1998