OctoInformBeta

OpenAI preprint, September 2026 · Section 5. Splitting vertices and bounding triangle mass

Lemma 5.1: A shared joint law gives pairwise bounds in terms of total variation distance

Coupling finite families with controlled disagreement.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A finite family of probability laws on the same state set can be sampled jointly. The quantity of interest is the chance that two coordinates disagree, measured against how far apart their marginal laws are.

A probability law pp on a finite set AA is a function p:A→ℝp\colon A\to\mathbb R satisfying (1). p(x)≥0(x∈A),∑x∈Ap(x)=1.p(x)\ge 0\quad(x\in A), \qquad \sum_{x\in A}p(x)=1.(1)✦ For functions a,b:A→ℝa,b\colon A\to\mathbb R, their total variation distance d(a,b)d(a,b) is the number defined by (2). d(a,b)=12∑x∈A|a(x)−b(x)|.d(a,b)=\frac12\sum_{x\in A}|a(x)-b(x)|.(2)✦

The Claim

Theorem 1 (Shared rejection coupling). Let II be a finite set, let JJ be a finite nonempty set, and let (pi)i∈I(p_i)_{i\in I} be probability laws on JJ. There is a probability law qq on the set JIJ^I of functions f:I→Jf\colon I\to J such that ∑f∈JIf(i)=yq(f)=pi(y)(i∈I,y∈J),∑f∈JIf(i)≠f(i′)q(f)≤2d(pi,pi′)1+d(pi,pi′)(i,i′∈I).\begin{aligned} \sum_{\substack{f\in J^I\\ f(i)=y}}q(f) &=p_i(y) &&(i\in I,\ y\in J),\\ \sum_{\substack{f\in J^I\\ f(i)\ne f(i')}}q(f) &\le \frac{2d(p_i,p_{i'})}{1+d(p_i,p_{i'})} &&(i,i'\in I). \end{aligned}(3)✦ For any finite set AA and any functions a,b:A→ℝa,b\colon A\to\mathbb R, 2d(a,b)1+d(a,b)≤2d(a,b).\frac{2d(a,b)}{1+d(a,b)}\le 2d(a,b).(4)✦ For real-valued functions on a finite set, twice their total variation distance divided by one plus that distance is at most twice their total variation distance.

In the paper, the result reads: for finite nonempty sets I,JI,J and probability laws pip_i on JJ, there are jointly distributed random variables YiY_i with respective laws pip_i and finite joint support such that ℙ(Yi≠Yi′)≤2d(pi,pi′)/(1+d(pi,pi′))≤2d(pi,pi′)\mathbb P(Y_i\ne Y_{i'})\le 2d(p_i,p_{i'})/(1+d(p_i,p_{i'}))\le 2d(p_i,p_{i'}) for every i,i′∈Ii,i'\in I.

What Is Checked

The coupling statement (3) concerns probability laws on finite sets, with a nonempty state set, while (4) concerns arbitrary real-valued functions on a finite set.