5D Library › Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices · 中文
Chapter 3 Bayesian Search: Where to Look, and What Not Finding Means
From anti-submarine warfare to search theory
During the Second World War the mathematician Bernard Koopman, working with the US Navy’s operations research group on anti-submarine warfare, studied how limited numbers of aircraft and ships could find submarines in large areas of ocean. After the war he set the work out in three papers on “The Theory of Search”, published in Operations Research in 1956–1957: the first dealt with the relative motion of searcher and target, the second with the probability of detection, and the third with how to allocate a limited search effort, given a known distribution of the target’s position, so as to maximise the probability of detection (Koopman 1956, 1957). Stone’s Theory of Optimal Search (1975) gave the field a systematic account (Stone 1975).
Search theory has three basic ingredients. The first is the prior: where the target might be, and with what probability in each place. The second is the detection function: if the target is in a given place, the probability of detecting it with a given search effort there; where the seabed is rugged, the water deep or the weather bad, the same effort detects with lower probability. The third is updating: searching a place without finding the target does not show that it is not there; it lowers the probability that it is there and raises the probability everywhere else.
Calculation
Divide the search area into cells; let be the probability that the target is in cell , and the probability that one search of detects the target if it is there. After one unsuccessful search of , Bayes’s rule gives That search detects the target with probability , so the greedy rule for “where to look next” is: choose the cell with the largest . For the discrete search problem in which one cell is searched at a time and each cell has a fixed detection probability, this rule can be shown to minimise the expected number of searches (Stone 1975).
The rule has two implications. First, “look where it is most likely to be” is not always right: a cell with a high probability that is hard to search may be worth less than one with a slightly lower probability that is easy to search. Second, not finding is information: every unsuccessful search pushes probability from easy places towards hard ones, so that, following the rule, the search turns of its own accord towards areas that have been “searched but not cleared”.
Searching a grid
Calculation
An invented sea area. The prior mixes three scenarios, as is common in real search planning: uniform within 8 cells of the last known position (weight 0.35), normal around the last known position (0.35), and normal around a point found by reverse drift (0.30). The detection probability is 0.8 on smooth seabed and 0.4 on rugged seabed in the east and along a ridge. Ten searches a day. Three plans are compared: (A) always search the cell with the largest ; (B) always search the cell with the largest , ignoring detection probability; (C) sweep cell by cell outwards from the last known position, ignoring the prior. The program computes, for each plan, the probability of having found the target by day (in expectation over the prior) and the mean number of days needed (truncated at day 120).
# Bayesian search, invented 20 x 20 sea area, 10 looks a day; prior and detection
# probabilities as in the text. Plans: (A) largest p_c d_c; (B) largest p_c; (C) sweep.
import math
N, LKP, DRIFT, LOOKS = 20, (8, 10), (12, 7), 10
CELLS = [(x, y) for x in range(N) for y in range(N)]
def prior():
inside = [c for c in CELLS if math.dist(c, LKP) <= 8]
p = {c: 0.0 for c in CELLS}
for w, m, s in ((0.35, LKP, None), (0.35, LKP, 3.0), (0.30, DRIFT, 2.5)):
part = {c: 1.0 if s is None else math.exp(-math.dist(c, m) ** 2 / (2 * s * s))
for c in inside}
tot = sum(part.values())
for c, v in part.items():
p[c] += w * v / tot
return p
def detect(c):
return 0.4 if c[0] >= 13 or abs(c[0] - c[1] - 2) <= 1 else 0.8
def update(p, c): # unsuccessful look at c (Bayes's rule)
miss = 1 - p[c] * detect(c)
for k in p:
p[k] /= miss
p[c] *= 1 - detect(c)
return miss
def run(plan, days):
p, found, curve, snaps, k = prior(), 0.0, [], {}, 0
sweep = sorted((c for c in CELLS if math.dist(c, LKP) <= 8),
key=lambda c: (math.dist(c, LKP), c))
for day in range(1, days + 1):
for _ in range(LOOKS):
if plan == "A":
c = max(CELLS, key=lambda c: p[c] * detect(c))
elif plan == "B":
c = max(CELLS, key=lambda c: p[c])
else:
c = sweep[k % len(sweep)]; k += 1
found += (1 - found) * (1 - update(p, c))
curve.append(found)
if day in (1, 5, 20):
snaps[day] = dict(p)
return curve, snaps
if __name__ == "__main__":
p0 = prior(); top = sorted(p0.values(), reverse=True)
print(f"prior: {sum(v > 0 for v in p0.values())} cells possible;"
f" top 10 hold {sum(top[:10]):.3f}, top 50 hold {sum(top[:50]):.3f}")
print("P(found by day t) t=1 t=5 t=10 t=20 t=40 mean days")
for plan, name in (("A", "A largest p x d"), ("B", "B largest p"), ("C", "C sweep")):
curve, _ = run(plan, 120)
cols = "".join(f" {curve[t - 1]:.3f}" for t in (1, 5, 10, 20, 40))
print(f" {name:25s}{cols} {sum(1 - f for f in curve) + 1:6.1f}")
snaps = run("A", 20)[1]
rough = lambda p: sum(v for k, v in p.items() if detect(k) < 0.5)
print("plan A, no success: rough-cell mass after 0/1/5/20 days: " + " ".join(
f"{rough(p):.3f}" for p in (p0, *snaps.values())))
tops = [(max(CELLS, key=lambda c: p[c]), max(p.values())) for p in snaps.values()]
print(" top cell after 1/5/20 days: " + ", ".join(f"{c} {v:.4f}" for c, v in tops))
# prior: 197 cells possible; top 10 hold 0.119, top 50 hold 0.473
# P(found by day t) t=1 t=5 t=10 t=20 t=40 mean days
# A largest p x d 0.088 0.311 0.484 0.694 0.892 17.5
# B largest p 0.067 0.287 0.459 0.672 0.888 18.3
# C sweep 0.071 0.262 0.451 0.665 0.850 21.3
# plan A, no success: rough-cell mass after 0/1/5/20 days: 0.349 0.382 0.465 0.559
# top cell after 1/5/20 days: (11, 8) 0.0139, (12, 9) 0.0158, (10, 7) 0.0136The prior allows 197 cells; the 10 most probable hold only 0.119 and the top 50 hold 0.473. The prior is quite diffuse, and no plan finds the target quickly. Plan A, which searches by , finds the target on the first day with probability 0.088, within ten days with 0.484 and within forty days with 0.892, taking 17.5 days on average; plan B, which looks only at , takes 18.3 days; plan C, which ignores the prior and sweeps outwards, takes 21.3 days and reaches only 0.850 by day forty. The differences here are modest because all three scenarios concentrate the prior near the last known position, so the order of plan C happens to follow the prior roughly; the further the prior departs from the searcher’s intuition (for instance, when drift carries the target far from the last known position), the more it costs to ignore it.
The last part of the program shows that not finding is information: rugged cells hold 0.349 of the prior, and after 1, 5 and 20 days of unsuccessful searching under plan A they hold 0.382, 0.465 and 0.559. The most probable cell also moves, from (11, 8), near the reverse-drift point, to (12, 9) and then to (10, 7).
Scorpion and AF 447
Evidence
The submarine Scorpion (1968). The US nuclear submarine Scorpion was lost in the Atlantic in 1968. Richardson and Stone reported the operations analysis of the search in 1971: they constructed nine loss scenarios, gave each a credibility weight and generated a prior distribution for the wreck’s position by Monte Carlo; during the search they updated the target distribution according to the effectiveness of each search and used it to decide where to search next. The wreck was eventually found within 260 yards of the cell with the highest prior probability (Richardson and Stone 1971). Stone himself spent about six weeks on scene near the Azores doing the analysis.
Evidence
AF 447 (2009–2011). On 1 June 2009 Air France Flight 447, from Rio de Janeiro to Paris, disappeared in stormy weather over the Atlantic. Over the next two years four phases of search — a surface search, a passive acoustic search for the underwater locator beacons in June–July 2009, and side-looking sonar searches in August 2009 and April–May 2010 — failed to find the wreckage. The French accident investigation agency asked Stone and colleagues to analyse where it lay (Stone et al. 2014). Within a circle of 40 nautical miles around the last known position, they built a prior from three mixed distributions: uniform within the circle; normal with a standard deviation of 8 nautical miles, based on nine loss-of-control accidents; and a distribution obtained by reverse drift of the recovered bodies, with weights 0.35, 0.35 and 0.30; they then updated it by the detection probability of each phase of the search. The effectiveness of the passive acoustic search depended on whether the two beacons were working, and because there were doubts about whether the beacons could survive the impact, they produced a posterior for the case in which both beacons had failed. The 2011 search started at the centre of that distribution and found the wreckage within about a week, in a high-probability area that the passive acoustic search had covered thoroughly. A recovered beacon, connected to a fully charged battery, was later found not to produce a signal. The authors write that it would have been better to put beacon failure and wreck location into one joint distribution.
The lesson of this case is not that “the Bayesian method magically found the wreck” but that one’s estimate of how effective past searches were is itself a hypothesis that needs checking. If the detection probability of past searches is overestimated, the posterior “rules out” the most probable area too early, and all later searching is directed to the wrong places.
Calculation
The same invented sea area illustrates the lesson. Suppose an earlier acoustic search covered every cell within 4 cells of the last known position and, if the beacons work, detects with probability 0.9. Three planners differ on the probability that the beacons work: one trusts the earlier search fully (), one uses a joint model (), and one ignores the earlier search (). Each searches with plan A using his or her own posterior; the truth is either “the beacons failed” or “the beacons worked”. The numbers are illustrative.
# An earlier search that was less effective than assumed (stylised after Stone et al.
# 2014; same invented grid and prior as p04). An acoustic search covered all cells within
# 4 of the last known position, detecting w.p. 0.9 IF the beacons work. Planners give
# "beacons work" probability w = 1, 0.8 (joint model) or 0 and then search by p x d.
import math
N, LKP, DRIFT, LOOKS = 20, (8, 10), (12, 7), 10
CELLS = [(x, y) for x in range(N) for y in range(N)]
def prior():
inside = [c for c in CELLS if math.dist(c, LKP) <= 8]
p = {c: 0.0 for c in CELLS}
for w, m, s in ((0.35, LKP, None), (0.35, LKP, 3.0), (0.30, DRIFT, 2.5)):
part = {c: 1.0 if s is None else math.exp(-math.dist(c, m) ** 2 / (2 * s * s))
for c in inside}
tot = sum(part.values())
for c, v in part.items():
p[c] += w * v / tot
return p
def detect(c):
return 0.4 if c[0] >= 13 or abs(c[0] - c[1] - 2) <= 1 else 0.8
def after_acoustic(p, w):
q = {c: v * (1 - 0.9 * w if math.dist(c, LKP) <= 4 else 1.0) for c, v in p.items()}
tot = sum(q.values())
return {c: v / tot for c, v in q.items()}
def days_to_find(belief, truth, days=200):
b, n, curve = dict(belief), {c: 0 for c in CELLS}, []
for _ in range(days * LOOKS):
c = max(CELLS, key=lambda c: b[c] * detect(c))
miss = 1 - b[c] * detect(c)
b = {k: v / miss for k, v in b.items()}; b[c] *= 1 - detect(c); n[c] += 1
if sum(n.values()) % LOOKS == 0:
curve.append(sum(truth[c] * (1 - (1 - detect(c)) ** n[c]) for c in CELLS))
return 1 + sum(1 - f for f in curve), curve
if __name__ == "__main__":
p0 = prior()
area = sum(v for c, v in p0.items() if math.dist(c, LKP) <= 4)
post = 0.8 * (1 - 0.9 * area) / (0.8 * (1 - 0.9 * area) + 0.2)
print(f"prior mass in the acoustic area {area:.3f};"
f" w = 0.8 -> {post:.3f} after the miss")
truths = {"failed": p0, "worked": after_acoustic(p0, 1.0)}
print("mean days to find (to 200) and P(found by day 10)")
print(" planner's w truth: beacons failed truth: beacons worked")
for w in (1.0, 0.8, 0.0):
row = [days_to_find(after_acoustic(p0, w), t) for t in truths.values()]
cols = "".join(f" {m:6.1f} days, {c[9]:.3f}" for m, c in row)
print(f" w = {w:.1f}{cols}")
# prior mass in the acoustic area 0.381; w = 0.8 -> 0.725 after the miss
# mean days to find (to 200) and P(found by day 10)
# planner's w truth: beacons failed truth: beacons worked
# w = 1.0 24.6 days, 0.336 16.3 days, 0.511
# w = 0.8 20.2 days, 0.371 16.8 days, 0.500
# w = 0.0 17.5 days, 0.484 20.3 days, 0.365The acoustic search area holds 0.381 of the prior. After the acoustic search finds nothing, the planner with the joint model lowers the probability that the beacons work from 0.8 to 0.725: not finding is itself evidence that the beacons may have failed.
If the truth is that the beacons failed, the planner who fully trusts the earlier search needs 24.6 days on average and finds the target within ten days with probability only 0.336; the planner who ignores the earlier search needs only 17.5 days, and the planner with the joint model 20.2 days. If the beacons worked, the order is reversed: the trusting planner is fastest (16.3 days), the planner who ignores the search slowest (20.3 days), and the joint model takes 16.8 days. The joint model is best under neither truth but worst under neither, and it loses almost nothing when the beacons worked. This is the “better approach” of which Stone and colleagues wrote: do not treat an uncertain assumption as certain, but let the data update it.
Note
The limits of Bayesian search. How well a search does depends on whether the prior and the detection probabilities are reasonable; two successful cases show that the method can work, not that it always succeeds. Priors usually come from expert judgement and past accidents; Volume 26, Probabilistic Judgement, Brier-Score Calibration and the Statistics of Collective Intelligence, discussed how to check whether such subjective probabilities are calibrated. The programs in this chapter show only the structure, and all their numbers are illustrative.
How animals search: the marginal value theorem and the Lévy-flight debate
The search theory above assumes a single target and a known prior. Foraging ecology studies another kind of search: resources are scattered over many patches, and a forager must decide how long to stay in a patch before leaving and how to move between patches. Each question has a famous model; one conclusion is robust, the other is still disputed.
Evidence
Charnov’s marginal value theorem (1976). Let be the gain a forager obtains by staying time in a patch, increasing but with diminishing returns (the patch is gradually depleted), and let be the average travel time between patches. If the aim is to maximise the long-run average rate of gain and all patches are alike, the long-run rate is , and setting gives an optimal leaving time with
that is, the forager leaves when the marginal rate of gain in the patch has fallen to the average rate for the habitat as a whole, travel time included. In Charnov’s words, the predator should leave the patch it is in when the marginal capture rate in the patch drops to the average capture rate for the habitat (Charnov 1976). Geometrically, is the point where a line drawn from on the time axis touches the gain curve. Two direct predictions follow: the farther apart the patches, the longer a forager should stay in each; and it leaves before the patch is exhausted. Cowie in 1977 let great tits in an aviary forage from cups of food (the patches) and varied the “travel” time between patches with loose or tight lids on the cups; when travel took longer, the birds stayed longer in each patch, in the predicted direction, though on average somewhat longer than the model’s optimum (Cowie 1977). Stephens and Krebs’s 1986 monograph reviews tests of this kind: most support the theorem in direction, while quantitative departures are common (Stephens and Krebs 1986).
Calculation
Take with and . The program finds by bisection and checks that the marginal rate at departure equals the average rate; the last column is the rate obtained by always leaving at whatever the travel time.
# Charnov's marginal value theorem. A patch gives g(t) = G(1 - exp(-r t)); travel between
# patches takes tau. The long-run rate is g(t)/(tau + t); the best leaving time t* solves
# g'(t*) = g(t*)/(tau + t*): leave when the marginal rate falls to the average rate.
import math
G, R = 10.0, 0.5
def g(t):
return G * (1 - math.exp(-R * t))
def dg(t):
return G * R * math.exp(-R * t)
def t_star(tau):
lo, hi = 1e-9, 100.0 # h(t) = g'(t)(tau + t) - g(t) falls from + to -
for _ in range(100):
mid = (lo + hi) / 2
lo, hi = (mid, hi) if dg(mid) * (tau + mid) - g(mid) > 0 else (lo, mid)
return lo
if __name__ == "__main__":
print("marginal value theorem, G = 10, r = 0.5")
print(" tau t* g(t*)/G g'(t*) g/(tau+t*) = best rate rate if leave at t = 2")
for tau in (1, 2, 4, 8):
t = t_star(tau)
best = g(t) / (tau + t)
print(f" {tau:3d} {t:5.2f} {g(t) / G:5.3f} {dg(t):6.3f} {best:6.3f}"
f" {g(2) / (tau + 2):6.3f}")
# marginal value theorem, G = 10, r = 0.5
# tau t* g(t*)/G g'(t*) g/(tau+t*) = best rate rate if leave at t = 2
# 1 1.72 0.576 2.121 2.121 2.107
# 2 2.29 0.682 1.589 1.589 1.580
# 4 3.01 0.778 1.110 1.110 1.054
# 8 3.87 0.856 0.721 0.721 0.632As the travel time rises from 1 to 8, the optimal stay rises from 1.72 to 3.87 and the share of the patch taken at departure from 57.6 % to 85.6 %; in no case is the patch exhausted, and in every row equals . A fixed rule of leaving at loses almost nothing when travel is short (2.107 against 2.121 at , about 0.6 %) but about 12 % when it is long (0.632 against 0.721 at ).
The marginal value theorem is itself a stopping rule: stop as soon as the marginal value of continuing falls below the average value available after giving up. It has the structure of the one-armed bandit of Chapter 5, except that here the gain curve of a patch is known; when the quality of a patch is uncertain, the decision to leave must also weigh the information gained by staying, which is the problem of Chapters 4 and 5.
Evidence
The Lévy-flight foraging hypothesis and its disputes. In 1996 Viswanathan and colleagues analysed data from salt-water immersion loggers on wandering albatrosses, treated each run of dry readings as a flight, reported that flight durations followed a power law, and concluded that albatrosses search by “Lévy flights” (Viswanathan et al. 1996). In 1999 they showed in Nature that when targets are sparse, randomly distributed and revisitable (they reappear after being found), and the forager has no memory and detects only nearby targets, an exponent in the step-length distribution (an “inverse-square” Lévy flight) maximises search efficiency, whereas for targets that vanish once found nearly straight-line motion () is better (Viswanathan et al. 1999). “Animals forage by Lévy flights” was then widely cited.
In 2007 Edwards and colleagues, including several authors of the 1996 paper, re-examined the albatross data (Edwards et al. 2007). The 1996 analysis, at a resolution of one hour, counted every dry run as a flight, but the dry runs at the start and end of each foraging trip often included time when the bird was still on Bird Island, South Georgia; the 14 longest (21 to 99 hours) all came at the start or end of a trip. With these removed, the longest flight fell from 99 hours to 20 and the data no longer showed a power law. In new 2004 data from 20 albatrosses carrying loggers and GPS (1,416 flights at 10-second resolution), flight durations were consistent with a shifted gamma distribution, with an exponential tail for long flights; re-analysing the four deer and bumblebee data sets of the 1999 paper, they found none with evidence for a power law over an exponential. They also proposed comparing power-law and exponential tails by likelihood and Akaike weights instead of fitting straight lines to log–log histograms.
Evidence
The debate is not over. In 2010 Humphries and colleagues analysed movement data from 14 species of open-ocean fish (sharks, tuna, billfish, ocean sunfish and others) and found Lévy-type movement mostly in sparse, less productive waters and Brownian movement mostly on productive shelves and fronts, with some individuals switching between them across habitats (Humphries et al. 2010); in 2012 they analysed wandering and black-browed albatrosses with high-resolution GPS and simultaneously recorded prey captures and concluded that both patterns occur (Humphries et al. 2012). On the other side, Pyke in 2015 argued that the Lévy model ignores directional correlation between steps, is less efficient than more realistic models and lacks convincing empirical support, and that the hypothesis should be abandoned (Pyke 2015); Levernier and colleagues proved in 2020 that in two or more dimensions the way the encounter rate scales with target density does not depend on the Lévy exponent, so tuning changes only a prefactor and the optimal depends on modelling details and can be almost anything; in their two-dimensional model (targets regenerate immediately after being taken) the inverse-square Lévy walk was optimal only in the special limit where each walk restarts right at a target’s edge and the step-length scale is much smaller than a target, and the gain from an optimal Lévy walk is small (Levernier et al. 2020).
Calculation
The program below reproduces the 1999 conclusion in the simplest one-dimensional model: targets are apart, the detection radius is 1, step lengths follow in a random direction, and a step that reaches a target stops there. With revisitable targets the walker restarts 1 unit from the target just found; with one-off targets it restarts midway between two targets. Efficiency is the number of targets found divided by the total path length.
# Levy walks in one dimension (after Viswanathan et al. 1999): targets lambda apart,
# detection radius 1, step lengths l >= 1 with p(l) ~ l^-mu, random direction; a step that
# reaches a target stops there. Revisitable targets: restart 1 from the target just found;
# one-off (destructive) targets: restart midway between two targets.
import random
def efficiency(mu, lam, destructive, finds, rng):
dist = 0.0
for _ in range(finds):
x = lam / 2 if destructive else 1.0
while True:
step = rng.random() ** (-1 / (mu - 1))
left = rng.random() < 0.5
room = x if left else lam - x
if step >= room:
dist += room
break
x += -step if left else step
dist += step
return finds / dist
if __name__ == "__main__":
rng = random.Random(42)
mus = (1.3, 1.5, 1.7, 1.8, 1.9, 2.0, 2.1, 2.3, 2.5)
n = 40000
print("revisitable targets: efficiency relative to the best mu (40,000 finds)")
print(" lambda best mu " + " ".join(f"{m:4.1f}" for m in mus))
for lam in (100.0, 1000.0, 10000.0):
eff = [efficiency(m, lam, False, n, rng) for m in mus]
top = max(eff)
print(f" {lam:6.0f} {mus[eff.index(top)]:4.1f} "
+ " ".join(f"{e / top:4.2f}" for e in eff))
print("one-off targets, lambda = 200: finds per 1,000 units of path")
for m in (1.1, 1.5, 2.0, 2.5, 3.0):
print(f" mu = {m:3.1f}: {1000 * efficiency(m, 200.0, True, 1500, rng):6.2f}")
# revisitable targets: efficiency relative to the best mu (40,000 finds)
# lambda best mu 1.3 1.5 1.7 1.8 1.9 2.0 2.1 2.3 2.5
# 100 1.7 0.85 0.94 1.00 0.98 0.94 0.93 0.88 0.81 0.68
# 1000 1.8 0.59 0.79 0.92 1.00 0.97 0.98 0.89 0.74 0.56
# 10000 1.9 0.35 0.58 0.82 0.90 1.00 0.92 0.87 0.60 0.39
# one-off targets, lambda = 200: finds per 1,000 units of path
# mu = 1.1: 8.92
# mu = 1.5: 5.94
# mu = 2.0: 2.84
# mu = 2.5: 1.08
# mu = 3.0: 0.45With revisitable targets the best in this run is 1.7 for , 1.8 for and 1.9 for . With other random seeds the best value can shift by 0.1 or 0.2 (at , 1.8 and 1.9 are practically tied), but in each of the 12 seeds we tried it never decreased as grew: the sparser the targets, the closer the optimum to 2, in line with the 1999 result, but even in an idealised one-dimensional model is a limit for very sparse targets. The efficiency curve is flat near its maximum (at every from 1.8 to 2.0 is within 97 % of the best), and differences of a few per cent between neighbouring values lie within the simulation error (about 1 % to 3 %). With one-off targets the conclusion is quite different: at the walker finds 8.92 targets per 1,000 units of path and at only 2.84; the closer to straight-line motion, the better.
“Lévy flight is the optimal search strategy” is therefore not a general result. It depends on whether targets regenerate, how sparse they are, the dimension and the forager’s perceptual range; and “animals really do use Lévy flights” is a separate empirical question, on which the albatross case shows that one slip in data processing is enough to manufacture a power law. The case is also an instance of the problem of testing power laws discussed in Books 20 and 25: a straight line on a log–log plot does not mean the data come from a power law.
Hypothesis · not established · A marginal-value rule for testing lanes
Hypothesis (untested). The author conjectures that teams testing several lanes at once who apply the marginal value theorem — “move resources out of a lane when its marginal return falls below the average return of the whole portfolio, counting the time needed to switch” — obtain a higher cumulative return for the same total effort than teams that rotate lanes on a fixed schedule. A testable prediction: in a multi-period simulated business game with switching costs and return measures registered in advance, the group allocating time by the marginal-value rule earns a higher cumulative return than the group rotating on a fixed schedule; if the difference between the groups lies within the pre-specified smallest effect of interest, the hypothesis loses its support.
From the seabed to “search” inside organisations
Looking for “the one that works” among markets, channels or directions also has the structure of a search: a failed small trial is like one unsuccessful look at a cell, and how much it should change one’s judgement depends on the trial’s “detection probability”.
Hypothesis · not established
The “premature exclusion” hypothesis (not yet established). The author conjectures that when teams evaluate new directions they systematically overestimate the “detection probability” of their own early small-scale trials, and so, like the early phases of the AF 447 search, rule some directions out too soon. A testable prediction: in organisations that record the sample size and power of every trial in advance, directions excluded after “one failure” and later retested succeed on retesting markedly more often than the original trial’s power would lead one to expect. If retests succeed about as often as expected, the hypothesis loses support.
Summary
Search theory writes “where to look” in terms of three ingredients: the prior, the detection function and Bayesian updating; the greedy rule for the next search picks the place with the largest product of posterior probability and detection probability. Not finding is information, pushing probability from easy places towards hard ones. On the illustrative grid, searching by the product is faster than looking only at probability or sweeping outwards. The Scorpion and AF 447 cases show that a good prior and honest detection probabilities are crucial; AF 447 in particular shows that assumptions about the effectiveness of past searches must themselves be put into the model and updated. In foraging ecology the marginal value theorem writes “when to leave a patch” as stopping when the marginal rate of gain falls to the average rate; “Lévy flights are optimal” holds only under conditions such as sparse, revisitable targets, and whether animals really search this way is still disputed. The next chapter turns to another kind of search: allocating a limited number of tries among several options with uncertain payoffs.
References
Fan, Y. (2026). Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices: Exploration–Exploitation Trade-offs and Sunk-Cost Truncation in Statistical Decision Theory [未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23810102 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).