Finite adaptive packet trees

Proof of Theorem 11.2

Starting from the root identity \(P_{\varnothing}=I\), replace every unselected internal node by the exact sum of its children. If a complete pruning contains the root it contains no other node. Otherwise its restriction to each child subtree is itself a complete pruning: every terminal path through that child must be met exactly once. Induction on the finite tree therefore justifies the substitution and its termination precisely at \(\Lambda\). Child subtrees have distinct node addresses, so their selected-node sets form a disjoint union. The sum identity uses only root identity and parent-to-child conservation; sibling orthogonality gives the additional interpretation as nonoverlapping projector packets. Applying the resulting identity to \(x\) gives the synthesis formula.

Back to statement · Read statement and proof side by side · Permalink · Source line 917 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 11.3

The root-only pruning exists, and every pruning is a subset of the finite node set, so the feasible set is nonempty and finite. Thus the minimum is attained. If competitors exist, their finitely many differences from a unique optimum are strictly positive, so their minimum is positive and is achieved by a competitor. In the singleton case there is no alternative selector under any objective change. In the remaining case, for any competing pruning \(\Lambda\ne\Lambda_y^*\),

Hence the same pruning remains uniquely optimal. Exact synthesis depends only on completeness of the pruning, not on the cost used to select it.

Back to statement · Read statement and proof side by side · Permalink · Source line 959 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 11.4

Proceed upward from the terminal nodes. Every complete pruning below an internal node \(v\) has exactly two possible forms: it either stops at \(v\), with cost \(c_v(y)\), or it refines and is the union of complete child prunings, whose minimum total cost is the sum of the already computed child minima. The recursion therefore gives the exact minimum on every subtree, in particular at the root. This characterization also proves both directions of the correspondence between recursive cuts and complete covering antichains, for arbitrary positive finite branching, including unary branches. Summing cached child values charges at most one addition per child edge; a finite rooted tree has \(|\mathcal T|-1\) such edges. The number of internal nodes is at most \(|\mathcal T|\), which gives the stated work bound. Ties do not affect optimality, but the stop-on-ties rule makes the selected pruning unambiguous.

Back to statement · Read statement and proof side by side · Permalink · Source line 994 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary 11.5

For any pruning of the subtree rooted at \(v\), either \(v\) itself is selected, producing perturbation at most \(\varepsilon_v\), or the pruning is the disjoint union of child prunings, producing perturbation at most the sum of the child envelopes. The same decomposition applied to the nonnegative weights \(\varepsilon_a\) proves equality with the maximum weight: at each node choose either the stop option or a maximizing pruning in each child, whichever gives the larger total. Finiteness ensures these choices attain their maxima. Evaluating each cost at a minimizer of the other cost bounds the difference of the two optimal values by the uniform envelope. The selector statement follows from the strict-gap theorem. The finite deterministic comparisons defining the selector make its preservation event measurable when the random node costs are measurable. The joint local-error event is contained in the selector-preservation event, so monotonicity of probability proves the probabilistic assertion.

Back to statement · Read statement and proof side by side · Permalink · Source line 1025 · Claim record · Lean coverage · Code · Worked examples