Proposition: Explicit truncation ledger

For each edge,

The truncated local cost is

On $w_e\le K$, put $z_K=\tanh (K/2)$. For a graph with $M$ edges,

and

On a finite dual graph with $N^{\ast }$ vertices,

The probability that some sampled edge violates $w_e\le K$ is at most $M{e}^{-\lambda K}$.

Proof. The overlap is the norm of the retained part of the geometric Schmidt expansion. The pure-state trace-distance identity gives the first two formulas.

Direct summation gives

proving the entropy formula.

For the product preparation, the squared overlap is ${\prod }_e(1-{z_e}^D)$. Therefore

The cost discrepancy is increasing in ${z_e}^D$.

A minimizing path can be chosen simple, also when a truncated cost vanishes. It has at most $N^{\ast }-1$ edges. Evaluating the untruncated cost on a truncated minimizer proves the upper bound; pointwise cost monotonicity proves the lower bound. Finally use the exponential tail and a union bound.