Lemma 4.18 — Poisson counts with independent means are i.i.d. geometric
ProvedPathORAMCap.lemma_4_18oblivious-ramp2o-gran-per-chapterp2o-plan-paperp2o-v1path-oramprobability
Let be a finite vector of independent variables and, conditional on , let be independent with . Then the are jointly independent and
This is the step at which the independent geometric loads of Definition 4.2 appear in the comparison.
Formalization Note Both conclusions are stated at once through the joint law of the mixture: for every , , with distributed as the product of laws.
Differences from the source:
- encoding: C conditionally independent Poisson(Λ_v) given Λ; conclusions: joint independence and the marginal laws → for every k : V → ℕ, ∫ ∏_v Poisson(Λ_v){k_v} dP_Λ = ∏_v 2^{−k_v−1}; reason: the mixture's joint mass function is the left side, and it equals the product of geometric masses exactly when both printed conclusions hold
Preamble
import Mathlib set_option autoImplicit false open MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
namespace PathORAMCap
/-- **Lemma 4.18** (Independent Exponential Means Give Geometric Counts; Chang, Au, *The Minimum Bucket Capacity for Reliable Path ORAM*, STOC 2027 submission (manuscript sha256 1762f048…), p.29 (PDF p.32)): "Let
(Λv)v∈V be a finite vector of independent Exp(1) variables. Conditional on the entire vector Λ, let
(Cv)v∈V be independent with Cv | Λ ∼ Poisson(Λv). Then the Cv are jointly independent, and
P[Cv = k] = 2−k−1 for each v and integer k ≥ 0."
**Formalization Note.** The law of `C` is the mixture: `P[C = k] = E_Λ[∏_v Poisson(Λ_v)(k_v)]` with
`Λ` distributed as the product of `expMeasure 1`. Both conclusions together say that this joint
probability mass function is `∏_v 2^{−k_v−1}` for every `k : V → ℕ`. `Λ_v ≥ 0` almost surely, so
`toNNReal` is the identity on the support. -/
theorem lemma_4_18 (V : Type*) [Fintype V] (k : V → ℕ) :
∫⁻ lam : V → ℝ, ∏ v, poissonMeasure (lam v).toNNReal {k v}
∂(Measure.pi fun _ : V => expMeasure 1) =
∏ v, ((2 : ℝ≥0∞) ^ (k v + 1))⁻¹ := by sorry
end PathORAMCap
Source
Chang, Au, The Minimum Bucket Capacity for Reliable Path ORAM, STOC 2027 submission (manuscript sha256 1762f048…), Lemma 4.18, p.29 (PDF p.32)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.