OctoInformBeta

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

Lemma 5.2: Average row entropy for reversible stochastic kernels dominated by positive reference weights

A weighted tail bound for reverse transitions.

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

The tail in Lemma 5.2 consists of steps of a finite Markov chain whose reverse transition probability is small relative to a prescribed weight at the starting state.

Let II be a finite state set. A real matrix kernel KK on II is a real matrix with rows and columns indexed by II.✦ A probability vector pp on II is a real function satisfying p(i)≥0(i∈I),∑i∈Ip(i)=1.p(i)\geq 0\quad(i\in I), \qquad \sum_{i\in I}p(i)=1.(1)✦ A stochastic kernel KK on II is a real matrix kernel whose every row is a probability vector in the sense of (1).

A real matrix kernel KK is reversible with respect to weights μ\mu on II if it satisfies detailed balance: μ(i)K(i,j)=μ(j)K(j,i)(i,j∈I).\mu(i)K(i,j)=\mu(j)K(j,i)\qquad(i,j\in I).(2)✦ The weights μ\mu in (2) will be a probability vector, while w:I→ℝw:I\to\mathbb R will provide strictly positive reference weights.

Weighted Entropy and Reverse Tails

For real functions w,pw,p on II, the weighted row entropy ℋw(p)\mathcal H_w(p) is the quantity ℋw(p)=∑j∈Ip(j)log⁡w(j)p(j).\mathcal H_w(p)=\sum_{j\in I}p(j)\log\frac{w(j)}{p(j)}.(3)✦ All logarithms are natural, and entropy summands use the convention 0log⁡0=00\log0=0. For real reference weights ww and real averaging weights μ\mu on II, and a real matrix kernel KK on II, the mean weighted row entropy ℋ¯w(μ,K)\overline{\mathcal H}_w(\mu,K) is the weighted sum ℋ¯w(μ,K)=∑i∈Iμ(i)ℋw(K(i,⋅)),\overline{\mathcal H}_w(\mu,K) =\sum_{i\in I}\mu(i)\mathcal H_w\bigl(K(i,\cdot)\bigr),(4)✦ where the row entropy is given by (3).

For a real matrix kernel KK on II, reference weights w:I→ℝw:I\to\mathbb R, a state i∈Ii\in I and a real threshold parameter aa, the reverse tail set Ba(i)B_a(i) is the subset of II given by Ba(i)={j∈I:K(j,i)<w(i)e−a}.B_a(i)=\{j\in I:K(j,i)<w(i)e^{-a}\}.(5) Its probability in row ii is ∑j∈Ba(i)K(i,j)\sum_{j\in B_a(i)}K(i,j), using the set in (5).

The Claim

Theorem 1 (Lemma 5.2). Let II be finite, let μ\mu be a probability vector on II, and let w(i)>0w(i)>0 for every i∈Ii\in I. Suppose that KK is a stochastic kernel reversible with respect to μ\mu, and that x>0x>0 satisfies K(i,j)≤xw(j)K(i,j)\leq xw(j) for every i,j∈Ii,j\in I. For every real aa, the reverse tail sets of (5) and the mean entropy of (4) satisfy (a+log⁡x)∑i∈Iμ(i)∑j∈Ba(i)K(i,j)≤ℋ¯w(μ,K)+log⁡x.(a+\log x) \sum_{i\in I}\mu(i)\sum_{j\in B_a(i)}K(i,j) \leq \overline{\mathcal H}_w(\mu,K)+\log x.(6)✦

In the paper, the result reads: let HH be a finite simple graph with positive weights ww, cross-mass constant C≥1C\geq1 and associated constant ACA_C, let x≥32x\geq32, let edge parameters satisfy cuv≥1/xc_{uv}\geq1/x and vertex parameters satisfy su≤exs_u\leq e^x, and suppose the unordered triangle mass TH(w)T_H(w) is positive; for the kernels Ku=KujK_u=K_u^j at the common time jj of Lemma 4.1 and random labels Yu,vY_{u,v} with those row laws, the μ\mu-averaged probability that Yu,vY_{u,v} is inadmissible is at most δx=(AC+1)log⁡x/(x+log⁡x)\delta_x=(A_C+1)\log x/(\sqrt{x}+\log x).

What Is Checked

The claim (6) is stated over stochastic real matrix kernels on finite state sets, with detailed balance relative to a probability vector and an entrywise bound relative to strictly positive reference weights.