Proposition 9 — Stirling's approximation, two-sided
ProvedBayesBAI.proposition_9bayesianbest-arm-identificationmulti-armed-banditsp2o-gran-per-chapterp2o-plan-paperp2o-v1simple-regret
For every integer ,
and
These are the bounds behind the leading constant in Lemma 15.
Differences from the source:
- encoding: n ∈ ℕ; the second pair "by using e^(1/n) ≤ 1 + 2/n for n ≥ 2" → 1 ≤ n, all four inequalities; reason: 1/(12n) is undefined at n = 0, and the second pair uses that bound at 12n ≥ 2
Preamble
import Mathlib
Formal statement
namespace BayesBAI
/-- Proposition 9 (Stirling's approximation), Komiyama, Ariu, Kato, Qin, arXiv:2111.09885v3, p.17:
for `n ≥ 1`, `√(2π) n^(n+1/2) e^(-n) e^(1/(12n+1)) < n! < √(2π) n^(n+1/2) e^(-n) e^(1/(12n))` and
`√(2π) n^(n+1/2) e^(-n) < n! < √(2π) n^(n+1/2) e^(-n) (1 + 1/(6n))`.
**Formalization Note.** "`n ∈ ℕ`" means `n ≥ 1`, as `1/(12n)` is undefined at `0`. -/
theorem proposition_9 (n : ℕ) (hn : 1 ≤ n) :
Real.sqrt (2 * Real.pi) * (n : ℝ) ^ ((n : ℝ) + 1 / 2) * Real.exp (-(n : ℝ)) *
Real.exp (1 / (12 * (n : ℝ) + 1)) < (n.factorial : ℝ) ∧
(n.factorial : ℝ) < Real.sqrt (2 * Real.pi) * (n : ℝ) ^ ((n : ℝ) + 1 / 2) * Real.exp (-(n : ℝ)) *
Real.exp (1 / (12 * (n : ℝ))) ∧
Real.sqrt (2 * Real.pi) * (n : ℝ) ^ ((n : ℝ) + 1 / 2) * Real.exp (-(n : ℝ)) <
(n.factorial : ℝ) ∧
(n.factorial : ℝ) < Real.sqrt (2 * Real.pi) * (n : ℝ) ^ ((n : ℝ) + 1 / 2) * Real.exp (-(n : ℝ)) *
(1 + 1 / (6 * (n : ℝ))) := by sorry
end BayesBAI
Source
Komiyama, Ariu, Kato, Qin, Rate-optimal Bayesian Simple Regret in Best Arm Identification, arXiv:2111.09885v3, Proposition 9, p.17
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.