Section 2, Eqs. (7)–(8) and M₁ — 0 ≤ δ[1 − δ/(1−γ)] ≤ 3 − 2^{3/2}, attained at (0, 2 − √2) and (2 − √2, 0)
ProvedRobbinsSeqDesign.StayOrSwitch.loss_maxbandit-algorithmsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1real-analysis
For real numbers , not both and not both , put and . Then
- ;
- the quantity satisfies
- the value is taken at , and at , .
This is the elementary half of the paper's comparison: is the asymptotic loss per toss of the rule , and is its worst case over all pairs of coins.
Formalization Note No probability enters this statement. is written as 2 * Real.sqrt 2. The numerical values and are not formalized.
Preamble
import Mathlib import Definitions.Def_RobbinsSeqDesign_StayOrSwitch_Coins
Formal statement
namespace RobbinsSeqDesign.StayOrSwitch
/-- Section 2, Eqs. (7)–(8) and the maximum `M₁`, p. 531: for `0 ≤ α, β ≤ 1` not both `0` and
not both `1`, `max(α, β) = γ + δ` and `0 ≤ δ[1 − δ/(1 − γ)] ≤ 3 − 2^{3/2}`; the value
`3 − 2^{3/2}` is taken at `α = 0, β = 2 − 2^{1/2}` and at `α = 2 − 2^{1/2}, β = 0`. -/
theorem loss_max :
(∀ α β : ℝ, 0 ≤ α → α ≤ 1 → 0 ≤ β → β ≤ 1 → ¬(α = 0 ∧ β = 0) → ¬(α = 1 ∧ β = 1) →
max α β = gamma α β + delta α β ∧
0 ≤ delta α β * (1 - delta α β / (1 - gamma α β)) ∧
delta α β * (1 - delta α β / (1 - gamma α β)) ≤ 3 - 2 * Real.sqrt 2) ∧
delta 0 (2 - Real.sqrt 2) * (1 - delta 0 (2 - Real.sqrt 2) / (1 - gamma 0 (2 - Real.sqrt 2)))
= 3 - 2 * Real.sqrt 2 ∧
delta (2 - Real.sqrt 2) 0 * (1 - delta (2 - Real.sqrt 2) 0 / (1 - gamma (2 - Real.sqrt 2) 0))
= 3 - 2 * Real.sqrt 2 := by sorry
end RobbinsSeqDesign.StayOrSwitch
Source
Robbins, Some aspects of the sequential design of experiments, Bull. Amer. Math. Soc. 58 (1952), p. 531, Section 2, Eqs. (7), (8) and the maximum M₁
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.