claimroutineinferred_dep

Interpolation interval captures binomial mass

Claim·§4.7 Choosing the parameters·inside lemExplicit parameter choice satisfies layout hypotheses

Statement (paper)

Let

\mu=\frac{Q(r-1)}{2r}

A_0=\lfloor\mu-\frac{R-1}{2}\rfloor

and

\mathcal I=\{A_0,\ldots,A_0+R-1\}

. Then, for sufficiently large

n

\mathcal I\subseteq\{0,\ldots,Q\}

, and for

W\sim\operatorname{Bin}(Q,(r-1)/(2r))

one has

\Pr[W\notin\mathcal I]\le 2e^{-R^2/(8Q)}\le\frac1{br^2\lambda}=\epsilon

, which is with

\epsilon=\tau/(rb)

. Moreover

0<\tau\le1/2

In plain English

With

\mu=\frac{Q(r-1)}{2r}

, the interval

\mathcal I

R

consecutive integers starting at

A_0=\lfloor\mu-\frac{R-1}{2}\rfloor

lies inside

\{0,\ldots,Q\}

for large

n

. A variable

W\sim\operatorname{Bin}(Q,(r-1)/(2r))

falls outside

\mathcal I

with probability at most

2e^{-R^2/(8Q)}\le\epsilon=\frac1{br^2\lambda}

, and

0<\tau\le1/2

Why it's here

This gives the tail bound that the layout lemma needs, with

\epsilon=\tau/(rb)

. The interval is centred at the binomial mean

\mu

and has width

R=\Theta_\beta(\sqrt\lambda)

, so a Hoeffding-type bound gives a tail of

e^{-\Omega(R^2/Q)}

. Taking the constant

\beta+3

R

makes this tail at most

1/(br^2\lambda)

, using the size bounds on

r

Q

R

from the previous claim.

Classified routine:

Direct application of Hoeffding's inequality (Hoeffding 1963) to a binomial variable centred at its mean, combined with the parameter size bounds from the previous claim; pure parameter bookkeeping.

Uses

claimParameter orders and balance inequalities

Used by

claimParameters computable and checkable in polylog time

Sources

PaperOpen

Section: §4.7 Choosing the parameters
Page: —
Label: —
Line: main_full_version.tex:2796

Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

info
inferred_dep
outline: "Interpolation interval and binomial tail bound" rests on claim-lem-incidence-parameters-1