Manuscript Oai227-A@1 · Oai227-A.tex · lemma · 7f45f607

Lemma: A finite clock-history allowance

Stage 2: price only specified finite operations › Clock histories and their actual time budget · lines 804–837 · proof included or linked

Oai227-A@1#lem:clock-tail

Back to manuscript

For the frozen compact used in Theorem thm:finite-certificate, the probability that a trajectory needs at least $144$ update attempts is less than $2^{- 144}$ , uniformly over every coupling.

If such a history is flagged and assigned score zero, rather than deleted, the absolute bias of either scaled mean score is at most $2^{1/3} 2^{- 144}$ .

Proof. If $N$ is Poisson with mean $μ$ , then

P {N \geq m} \leq E (m N) = \frac{μ ^{m}}{m !} .

Also

lo g (m!) \geq \int_{1}^{m} lo g x d x = m lo g m - m + 1,

so $m! \geq (m / e)^{m}$ . For $m = 144$ , $μ < 112/5$ , and $e < 3$ ,

\frac{e μ}{144} < \frac{3 ( 112/5 )}{144} = \frac{7}{15} < \frac{1}{2} .

This proves the tail bound. On the flagged event, changing a score to zero changes it by at most $2^{1/3}$ . Take expectations.

Displayed formulas in this passage

unlabeled · line 818
$P {N \geq m} \leq E (m N) = \frac{μ ^{m}}{m !} .$
unlabeled · line 823
$lo g (m!) \geq \int_{1}^{m} lo g x d x = m lo g m - m + 1,$
unlabeled · line 829
$\frac{e μ}{144} < \frac{3 ( 112/5 )}{144} = \frac{7}{15} < \frac{1}{2} .$

Lemma: A finite clock-history allowance

Displayed formulas in this passage

Nearby in this section