lemmaroutine

Conditional moment bound at a specified start

Averaged eighth-moment bound gives conditional tail bound at a fixed start

z

turns averaged error into a bound at the chosen start

Lemma·lem:final-majority·§12.2 A dyadic approximation at the specified start

Statement (paper)

Let

W\in[0,1]^V

, and suppose an estimator satisfies

\frac1N\mathbb E\sum_{v\in V}\frac{X_f(v)}f |\bar W(v)-W(v)|^8\le C_b^8 2^{-8p}.

For any specified

z\in V

and every

\eta>0

\begin{aligned} \mathbb E\bigl[|\bar W(z)-W(z)|^8\mid X_f(z)=1\bigr] &\le N\frac f{\pi_f}C_b^8 2^{-8p}, \\ \Pr\bigl[|\bar W(z)-W(z)|>\eta\mid X_f(z)=1\bigr] &\le N\frac f{\pi_f}C_b^8 2^{-8p}\eta^{-8}. \end{aligned}

In plain English

If the weighted average of

|\bar W(v)-W(v)|^8

over

v

(weighted by

X_f(v)/f

) is at most

C_b^8 2^{-8p}

, then for any fixed

z

the conditional eighth moment of

|\bar W(z)-W(z)|

given

X_f(z)=1

is at most

N\frac f{\pi_f}C_b^8 2^{-8p}

. Consequently, by Markov's inequality, the conditional probability that the error exceeds

\eta

is at most

N\frac f{\pi_f}C_b^8 2^{-8p}\eta^{-8}

Why it's here

This turns an error bound averaged over all vertices into one at a single specified start

z

, at the cost of the factor

N f/\pi_f

from conditioning on

X_f(z)=1

. The tail bound then follows from Markov's inequality applied to the eighth power. The fixed-precision theorem uses this to get a high-probability guarantee at the chosen start vertex.

Classified routine:

Direct bookkeeping: drop all terms but

v=z

from the averaged sum, divide by

\Pr[X_f(z)=1]=\pi_f

to condition, then apply Markov's inequality to the eighth power.

Uses

Nothing else in the paper

Used by

thmDeterministic logspace approximation of acceptance probabilityclaimPrecision choice beats coordinate factor N

Sources

PaperOpen

Section: §12.2 A dyadic approximation at the specified start
Page: —
Label: lem:final-majority
Line: sections/conclusion.tex:116

Leannot aligned

Phase 2 aligns this node to a Lean declaration.