Confidence length
DefinitionStreamRot_Supplement_ellDeltap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationspace-complexitystreaming-algorithms
For a horizon and a failure probability , the confidence length is
with the natural logarithm. It is the factor by which the upper width bound (B.2) of the confidence-uniform width law depends on the confidence level: at it is the horizon, and for positive it is capped by .
Formalization Note The value is defined by cases on , so gives and never . A negative also gives ; Theorem B.1 uses only .
Definition code
import Mathlib
namespace StreamRot
namespace Supplement
/-- The confidence length `ℓ_δ(N) = min{N, log(2/δ)}` for `0 < δ ≤ 1/3`, and `ℓ_0(N) = N`, with the natural
logarithm. Qi, Constant-Failure Width Bounds for Streaming Rotations, STOC 2027 submission (manuscript sha256 3ffd9cd7…), Section B.1, p.20 (also Section 7, p.9).
**Formalization Note** The value is defined by cases on `0 < δ`, so `δ = 0` gives `N` and never `log(2/0)`.
Negative `δ` also gives `N`; Theorem B.1 only uses `0 ≤ δ ≤ 1/3`. -/
noncomputable def ellDelta (N : ℕ) (δ : ℝ) : ℝ :=
if 0 < δ then min (N : ℝ) (Real.log (2 / δ)) else (N : ℝ)
end Supplement
end StreamRot
Source
Qi, Constant-Failure Width Bounds for Streaming Rotations, STOC 2027 submission (manuscript sha256 3ffd9cd7…), Section B.1, p.20 (PDF 22); Section 7, p.9 (PDF 11)