On a constant filtration the bounded-surprise property holds with the optimal parameter
ProvedKServer.bounded_surprise_zero_of_constant_filtrationThe tame pair is free on a constant filtration; bounded surprise is then exact.
Let C be a chunk system with online escapes on a metric space with marked points
s, t, with size ceiling cHi, and suppose the filtration is constant: every
outcome shares its history at every time, i.e. C.hist h ω = C.hist h ω' for all
h, ω, ω'. Then the time-h atom C.atom h ω is all of Ω, so the
conditional expected remaining size
F_h(ω) = condRemaining h ω is, for every level h, the plain tail sum
∑_{j ≥ h} c_j of the sizes, and is therefore independent of ω. The realised
window size S_{[a,b)}(ω) = windowSize a b ω is also independent of ω, and
S_{[a,b)} = ∑_{a ≤ j < b} c_j = F_a - F_b ,
so BoundedSurprise holds with the optimal parameter cmax = 0, with equality,
for every window.
The hypothesis hist 0 constant that appears throughout the BCR level invariant
is the level-0 instance of the constancy assumption; this lemma isolates the
observation that the extra branchwise conditions of
KServer.BCRInductiveSubchunksTame — namely SlowDecrement and
BoundedSurprise at cmax = 3 * 3^w / 2 — carry no content that is not already
forced by hsmeas and hsize once the filtration is constant, and that the
regrouping of Lemma 15 therefore needs them only for genuinely refining
filtrations.
The proof uses only the definitions of atom, condRemaining, windowSize and
BoundedSurprise: the atom is Finset.univ by Finset.filter_true_of_mem, so
condRemaining collapses to ∑ ω, P ω * (tail sum) / ∑ ω, P ω and the denominator
is 1 by hPsum, leaving a ω-independent tail sum.
import Mathlib import Definitions.Def_KServer_chunk_bounded_surprise
theorem KServer.bounded_surprise_zero_of_constant_filtration :
∀ {X : Type*} [MetricSpace X] {s t : X} {cLo cHi total price : ℝ} {mLo : ℕ}
(C : ChunkSystemB X s t cLo cHi total price mLo),
0 ≤ cHi →
(∀ (h : ℕ) (ω ω' : C.Ω), C.hist h ω = C.hist h ω') →
C.BoundedSurprise 0 := by sorry