Point sampling of a graphon

Draw n + 1 independent points y 0, …, y n of the carrier of a graphon W. The W-random weighted graph H(y, W) has vertex set Fin (n + 1), all vertices of weight 1 / (n + 1), and edge weights W (y i) (y j); as a graphon it is the pullback W.comap y of W to the uniform carrier on Fin (n + 1). This file proves that it converges to W in cut distance in probability:

P(ε ≤ δ□(H(y, W), W)) → 0 as n → ∞, for every ε > 0,

over an arbitrary probability carrier. Together with the Bernoulli edge rounding (TauCeti.DenseGraphLimits.exposedSample_cutDist_comap_concentration), which compares H(y, W) with the sampled simple graph G(n, W), it gives the second sampling lemma TauCeti.DenseGraphLimits.sampleGraph_cutDist_tendsto_inProbability: δ□(G(n, W), W) → 0 in probability.

The proof compares W with a step graphon U close to it in L¹.

• Sampling does not increase the L¹ distance on average: the expected L¹ distance between the sampled graphs H(y, W) and H(y, U) is at most ‖W - U‖₁ + 1 / (n + 1), the 1 / (n + 1) accounting for the diagonal pairs (y i, y i). By Markov's inequality H(y, W) and H(y, U) are close with high probability.
• The sample H(y, U) of a step graphon is again a weighted graph with the same block values, whose vertex weights are the empirical frequencies of the blocks among the sample points. Changing the vertex weights of a weighted graph costs at most twice their ℓ¹ distance (TauCeti.DenseGraphLimits.cutDist_ofMatrix_le_two_mul_sum_abs), and the frequencies concentrate at the block measures by the weak law of large numbers (TauCeti.meas_ge_le_variance_div_card_mul_sq_pi).

On a countably generated carrier the block averages along a refining sequence of finite partitions converge to W in L¹ (TauCeti.DenseGraphLimits.tendsto_eLpNorm_countableStepGraphonAvg), which supplies U; an arbitrary graphon is the pullback of one on the Cantor space (TauCeti.DenseGraphLimits.Graphon.exists_comap_natBool), and the sampled graphs pull back along.

Main result

• TauCeti.DenseGraphLimits.cutDist_comap_tendsto_inProbability — the weighted sampled graph H(y, W) converges to W in cut distance in probability.

References

• L. Lovász, Large Networks and Graph Limits, AMS Colloquium Publications 60 (2012), §10.1 and Lemma 10.16: the W-random weighted graphs H(n, W) and the second sampling lemma.
• C. Borgs, J. Chayes, L. Lovász, V. Sós, K. Vesztergombi, Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing, Adv. Math. 219 (2008), 1801–1851, §4: sampling from a graphon.

theorem TauCeti.DenseGraphLimits.cutDist_comap_tendsto_inProbability {Ω : Type u_1} [MeasurableSpace Ω] {μ : MeasureTheory.Measure Ω} [MeasureTheory.IsProbabilityMeasure μ] (W : Graphon Ω μ) {ε : ℝ} (hε : 0 < ε) : Filter.Tendsto (fun (n : ℕ) => (MeasureTheory.Measure.pi fun (x : Fin (n + 1)) => μ).real {y : Fin (n + 1) → Ω | ε ≤ cutDist (W.comap y ⋯ (ProbabilityTheory.uniformOn Set.univ)) W}) Filter.atTop (nhds 0)

Point sampling converges in cut distance, in probability. Sample n + 1 independent points y of the carrier of a graphon W. The weighted graph H(y, W) on Fin (n + 1) with uniform vertex weights and edge weights W (y i) (y j) — the pullback of W to the uniform carrier on Fin (n + 1) — is at cut distance at least ε from W with probability tending to zero as n → ∞, for every ε > 0. The carrier is an arbitrary probability space.