§3.2, p. 16 — an IBR experiment is an experiment with marginals q, and its worst-case variance is the sum of the worst-case variances of its blocks
ProvedCorrClusterExp.IBR.ibr_additivityLet , let be cluster sizes, and partition the clusters into consecutive blocks . Consider the IBR experiment that, independently on each block with clusters, treats a uniformly random set of clusters with probability and of clusters otherwise. Then every cluster is treated with probability , and the worst-case variance of the IBR experiment is the sum of the worst-case variances of its blocks:
where is the correlation matrix of the IBR experiment and that of the block law on .
This additivity is what makes the optimal partition computable by the dynamic program (4).
Formalization Note Blocks are given by c : Composition n; block has c.blocksFun j clusters, embedded by c.embedding j.
Differences from the source:
- generalization: the page speaks of the worst-case variance only → Lean also concludes that the IBR law is an experiment (marginals ); reason: p. 14 states that IBR treats a fraction of each block; the added conclusion is needed for and dropping it gives the page's claim.
- generalization: blocks of the clusters sorted by decreasing size → any consecutive blocks of any , sorted or not; reason: the sizes play no role in additivity; the sorted case is an instance.
import Mathlib import Definitions.Def_CorrClusterExp_IBR_Setting
namespace CorrClusterExp.IBR
open Matrix Finset
theorem ibr_additivity (q : ℝ) (hq0 : 0 < q) (hq : q ≤ 1 / 2) (n : ℕ) (c : Composition n)
(w : Fin n → ℝ) (hw0 : ∀ i, 0 ≤ w i) :
IsExperiment q (ibrLaw q c) ∧
VIBR q w c = ∑ j : Fin c.length,
worstCase (corr q (fracLaw q (c.blocksFun j))) (fun i => w (c.embedding j i)) := by sorry
end CorrClusterExp.IBR
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.