The best pruning on the previous page costs \(9\); the cheapest competitor costs \(10\). Its exact global gap is therefore \(\Gamma=1\). The plate lists every complete-pruning cost in sorted order, giving each pruning its own horizontal rank.
Reading the drawing
Sorted pruning costs are plotted against pruning rank. The unique optimum and next-best cost determine the stated global stability margin.
Drawing labels and data 16 labels
Read the original labels as selectable text. Tables preserve grid relationships; other short labels are grouped compactly.
- 0
- 5
- 10
- 15
- 20
- 25
- 9
- 10
- 15
- 20
- all 26 complete pruning costs
- \(\Gamma=10-9=1\)
- \(E(\varnothing)=8/32\)
- \(2E=1/2<\Gamma\)
- selector certified stable
- pruning rank
Propagate an error budget as carefully as a cost
Suppose every node cost changes by at most \(\varepsilon_v=1/32\). A pruning may select as many as eight leaves, so its total cost can change by at most \(8/32=1/4\). The recursive envelope proves this without guessing which pruning will be selected:
For any competitor \(\Lambda\), the changed cost difference is bounded below by
Thus the optimum is unchanged for every permitted simultaneous perturbation, not just a sampled noise realization. The envelope is over all feasible prunings, not just the five nodes in the current optimum.
Strict inequality has content
If two competing costs are \(9\) and \(10\), moving them to \(9.5\) and \(9.5\) removes uniqueness. Equality in \(2E=\Gamma\) is therefore not a unique-selector certificate. For ordinary probability, the random node costs and the joint good event must be measurable. Separate nodewise probability bounds do not automatically give the probability of that joint event.
Read this as
The exact selector is stable because its global gap exceeds the total worst-case movement of both competing costs.