Lemma A.2 — splitting probability and expectation
ProvedStableMSR.Recovery.Supplement.split_probabilityclusteringp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1perturbation-stability
Let a finite metric input with be -stable, where . Set , take the correct guess , and assume and . Sample a uniform order of and an independent uniform radius in . For every large optimal cluster of radius , and for counting the large clusters split by the final adjusted partition,
Here , , and the logarithm is natural. Both conclusions use the specified partition construction, including the simultaneous component adjustment. This is the quantitative splitting estimate used by the scale-success lemma.
Differences from the source:
- encoding: Finite ordered metric input and unordered exact-k partitions → Fin n points, real metric arrays, and finite sets of nonempty disjoint blocks; reason: Input-order relabelling preserves every source instance and partition; base published definitions are reused without extra conditions
- encoding: Uniform order and independent auxiliary radius; expectation of the split count → Finite uniform Dirac mixture times normalized interval volume, and the finite sum of split-event probabilities; reason: This is exactly the product analysis law and the expectation of the finite sum of indicators; it avoids a nonintegrable Bochner default
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_Partitions set_option autoImplicit false open scoped Classical
Formal statement
namespace StableMSR.Recovery.Supplement
theorem split_probability {n k : ℕ} (d : Point n → Point n → ℝ) (γ L : ℝ) (O : Partition n)
(hk : 1 ≤ k) (hkn : k < n) (hd : IsMetricArray d) (hγ : 1 < γ ∧ γ < 2)
(hO : Stable d k γ O)
(hV : netVertices d (largestRadius d O) L ≠ ∅)
(hL : sigma * largestRadius d O ≤ L ∧ L ≤ densityScale d O (γ - 1)) :
(∀ C ∈ largeClusters d O (γ - 1),
(analysisLaw d (largestRadius d O) L)
{p | Split C (partitionAt d (γ - 1) (largestRadius d O) L p.2 p.1)} ≤
ENNReal.ofReal (chi * radius d C / L * Real.log (1 + 12 * sigma / (γ - 1) ^ 2))) ∧
splitExpectation d O (γ - 1) (largestRadius d O) L ≤
chi * largeMass d O (γ - 1) / L * Real.log (1 + 12 * sigma / (γ - 1) ^ 2) := by sorry
end StableMSR.Recovery.Supplement
Source
Shyam Ravichandran, Lev Reyzin, STOC 2027 submission #1010 (October 2026), Lemma A.2, p. 17; PDF SHA256 8bb34b0b6d31458fe6fc0848c1fc82a6083f3e9ae672e748d24cf82d5289e53e