Lemma 2.2 — when
ProvedGivenDegreeSeq.GraphLimit.lemma_2_2lipschitzmaximum-likelihoodp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1random-graphs
Let and let be the map of (4)–(5). Let and with . Then
where is the norm and .
This Lipschitz bound in is the technical input that lets the proof of Theorem 1.1 control the iterates in the norm, eq. (26).
Formalization Note is Mathlib's norm on Fin n → ℝ; the norms are written as explicit sums. No positivity of is assumed: cancels in each coordinate of .
Preamble
import Mathlib import Definitions.Def_GivenDegreeSeq_GraphLimit_Phi
Formal statement
namespace GivenDegreeSeq.GraphLimit
/-- **Lemma 2.2** (Chatterjee–Diaconis–Sly, arXiv:1005.1136v5, p. 14). Let `x, y ∈ ℝⁿ` with
`max{|x|∞, |y|∞} ≤ K`. Then `|φ(x) − φ(y)|₁ ≤ 2e^{2K} |x − y|₁`, where `|·|₁` is the `L¹` norm on
`ℝⁿ`. Here `‖·‖` on `Fin n → ℝ` is the sup norm `|·|∞`; the `L¹` norms are written out as sums.
The terms `log d_i` cancel in `φ(x) − φ(y)`, so no condition on `d` is needed. -/
theorem lemma_2_2 (n : ℕ) (d x y : Fin n → ℝ) (K : ℝ) (hx : ‖x‖ ≤ K) (hy : ‖y‖ ≤ K) :
∑ i, |phi d x i - phi d y i| ≤ 2 * Real.exp (2 * K) * ∑ i, |x i - y i| := by sorry
end GivenDegreeSeq.GraphLimit
Source
Chatterjee, Diaconis & Sly, Random Graphs with a Given Degree Sequence, arXiv:1005.1136v5, p. 14, Lemma 2.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.