A MINIMAX OPTIMAL STOP RULE IN RELIABILITY CHECKING

Consider a machine, which may or may not have a defect, and the probab ility q that this machine is defective is unknown. In order to determi ne whether the machine is defective, it is tested. On each test, the d efect is found with probability p, if it has not been found yet. Perfo rming n tests costs c(n) dollars and there is a fine of 1 dollar if th ere is a defect and it is not found on the tests. When should we stop testing, in order to minimize the cost? This problem is treated in a m inimax setting: we try to find a strategy that works well, even for 'b ad' q's. It turns out that the minimax optimal stop rule can be unexpe ctedly complicated. For example; if p = 1/2 and c(n) = cn = 0.25n, the n the optimal rule is to start by performing one test. If a defect is found we stop, otherwise we perform a second test. If a defect is foun d, then again we stop, else toss a coin and stop if this shows heads. If we still have not stopped, a third and last test is performed.