Manuscript Oai211-A@1 · Oai211-A.tex · lemma · 3f3e4f63

Lemma: Finite-size bounded-label certificate

Uniform path sums · lines 414–466 · proof included or linked

Oai211-A@1#lem:finitepath, Oai211-A@1#eq:finitepath, Oai211-A@1#eq:finiterelative

Suppose $∣ b ∣ \leq B$ , with $B > 0$ . For $x > 0$ and $1 \leq L \leq N - 1$ ,

P_{N} (v \in T_{N} max ∣ B_{b} (v) - μ_{b} H (v) ∣ > x) \leq γ_{N} (L) + \frac{2}{π _{N}} h = 1 \sum^{L} exp (- \frac{x ^{2}}{2 B ^{2} h}) .

The right side may be capped at one.

For $1 \leq ℓ \leq L \leq N - 1$ and $r > 0$ ,

P_{N} (H (v) \geq ℓ max \frac{B _{b} ( v )}{H ( v )} - μ_{b} > r) \leq γ_{N} (L) + \frac{2}{π _{N}} h = ℓ \sum^{L} exp (- \frac{h r ^{2}}{2 B ^{2}}) .

A maximum over an empty set is zero.

Proof. For an iid spine path of length $h$ , Hoeffding's inequality for variables in $[- B, B]$ gives

P_{sp} (j = 1 \sum^{h} b (Z_{j}) - h μ_{b} > x) \leq 2 exp (- \frac{x ^{2}}{2 B ^{2} h}) .

The probability that there is a violating node at depth $h$ is at most the expected number of such nodes. Apply Lemma lem:spine in the unconditioned tree, then bound the probability after size conditioning by division by $π_{N}$ . Sum over $h \leq L$ , and add $P_{N} (H_{m a x} > L) = γ_{N} (L)$ . This proves (eq:finitepath). Use $x = h r$ at depth $h$ to prove (eq:finiterelative).

Displayed formulas in this passage

Oai211-A@1#eq:finitepath · line 418
$P_{N} (v \in T_{N} max ∣ B_{b} (v) - μ_{b} H (v) ∣ > x) \leq γ_{N} (L) + \frac{2}{π _{N}} h = 1 \sum^{L} exp (- \frac{x ^{2}}{2 B ^{2} h}) .$
Oai211-A@1#eq:finiterelative · line 432
$P_{N} (H (v) \geq ℓ max \frac{B _{b} ( v )}{H ( v )} - μ_{b} > r) \leq γ_{N} (L) + \frac{2}{π _{N}} h = ℓ \sum^{L} exp (- \frac{h r ^{2}}{2 B ^{2}}) .$
unlabeled · line 450
$P_{sp} (j = 1 \sum^{h} b (Z_{j}) - h μ_{b} > x) \leq 2 exp (- \frac{x ^{2}}{2 B ^{2} h}) .$

Nearby in this section

corollary: Corollary: Bounded path law