Where to look after looking and not finding

In May 1968 the United States submarine Scorpion failed to arrive at Norfolk, Virginia, and disappeared somewhere in the Atlantic. The Navy’s search was directed by John Craven, who did something unusual for the time: he asked experts to bet on scenarios for the loss, combined their bets into a map of probabilities over the sea floor, and directed the search to the cells of that map in an order chosen by Bayes’ theorem. The wreck was found in October, about 200 metres from the cell his map had rated most likely. Forty years later, the same method found the wreck of Air France flight 447 in the South Atlantic, after four searches over two years — and the reason the earlier searches had failed was a mistake in exactly the kind of calculation this essay draws.

The problem is old and the mathematics is a direct use of Bayes’ theorem as a picture of rectangles. An object lies in one of many places, each with a probability. A search of a place may or may not find it if it is there. After a search that finds nothing, how should the probabilities change, and where should the next search go?

What a failed look does #

Divide the search area into cells, with $p_i$ the probability that the object is in cell $i$. A look in cell $j$ finds the object, if it is there, with probability $d_j$ — the detection probability, which depends on visibility, depth, equipment and luck. Suppose the look finds nothing. By Bayes’ theorem the probability that the object is in cell $j$ becomes

$$p_j' = \frac{p_j(1 - d_j)}{1 - p_j d_j},$$

and every other cell is scaled up by the same denominator, $p_i' = p_i/(1 - p_j d_j)$. The denominator is the probability that the look fails, which is $1 - p_j d_j$ because the look succeeds only if the object is there and is seen.

The figure shows how much a failure is worth. A thorough look, $d = 0.9$, that finds nothing in a cell that held half the probability drops it to 9%. A poor look, $d = 0.3$, drops it only to 41%. The probability removed goes to all the other cells in proportion to what they held, which is why a failed search makes every unsearched place a little more likely. In the language of decibans, a failed look in cell $j$ is evidence against “the object is in $j$” with weight $10\log_{10}(1/(1 - d_j))$ decibans: ten for a thorough look, one and a half for a poor one, whatever the prior.

In the hero, sixty looks have redrawn the map. They went mostly to the good-visibility parts of the two areas of suspicion, and those parts have faded, while the rough-water box, where looks are weak evidence, now holds a larger share. The object has been found on one of those sixty looks with probability 0.425, and given that it has not, the map on the right is what the searchers should believe.

Where the next look should go #

The tempting rule is to look in the most likely cell. It is wrong when cells differ in visibility, because the most likely cell may be one where a look rarely succeeds. The right quantity is the chance of finding the object on the next look, which is $p_i d_i$: the probability it is there times the probability of seeing it if it is.

The curves are exact. Each look multiplies the remaining chance in its cell by $1 - d$, and the chance found so far is the sum of what has been removed, so no simulation is needed. Looking where $p \times d$ is highest finds the object with probability 0.577 after 100 looks; looking where $p$ is highest, 0.545; sweeping row by row, 0.406. After 400 looks the first two are at 0.941 and 0.936 and the sweep at 0.833. The greedy rule wins throughout, and the computation checks that it has the smallest expected number of looks of the three.

David Blackwell showed in the early 1960s that when every look costs the same, the greedy rule is the best of all rules: it minimises the expected number of looks until the object is found. When looks cost different amounts, the rule is to maximise $p_i d_i / c_i$, the chance of success per unit cost. The proof is an exchange argument of the kind used for Gittins’s index: any rule that makes a look with a lower ratio before one with a higher can be improved by swapping them, because the posterior after both looks is the same in either order and the higher-ratio look succeeds sooner.

When to give up #

