Reciprocal Bernoulli factory: a bit of mean in expected rounds (cited from Lee et al. 2014)
ProvedBilateralProfitRegular.lee_factorybilateral-tradeonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1posted-pricesregret-boundsregular-distributions
This is the step of the proof of Lemma 6.5 that generates each of . The paper attributes it to an adaptation of Huber's procedure, citing Propositions 1, 2 and 4 of A. Lee, A. Doucet and K. Łatuszyński (2014). Write and .
There is a universal constant such that, for every , there is a procedure with the following property. Given i.i.d. flips of a coin with unknown bias satisfying , the procedure:
- stops almost surely;
- outputs a bit equal to with probability exactly ;
- uses at most coin flips in expectation.
The range of is where the paper makes the claim. The condition is as printed. The bound comes from Lemma 6.4(ii), and gives .
Differences from the source:
- reading: "a bit of mean from trade bits at … expected rounds, since " → for and ; reason: the paper's standing range for this step: mean as printed, and by Lemma 6.4(ii); the claim is made only there
- encoding: a factory generating a bit from trade bits → a sampling procedure with the single query "flip", chosen before ; reason: same law of everything it observes
Preamble
import Mathlib import Definitions.Def_BilateralProfitRegular_Proc
Formal statement
namespace BilateralProfitRegular
open MeasureTheory
/-- **Reciprocal Bernoulli factory for `B`, `B′`** ("An adaptation of the same procedure from
Huber [27] … can generate a bit of mean `P̂(w)/(20P(y)) ≤ 1/2` from trade bits at `y` (see
Propositions 1, 2, and 4 in Lee et al. [33]). It uses `O(1/P(y)) = O(1/P̂(w))` expected rounds"),
Brüstle, di Gregorio, Fusco, Leonardi (manuscript, sha256 e91e8127…), proof of Lemma 6.5, p.42
(PDF 44); cited from A. Lee, A. Doucet, K. Łatuszyński, *Perfect simulation using atomic
regeneration with application to Sequential Monte Carlo*, arXiv:1407.5770v1, 2014,
Propositions 1, 2, 4.
There is a universal `C` such that for every `m ∈ (0, 1/20]` there is a procedure that, given
i.i.d. coins of an unknown bias `p` with `2m ≤ p ≤ min(1, 200m)`, outputs a bit of mean `m/p`
(stops almost surely, outputs `true` with probability exactly `m/p`) using at most `C/p` coin
flips in expectation.
**Formalization Note.** `m = P̂(w)/20` and `p = P(y)`; the range of `p` is the paper's standing
range for this step: `m/p ≤ 1/2` (as printed) and `P(y) ≤ 10 P̂(w)` (Lemma 6.4(ii)), and
`P̂(w) ≤ 1` gives `m ≤ 1/20`. A factory is a `Proc` with the single query "flip the coin"; it is
chosen before `p`. -/
theorem lee_factory :
∃ C : ℝ, 0 < C ∧ ∀ m : ℝ, 0 < m → m ≤ 1 / 20 →
∃ (Ω : Type) (_ : MeasurableSpace Ω) (Pω : Measure Ω) (_ : IsProbabilityMeasure Pω)
(F : Proc Unit Bool Ω),
∀ p : ℝ, 2 * m ≤ p → p ≤ 1 → p ≤ 200 * m →
Proc.law Pω {x | F.out (fun _ => p) x.1 x.2 = none} = 0 ∧
Proc.law Pω {x | F.out (fun _ => p) x.1 x.2 = some true} = ENNReal.ofReal (m / p) ∧
F.expRounds (fun _ => p) Pω ≤ ENNReal.ofReal (C / p) := by sorry
end BilateralProfitRegular
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), proof of Lemma 6.5, p.42 (PDF 44); cited: A. Lee, A. Doucet, K. Łatuszyński, Perfect simulation using atomic regeneration with application to Sequential Monte Carlo, arXiv:1407.5770v1, 2014, Propositions 1, 2, 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.