Manuscript Psy03-B@1 · Psy03-B-v1.tex · theorem · 8ca3caf9

Theorem: Conditional-cycle concentration

Feedback-aware threshold and severity certification › Fresh challenge blocks · lines 1227–1260 · proof included or linked

Psy03-B@1#thm:conditional, Psy03-B@1#eq:conditional

Back to manuscript

Under Assumption ass:fresh,

P {\abs Q_{t}^{-} - Q_{t}^{-} > r_{t} H_{t}} \leq δ_{t}, r_{t} = \frac{lo g ( 2/ δ _{t} )}{2 n _{t}} .

If the predictable allocations satisfy $\sum_{t} δ_{t} \leq δ$ almost surely, then

P {\exists t : \abs Q_{t}^{-} - Q_{t}^{-} > r_{t}} \leq δ .

The horizon can be finite or countable with summable allocations. Stopping after completed blocks preserves the guarantee.

Proof. Condition on $H_{t}$ and apply the bounded-variable Hoeffding inequality Hoeffding. This is the same conditional-dependence discipline used in Psy02-B thm:sampling CheungPsy02B. Taking expectations and a union bound gives

t \sum P (failure at t) \leq E t \sum δ_{t} \leq δ .

Displayed formulas in this passage

Psy03-B@1#eq:conditional · line 1230
$P {\abs Q_{t}^{-} - Q_{t}^{-} > r_{t} H_{t}} \leq δ_{t}, r_{t} = \frac{lo g ( 2/ δ _{t} )}{2 n _{t}} .$
unlabeled · line 1241
$P {\exists t : \abs Q_{t}^{-} - Q_{t}^{-} > r_{t}} \leq δ .$
unlabeled · line 1256
$t \sum P (failure at t) \leq E t \sum δ_{t} \leq δ .$

Theorem: Conditional-cycle concentration

Displayed formulas in this passage

Nearby in this section