Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§6.1 — normalized trace experiment and conditional entropy

Definition
DOPriorityQueue_Construction_Supplement_Experiment

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

differential-obliviousnessp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1priority-queueprobability

Let n≥2n\ge2n≥2 and let b1,…,bnb_1,\ldots,b_nb1​,…,bn​ be distinct fixed tokens. Choose priorities X1,…,XnX_1,\ldots,X_nX1​,…,Xn​ independently and uniformly from [n]={1,…,n}[n]=\{1,\ldots,n\}[n]={1,…,n}. The history σ(X)\sigma(X)σ(X) first inserts (Xi,bi)(X_i,b_i)(Xi​,bi​) in index order and then performs nnn minimum extractions. Let Π(X)\Pi(X)Π(X) list insertion indices in stable increasing order of (Xi,i)(X_i,i)(Xi​,i).

A trace kernel assigns a probability mass function to each operation history. It has no payload indivisibility, private-space, or computation restriction. Insertion-field privacy is defined using the published adjacency and queue domain. The joint experiment first chooses XXX uniformly and then draws the call-grouped address/direction trace from the kernel. If VVV denotes that trace,

H(Π∣V)=∑vPr⁡[V=v]H(Π∣V=v),P(v)=∑j∣vj∣.H(\Pi\mid V)=\sum_v\Pr[V=v]H(\Pi\mid V=v),\qquad P(v)=\sum_j|v_j|.H(Π∣V)=v∑​Pr[V=v]H(Π∣V=v),P(v)=j∑​∣vj​∣.

The imported Shannon entropy is in bits. Null fibers have zero weight; 0log⁡0=00\log0=00log0=0. The expectation of PPP is a nonnegative extended sum and may be infinite. The finite range of Π\PiΠ makes its conditional entropy finite for every normalized law.

The information-loss parameter is

γn=ε+1ln⁡2+δlog⁡2n1−e−1.\gamma_n=\frac{\varepsilon+1}{\ln2}+\frac{\delta\log_2n}{1-e^{-1}}.γn​=ln2ε+1​+1−e−1δlog2​n​.

This interface gives Lemma 6.2 its full scope, including encoded payloads. Zero-based finite indices encode the source's one-based priorities by adding one. Token identities are semantic labels, not extra words accessible to a queue.

Definition code
import Definitions.Def_DOPriorityQueue_Construction_Queue
import Definitions.Def_DOPriorityQueue_Construction_RAM
import Definitions.Def_SpanForestStream_Unrestricted_Info

set_option autoImplicit false

namespace DOPriorityQueue.Construction.Supplement

/-- General normalized trace mechanism. No token-routing or memory axiom occurs
here: Lemma 6.2 also applies to queues with jointly encoded payloads. -/
abbrev TraceKernel (w : ℕ) := List (Operation ℕ) → PMF (RAM.Trace w)

noncomputable def kernelEvent {w : ℕ} (K : TraceKernel w)
    (h : List (Operation ℕ)) (A : Set (RAM.Trace w)) : ENNReal :=
  SpanForestStream.Unrestricted.probOf (K h) A

noncomputable def insertionDO {w : ℕ} (K : TraceKernel w) (T U : ℕ) (ε δ : ℝ) : Prop :=
  0 ≤ ε ∧ 0 ≤ δ ∧ δ ≤ 1 ∧
  ∀ h h', validHistory T U h → validHistory T U h' → insertionNeighbors h h' →
    ∀ A : Set (RAM.Trace w),
      kernelEvent K h A ≤ ENNReal.ofReal (Real.exp ε) * kernelEvent K h' A + ENNReal.ofReal δ

/-- Equation (7). Fin indices are zero-based; actual priorities are i.val + 1. -/
def experimentHistory {n : ℕ} (b : Fin n → ℕ) (X : Fin n → Fin n) :
    List (Operation ℕ) :=
  (List.ofFn fun i => Operation.insert ((X i).val + 1) (b i)) ++
    List.replicate n Operation.extractMin

/-- Π is represented by its list of insertion indices in stable output order.
This is a permutation, not an arbitrary output supplied by the implementation. -/
def stablePermutation {n : ℕ} (X : Fin n → Fin n) : List (Fin n) :=
  (List.finRange n).mergeSort fun i j =>
    decide ((X i).val < (X j).val ∨ ((X i).val = (X j).val ∧ i.val ≤ j.val))

noncomputable def experimentLaw {n w : ℕ} (K : TraceKernel w) (b : Fin n → ℕ) :
    PMF ((Fin n → Fin n) × RAM.Trace w) := by
  classical
  letI : Nonempty (Fin n → Fin n) := ⟨id⟩
  exact (PMF.uniformOfFintype (Fin n → Fin n)).bind fun X =>
    (K (experimentHistory b X)).map fun v => (X, v)

/-- Countable trace conditioning; null fibers receive weight zero. The imported
entropy uses nonnegative extended sums, bits, and 0 log 0 = 0. -/
noncomputable def residualEntropy {n w : ℕ} (K : TraceKernel w) (b : Fin n → ℕ) :
    ENNReal :=
  let law := experimentLaw K b
  ∑' v : RAM.Trace w,
    (law.map Prod.snd) v *
      SpanForestStream.Unrestricted.entropyBits
        (SpanForestStream.Unrestricted.condLaw law Prod.snd
          (fun z => stablePermutation z.1) v)

def probeCount {w : ℕ} (v : RAM.Trace w) : ℕ := v.flatten.length

/-- Extended nonnegative expectation, including +∞ for unbounded probe cost. -/
noncomputable def expectedProbes {w : ℕ} (K : TraceKernel w)
    (h : List (Operation ℕ)) : ENNReal :=
  ∑' v : RAM.Trace w, K h v * (probeCount v : ENNReal)

noncomputable def mixedProbes {n w : ℕ} (K : TraceKernel w) (b : Fin n → ℕ) :
    ENNReal :=
  ∑' v : RAM.Trace w, ((experimentLaw K b).map Prod.snd) v * (probeCount v : ENNReal)

/-- Section 6.1: ln 2 in the first term is a natural logarithm. -/
noncomputable def gamma (n : ℕ) (ε δ : ℝ) : ℝ :=
  (ε + 1) / Real.log 2 + δ * Real.logb 2 n / (1 - Real.exp (-1))

end DOPriorityQueue.Construction.Supplement
Source
Zimai Guo, Cheng Hong, Zhechen Li, STOC 2027 submission #538 (October 2026), pp. 28–30, equation (7), equations (8)–(15)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me