Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.4.1 — the Palm expansion of a functional of the count

Proved
PalmQueueing.Ordering.palm_count_expansion

by mikedeng1 · Oct 2, 2026 · Mathlib 0df444a (Lean v4.33.1)

palm-calculusprobabilityqueueingstatisticsstochastic-ordering

Lemma 4.4.1. Let NNN be a stationary point process with finite intensity λ\lambdaλ and Palm probability P0P^0P0, with points TnT_nTn​ (T0≤0<T1T_0 \le 0 < T_1T0​≤0<T1​). For all functions f:R+→Rf : \mathbb{R}_+ \to \mathbb{R}f:R+​→R with f(0)=0f(0) = 0f(0)=0, and for all x>0x > 0x>0,

EP[f(N[0,x))]=∑n=0∞(f(n+1)−2f(n)+f((n−1)+)) λEP0(x−Tn)+,(4.4.1)E_P[f(N[0,x))] = \sum_{n=0}^{\infty}\big(f(n+1) - 2f(n) + f((n-1)^+)\big)\, \lambda E_{P^0}(x - T_n)^+ , \tag{4.4.1}EP​[f(N[0,x))]=n=0∑∞​(f(n+1)−2f(n)+f((n−1)+))λEP0​(x−Tn​)+,(4.4.1)

whenever the series converges absolutely.

A stationary expectation of a functional of the count in a window is expanded into a series of second differences of fff against Palm expectations of the residual window (x−Tn)+(x - T_n)^+(x−Tn​)+. For fff convex every coefficient is non-negative, so the expansion is monotone in the quantities EP0(x−Tn)+E_{P^0}(x-T_n)^+EP0​(x−Tn​)+; this is what turns a ≤cx\le_{cx}≤cx​ comparison of the Palm distributions Tn[P0]T_n[P^0]Tn​[P0] into a ≤cx\le_{cx}≤cx​ comparison of the stationary counts N[0,x)[P]N[0,x)[P]N[0,x)[P] (Property 4.4.1).

Formalization Note. The book states (4.4.1) "for all functions fff" without a convergence qualification. Read literally this fails: the partial sums differ from ∑k≤Mf(k)P(N[0,x)=k)\sum_{k\le M} f(k)P(N[0,x)=k)∑k≤M​f(k)P(N[0,x)=k) by the boundary term f(M+1)aM−f(M)aM+1f(M+1)a_M - f(M)a_{M+1}f(M+1)aM​−f(M)aM+1​, with an=λEP0(x−Tn)+a_n = \lambda E_{P^0}(x-T_n)^+an​=λEP0​(x−Tn​)+, which need not vanish for heavy-tailed counts and sparse fff even when EP∣f(N[0,x))∣<∞E_P|f(N[0,x))| < \inftyEP​∣f(N[0,x))∣<∞. The statement therefore assumes ∑n∣f(n+1)−2f(n)+f((n−1)+)∣ an<∞\sum_n |f(n+1) - 2f(n) + f((n-1)^+)|\,a_n < \infty∑n​∣f(n+1)−2f(n)+f((n−1)+)∣an​<∞, which covers the book's use (convex fff with finite expectation, all terms non-negative).

Preamble
import Mathlib
import Definitions.Def_PalmQueueing_Palm_PointProcess
Formal statement
/-!
# Lemma 4.4.1: the Palm expansion of a functional of the count (§4.4, p.295)
-/

namespace PalmQueueing.Ordering

open MeasureTheory
open PalmQueueing.Palm

variable {Ω : Type*} [MeasurableSpace Ω]

/-- **Lemma 4.4.1** (p.295). Let `N` be a stationary point process with finite intensity. For all
functions `f : ℝ₊ → ℝ` with `f(0) = 0`, and for all `x > 0`,

`(4.4.1)  E_P[f(N[0,x))] = Σ_{n=0}^{∞} ( f(n+1) − 2f(n) + f((n−1)⁺) ) λ E_{P⁰}(x − T_n)⁺`.

A stationary expectation of a functional of the count in a window is expanded into a series of
**second differences** of `f` against Palm expectations of the residual window `(x − T_n)⁺`. The
second difference is what makes the lemma useful: `f` convex means every coefficient
`f(n+1) − 2f(n) + f((n−1)⁺)` is non-negative, so the whole expansion is monotone in the quantities
`E_{P⁰}(x − T_n)⁺` — which is exactly what Property 4.4.1 needs to turn a `≤_cx` comparison of the
`T_n[P⁰]` into a `≤_cx` comparison of the counts `N[0,x)[P]`.

That equivalence, Property 4.4.1, is the point of §4.4:

> (i) `T_n[P⁰] ≤_cx T̃_n[P̃⁰]` for all `n ≥ 1`;  (ii) `N[0,x)[P] ≤_cx Ñ[0,x)[P̃]` for all
> `x ∈ ℝ₊`

are equivalent. The section's Example 4.4.1, "Feller's paradox revisited", shows that the
corresponding statement for `≤_i` is **false** — the Palm order does not pass to the stationary
one — so the restriction to `≤_cx` is essential and this lemma is where it enters.

`f(0) = 0` is a hypothesis, not a normalisation: the coefficient at `n = 0` is
`f(1) − 2f(0) + f(0) = f(1) − f(0)`, and the series is arranged around it.

**Correction of the page (recorded in `HARD.md`).** The page states (4.4.1) "for all functions
`f`" without saying in what sense the series converges, and read literally it is false: the
second differences telescope, `Σ_{n ≤ M} Δ²f(n) a_n = Σ_{k ≤ M} f(k) P(N[0,x) = k)
+ f(M+1) a_M − f(M) a_{M+1}` with `a_n = λE_{P⁰}(x − T_n)⁺ = E_P(N[0,x) − n)⁺`, and for a mixed
Poisson `N` with heavy-tailed intensity and `f` supported on a sparse set the boundary term does
not vanish although `E_P|f(N[0,x))| < ∞`. The theorem is therefore stated under the hypothesis
that the series of (4.4.1) converges absolutely, `Σ_n |Δ²f(n)| λE_{P⁰}(x − T_n)⁺ < ∞`, which
covers the use the book makes of it (convex `f`, where every term is non-negative) and makes the
right-hand side an honest sum rather than Lean's `tsum` of a non-summable family (`= 0`). -/
theorem palm_count_expansion (S : PalmSetting Ω) (f : ℝ → ℝ) (hf0 : f 0 = 0) (x : ℝ) (hx : 0 < x)
    (hsum : Summable fun n : ℕ =>
      |f ((n : ℝ) + 1) - 2 * f (n : ℝ) + f (max ((n : ℝ) - 1) 0)| *
        (S.lam * ∫ ω, max (x - S.N.T (n : ℤ) ω) 0 ∂S.P0)) :
    ∫ ω, f ((S.N.count ω (Set.Ico (0 : ℝ) x)).toReal) ∂S.P
      = ∑' n : ℕ,
          (f ((n : ℝ) + 1) - 2 * f (n : ℝ) + f (max ((n : ℝ) - 1) 0)) *
            (S.lam * ∫ ω, max (x - S.N.T (n : ℤ) ω) 0 ∂S.P0) := by sorry

end PalmQueueing.Ordering
Source
Baccelli & Bremaud, Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences, 2nd ed., Springer 2003, p. 295, Lemma 4.4.1
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 2026

    Confirmed by the mission captain (proposal self-audit).

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