Every search has a cost, and a search that might go on for ever needs a rule for stopping. If finding the object is worth $V$ and a look in cell $i$ costs $c_i$, the next look is worth making only if its expected gain exceeds its cost, $p_i d_i V > c_i$, at the best cell. That one-step rule is a good guide but not always the best one. A failure lowers the probability of the cell searched and raises every other, so a look elsewhere can be worth more after a failure than it was before, and a search that stops the moment the best single look is unprofitable may stop too early when several cheap looks together would pay. The full question compares the cost of all the looks still to come with the chance that they succeed, which makes it a problem of optimal stopping, solved by working backwards from a horizon; for searches with a fixed set of cells and costs it can be computed, and its answer is never to stop sooner than the one-step rule says.

Real searches add a complication the rule ignores: the value of finding the object changes with time, for a survivor in the water or a flight recorder whose battery runs down. Then the threshold rises as the search goes on, and the stopping question becomes the kind of race against a deadline that the coin-tossing game posed in a simpler form.

Where the prior comes from #

The calculation starts from a map, and the map is the least objective part of it. For the Scorpion, Craven’s map came from scenarios — an explosion, a loss of control, a torpedo turned against the boat — each given a probability by consulted experts and each translated, through the physics of a sinking hull, into a spread of positions on the sea floor. For Air France 447 the prior came from the last reported position, the aircraft’s range and the drift of debris recovered from the surface, run backwards through ocean current models. In both cases the prior was wide and uncertain, and Bayes’ theorem’s contribution was not to supply it but to say exactly how each failed search should reshape it.

There is a subtle point about what counts as evidence, which the two children and the sentence made in another setting: the information carried by a failure depends on how the search was conducted, not only on its result. A sonar sweep that was planned, executed to specification and reported nothing is one kind of evidence; a passing ship that happened not to notice anything is another, with a much lower detection probability. Entering both with the same $d$ is the error that the overconfident search figure exaggerates.

Dividing effort finely #

Bernard Koopman, who founded search theory for the United States Navy’s anti-submarine campaign in the Second World War, worked with continuous effort instead of discrete looks. If a cell is searched with effort $z$, the chance of missing an object there is $e^{-z}$, a natural model when the effort is many independent glimpses. A fixed total effort $Z$ is to be divided among the cells to maximise the chance of detection, $\sum p_i(1 - e^{-z_i})$.

The solution is a water level. Searching a cell with effort $z_i$ leaves it holding $p_i e^{-z_i}$, and the optimum makes this the same for every searched cell, with the unsearched cells already below that level. In the figure the four likeliest of eight cells are searched, with efforts from 1.21 down to 0.30, and the other four are left alone; the chance of detection is 0.4435, against 0.4142 if effort is spread in proportion to probability and 0.3127 if it is spread evenly. The same water-filling solves the problem of dividing power among noisy channels to maximise capacity, where the noise floor plays the part of the prior.

The exponential law has a reason. If an observer sweeps a region along tracks laid down at random, each covering a small fraction of the area, the chance that none of many independent sweeps passes over the object is a product of many factors each close to one, which tends to $e^{-z}$ with $z$ the total area swept divided by the area of the region. Koopman called this the random-search formula, and it is pessimistic on purpose: tracks laid in a careful parallel pattern miss less, and a perfectly planned sweep of effort $z \le 1$ would find the object with probability $z$ rather than $1 - e^{-z}$.

The level structure has a practical meaning. After an optimal search every searched cell has the same remaining probability, so if the search fails, the next increment of effort should be spread over all of them, and over any cell whose probability has just reached the level. Search plans are drawn this way: the effort contours on a map follow the probability contours, cut off at a level.

A search that trusts its eyes too much #

Every number in the calculation above depends on the detection probabilities, and they are the hardest numbers to know. A search that overrates its own detection chance in some area will conclude, after a few failures there, that the object is not there, and will move on to cells that are in fact less likely.

