Expected visit comparison for randomized two-bit policies
ProvedBilateralProfitLB.expCount_transfer_randomizedFix an integer , a perturbation index , and a horizon . Consider a posted-price policy that draws a random seed with a probability law and observes the separate seller and buyer acceptance bits after each round. The seed is independent of all valuations. The policy posts a pair in as a measurable function of the seed for each fixed history of acceptance bits.
Let count the rounds in which the posted buyer price lies in the perturbation interval . Write and for the expectations under the -th perturbed law and the baseline law, respectively. Each expectation is over the policy seed and the independent valuation pairs drawn from the indicated law. Then
Formalization Note. Claim 3.6 states this inequality for deterministic policies. The extension here retains the independent seed in the transcript and uses the same seed law under both instances. It holds on any measurable seed space with a probability measure. The intervals, price bounds, and inclusive acceptance events are those of Section 7.
import Mathlib import Definitions.Def_BilateralProfitLB_Construction import Definitions.Def_BilateralProfitLB_Stochastic open MeasureTheory BilateralProfitLB
theorem BilateralProfitLB.expCount_transfer_randomized (K : ℕ) (hK : 1 ≤ K) (j : ℕ) (hj1 : 1 ≤ j) (hjK : j ≤ K) (T : ℕ)
(Ω : Type) [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P] (π : Policy Ω) :
expCount π P (law K j) T (I K j) - expCount π P (law K 0) T (I K j) ≤
(T : ℝ) / (22 * (K : ℝ) ^ 2) * Real.sqrt (expCount π P (law K 0) T (I K j)) := by sorry