Claim 5.5 — and for
ProvedBilateralProfitMHR.claim_5_5bilateral-trademonotone-hazard-rateonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1posted-pricesregret-bounds
Let and let , the number of trials up to and including the first success. With and ,
where is the subgaussian norm (Definition 5.2).
Posting a price pair until the first trade therefore gives an unbiased estimate of with subgaussian noise, which is the observation model needed for Corollary 3.1.
Differences from the source:
- encoding: → is integrable and its integral is ; reason: the expectation is finite (it equals ), and integrability makes the integral the true mean
- encoding: → the published -valued subgaussian norm is at most ; reason: Definition 5.2's infimum, with value for a non-subgaussian variable; same instances
Preamble
import Mathlib import Definitions.Def_BilateralProfitMHR_LogProfitOracle import Definitions.Def_HighDimProb_Concentration_SubgaussianNorm_v2
Formal statement
namespace BilateralProfitMHR
open MeasureTheory
/-- **Claim 5.5 (Estimating a logarithm from a geometric waiting time)**, Brüstle, di Gregorio,
Fusco, Leonardi (manuscript, sha256 e91e8127…), p.35 (PDF 37); proof App. A.5, pp.60–61
(PDF 62–63): let `Q ∈ (0, 1]` and `N ∼ Geom(Q)`. Then `E[H_{N−1}] = −log Q` and
`‖H_{N−1} + log Q‖_{ψ₂} ≤ 4 √(1 − log Q)`.
**Formalization Note.** `Geom(Q)` is `geomLaw Q` on `{1, 2, …}`; `H_m = ∑_{k=1}^m 1/k`,
`H_0 = 0`. The expectation is stated together with the integrability of `H_{N−1}` (so the
Bochner integral is the true mean). `‖·‖_{ψ₂}` is the published `subgaussianNorm` (Definition
5.2), valued in `ℝ≥0∞` and `⊤` for a non-subgaussian variable, so the bound also asserts that
`H_{N−1} + log Q` is subgaussian. Logarithms are natural. -/
theorem claim_5_5 (Q : ℝ) (hQ0 : 0 < Q) (hQ1 : Q ≤ 1) :
Integrable (fun N : ℕ => harm (N - 1)) (geomLaw Q) ∧
∫ N, harm (N - 1) ∂(geomLaw Q) = -Real.log Q ∧
HighDimProb.Concentration.subgaussianNorm (geomLaw Q)
(fun N : ℕ => harm (N - 1) + Real.log Q) ≤
ENNReal.ofReal (4 * Real.sqrt (1 - Real.log Q)) := by sorry
end BilateralProfitMHR
Source
Brüstle, di Gregorio, Fusco, Leonardi, Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism (manuscript, STOC 2027 submission, sha256 e91e81279505b765c7c96c219d674c0fbbbd6ca47a00da8fe228d498ca25ac87), Claim 5.5, p.35 (PDF 37); proof App. A.5, pp.60–61 (PDF 62–63)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.