In the figure the difference is modest, because the rough box holds only a third of the prior. The real case was not modest. Air France 447 went down in June 2009, and the first searches listened for the underwater locator beacons on its flight recorders. They searched the area near the last known position, heard nothing, and treated that as strong evidence that the wreck was elsewhere — as it would have been, had the beacons been working. Three further searches in 2009 and 2010 covered wider areas without success. In 2011 a Bayesian reanalysis by the firm Metron, founded by search theorists, allowed for the possibility that both beacons had failed, which lowered the detection probability of the early listening searches. The posterior shifted back towards the area near the last known position, and the wreck was found there within a week of the search resuming, in April 2011.

The failure was not in Bayes’ theorem but in the list of hypotheses it was given, the subject of being certain of a coin that is not there. A hypothesis that the beacons might have failed, given even a modest prior, would have kept probability in the area that was in fact the right one.

Failure moves belief into the hard places #

As failures accumulate, probability drains out of the places where looks are effective and collects in the places where they are not, even though those places are searched too. In this example the rough-water box rises from 33% to 37% over three hundred failed looks, while the chance the search would already have succeeded climbs past 90%. The drift is slow here because the greedy rule keeps returning to the box’s edge. It is the arithmetic behind a common experience in real searches: the longer a search goes on without success, the more likely it is that the object is somewhere the search is poor at seeing, and the more of the remaining effort must be spent there despite the poor odds.

The likeliest place is the wrong place to look #

The surprise is that the most likely place is often the wrong place to look. It sounds paradoxical that a searcher who believes an object is probably in one place should look in another, and it is a misunderstanding that the door that was not opened shares: what matters is not where the prize probably is, but how the next action changes what can be learned. Looking where $p \times d$ is highest trades probability for visibility, and Blackwell’s theorem says that trade is exactly right.

A second surprise is that a failed search is good news for every place it did not search. The probabilities must sum to one, so evidence against one cell is evidence for all the others in proportion, and a map redrawn after a failure is brighter everywhere except where the search went.

A made-up sea with known sensors #

The grid, the prior and the detection probabilities are made up for the illustration; real searches estimate them from drift models, expert judgement and sensor tests, with large uncertainties that the figures ignore. The object is assumed not to move, and each look to be independent of the others given the object’s location; drifting objects and correlated misses, such as a beacon that has failed for good, require richer models. The account of the Scorpion and Air France 447 searches is quoted from published accounts, simplified, and not reconstructed here.

Posteriors computed, Koopman quoted #

Computed here: the prior from two Gaussian hot spots and a floor, normalised; every posterior by Bayes’ rule, checked to sum to one; the exact chance of having found the object after each look under three rules, computed by tracking the remaining mass in each cell, with the greedy rule’s expected number of looks the smallest; Koopman’s allocation by bisection on the water level, with the effort checked to sum to the total and the result compared with proportional and even allocations; and the overconfident search, using its believed detection chances for the posterior and the true ones for the chance found.

Quoted: Blackwell’s theorem; Koopman’s work of 1946 and 1957; the Scorpion search of 1968 under John Craven; the Air France 447 searches and Metron’s reanalysis of 2011.

Still open: searching for something that moves #

When the object moves — a drifting life raft, a submarine trying to avoid detection — the search becomes a game or a control problem over time, and the clean results fail. For an object moving as a Markov chain, the optimal search plan can be computed by dynamic programming in small cases, but no simple index rule like Blackwell’s is optimal in general, and the computation grows exponentially with the number of cells and steps. For an evading object the search is a game whose value is known only for special geometries. Lawrence Stone, whose textbook defined the field, has written that the gap between what is optimal and what can be computed is the central practical problem of search theory, and in most realistic settings it remains open.

Look where finding is likeliest #

After a look that finds nothing, Bayes’ rule scales the searched cell’s probability by $(1 - d)/(1 - pd)$ and raises every other cell, so every search redraws the map. The best next look is where the chance of finding the object on that look, $p \times d$, is highest — not where the object is likeliest — and over 400 looks on this map that rule beats the alternatives at every step. With continuous effort the optimum is a water level, and a search that overrates its own detection chance writes off the hard places too early, the mistake that kept the wreck of Air France 447 hidden until the arithmetic was redone.