(4), §3.2, p. 16 — Bellman equation V_k = min_{h∈[k]} g_k(h) + V_{k−h} for the optimal IBR partition
ProvedCorrClusterExp.IBR.bellman_4block-randomizationdynamic-programmingexperimental-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let with . For let be the worst-case variance of a block made of the first clusters under the block law of Proposition 3.1, and let be the worst-case variance of the optimal IBR experiment on the remaining clusters (). Then the worst-case variance of the optimal IBR experiment satisfies the Bellman equation
Applied to the last clusters, this is the recursion of the paper, which computes the optimal partition in polynomial time.
Formalization Note The minimum is stated as two clauses: for every , and equality for some . The suffix sizes are fun i : Fin (n - h) => w ⟨h + i, _⟩.
Differences from the source:
- encoding: for the last of the sorted clusters → of the suffix size vector, with the equation stated for every and ; reason: the recursion at level is the instance on the suffix, so every level is covered.
- encoding: → " for all and for some"; reason: same statement for a finite nonempty index set.
Preamble
import Mathlib import Definitions.Def_CorrClusterExp_IBR_Setting
Formal statement
namespace CorrClusterExp.IBR
open Matrix Finset
theorem bellman_4 (q : ℝ) (hq0 : 0 < q) (hq : q ≤ 1 / 2) (n : ℕ) (hn : 1 ≤ n)
(w : Fin n → ℝ) (hw0 : ∀ i, 0 ≤ w i) (hw : Antitone w) :
(∀ (h : ℕ) (h1 : 1 ≤ h) (h2 : h ≤ n),
VDP q w ≤ worstCase (corr q (fracLaw q h)) (fun i : Fin h => w (Fin.castLE h2 i)) +
VDP q (fun i : Fin (n - h) => w ⟨h + i.val, by have := i.isLt; omega⟩)) ∧
∃ (h : ℕ) (h1 : 1 ≤ h) (h2 : h ≤ n),
VDP q w = worstCase (corr q (fracLaw q h)) (fun i : Fin h => w (Fin.castLE h2 i)) +
VDP q (fun i : Fin (n - h) => w ⟨h + i.val, by have := i.isLt; omega⟩) := by sorry
end CorrClusterExp.IBR
Source
Candogan, Chen, Niazadeh, Correlated Cluster-Based Randomized Experiments: Robust Variance Minimization, SSRN 3852100 (version of March 22, 2023), p. 16, §3.2, equation (4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.