OctoInformBeta

OpenAI preprint, September 2026 · Section 4. Local walks and entropy

Lemma 4.1: Reversibility and entropy bounds give a common time of small average total variation

Local walk smoothing controls neighboring rows.

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

Fixing a vertex uu, the local walk moves between adjacent vertices of its neighborhood N(u)N(u). Its successive distributions can be compared when their starting vertices complete a triangle with uu. Lemma 4.1 concerns these comparisons after adding holding steps, with weighted entropy controlling the choice of a common time.

Let G=(V,E)G=(V,E) be a finite simple graph with positive vertex weights wvw_v. The neighborhood N(u)N(u) of a vertex uu in GG is the set of vertices adjacent to uu.✦ For a vertex set S⊆VS\subseteq V and vertices u,v∈Vu,v\in V, the vertex mass w(S)w(S), neighborhood mass sus_u and common neighborhood mass cuvc_{uv} are, respectively, w(S)=∑v∈Swv,su=w(N(u)),cuv=w(N(u)∩N(v)).w(S)=\sum_{v\in S}w_v,\qquad s_u=w(N(u)),\qquad c_{uv}=w(N(u)\cap N(v)).(1) The cross mass ew(S,D)e_w(S,D) of two vertex sets S,D⊆VS,D\subseteq V, which may overlap, is the sum of the products of endpoint weights over ordered adjacent pairs with first vertex in SS and second vertex in DD: ew(S,D)=∑u∈S,v∈Duv∈Ewuwv.e_w(S,D)=\sum_{\substack{u\in S,\ v\in D\\uv\in E}}w_uw_v.(2)✦ For a real parameter tt, the growth function gtg_t is the function on nonnegative real arguments given by gt(a)={a(t+max⁡{0,log⁡(1/a)}),a>0,0,a=0.g_t(a)= \begin{cases} a\bigl(t+\max\{0,\log(1/a)\}\bigr),&a>0,\\ 0,&a=0. \end{cases}(3)✦ The cross mass bound with constant CC is the condition that, for every t≥1t\ge1 and every S,D⊆VS,D\subseteq V with w(S),w(D)≤etw(S),w(D)\le e^t, ew(S,D)≤Cgt(w(S)).e_w(S,D)\le Cg_t(w(S)).(4)✦

The oriented edge state set is ℰ={(u,v):uv∈E}\mathcal E=\{(u,v):uv\in E\}; uu is the tail and vv the head of (u,v)(u,v). The local walk normalizer ZZ and edge law π\pi are Z=∑(u,v)∈ℰwuwvcuv,π(u,v)=wuwvcuvZ.Z=\sum_{(u,v)\in\mathcal E}w_uw_vc_{uv},\qquad \pi(u,v)=\frac{w_uw_vc_{uv}}{Z}.(5) The neighborhood transition kernel PP is the real matrix on ℰ\mathcal E given by P((u,v),(a,y))={wy/cuv,a=uandvy∈E,0,otherwise.P\bigl((u,v),(a,y)\bigr)= \begin{cases} w_y/c_{uv},&a=u\ \text{and}\ vy\in E,\\ 0,&\text{otherwise}. \end{cases}(6)✦ The reference weight aa on the oriented edge set ℰ\mathcal E is the function assigning to each edge (u,v)(u,v) the weight of its head vertex: a(u,v)=wv.a(u,v)=w_v.(7)✦ For the law (5), assume that GG has an edge and cuv>0c_{uv}>0 on every edge.

Kernels and Entropy

A real kernel KK on a finite state set II is a real matrix indexed by I×II\times I.✦ A probability vector pp on a finite state set II is a real vector with nonnegative entries summing to one.✦ A real kernel KK on II is stochastic when each row is a probability vector.✦ A real weight vector ρ\rho on a finite state set II is stationary for a real kernel KK on II when the incoming mass at each state equals its weight; the kernel KK is reversible for ρ\rho when detailed balance holds: pi≥0(i∈I),∑i∈Ipi=1,∑i∈IρiK(i,k)=ρk(k∈I),ρiK(i,k)=ρkK(k,i)(i,k∈I).\begin{aligned} &p_i\ge0\ (i\in I),\qquad \sum_{i\in I}p_i=1,\\ &\sum_{i\in I}\rho_iK(i,k)=\rho_k\quad(k\in I),\\ &\rho_iK(i,k)=\rho_kK(k,i)\quad(i,k\in I). \end{aligned}(8) For a real kernel KK on a finite state set II, the lazy kernel L(K)L(K) and the smoothed kernels Sj(K)S_j(K) are the matrices given by L(K)(i,k)=𝟏i=k+K(i,k)2,Sj(K)=L(K)j(j≥0).L(K)(i,k)=\frac{\mathbf1_{i=k}+K(i,k)}2,\qquad S_j(K)=L(K)^j\quad(j\ge0).(9) Write Qj=Sj(P)Q_j=S_j(P) for the smoothing (9) of the local kernel (6).

For positive reference weights bb and probability vectors p,qp,q on a finite state set II, the weighted row entropy hb(p)h_b(p) and the total variation distance TV⁡(p,q)\operatorname{TV}(p,q) are the real quantities given by hb(p)=∑i∈Ipilog⁡bipi,TV⁡(p,q)=12∑i∈I|pi−qi|.h_b(p)=\sum_{i\in I}p_i\log\frac{b_i}{p_i},\qquad \operatorname{TV}(p,q)=\frac12\sum_{i\in I}|p_i-q_i|.(10) All logarithms are natural, and zero entries contribute zero to the entropy in (10). The mean weighted row entropy h¯ρ,b(K)\overline h_{\rho,b}(K) of a kernel KK on a finite state set II, with averaging weights ρ\rho and positive reference weights bb, is the weighted sum of its row entropies given by h¯ρ,b(K)=∑i∈Iρihb(K(i,⋅)).\overline h_{\rho,b}(K)=\sum_{i\in I}\rho_i h_b(K(i,\cdot)).(11)✦

For the local walk, the average entropy HjH_j and the mean neighboring row distance DjD_j are the weighted averages given below, with edge law (5), reference weights (7) and mean entropy (11): Hj=h¯π,a(Qj),Dj=∑e∈ℰπ(e)∑f∈ℰP(e,f)TV⁡(Qj(e,⋅),Qj(f,⋅)).H_j=\overline h_{\pi,a}(Q_j),\qquad D_j=\sum_{e\in\mathcal E}\pi(e) \sum_{f\in\mathcal E}P(e,f) \operatorname{TV}(Q_j(e,\cdot),Q_j(f,\cdot)).(12)

For the cross mass constant CC, the exceptional mass constant ECE_C, entropy bound constant ACA_C and smoothing bound constant BCB_C are the real numbers given by EC=42C2+2C,AC=10+EC,BC=2AC+1.E_C=42C^2+2C,\qquad A_C=10+E_C,\qquad B_C=2\sqrt{A_C+1}.(13)

The Claim

Theorem 1. Let GG be a finite simple graph with positive vertex weights. If GG has an edge and cuv>0c_{uv}>0 on every edge, then the local transition is reversible for its edge law: π(e)P(e,f)=π(f)P(f,e)(e,f∈ℰ).\pi(e)P(e,f)=\pi(f)P(f,e)\qquad(e,f\in\mathcal E).(14)✦ For any real kernel KK on a finite state set and real weights ρ\rho for which KK is reversible, every nonnegative integer jj satisfies ρiSj(K)(i,k)=ρkSj(K)(k,i)(i,k∈I).\rho_iS_j(K)(i,k)=\rho_kS_j(K)(k,i)\qquad(i,k\in I).(15)✦ If x>0x>0 and cuv≥1/xc_{uv}\ge1/x on every edge of GG, then, for every nonnegative integer jj, Qj(e,f)≤xa(f)(e,f∈ℰ).Q_j(e,f)\le x a(f)\qquad(e,f\in\mathcal E).(16)✦ If, in addition, GG has an edge and su≤exs_u\le e^x for every vertex uu, then every nonnegative integer jj satisfies −log⁡x≤Hj.-\log x\le H_j.(17)✦ For any finite state set, a stationary probability vector ρ\rho for a stochastic kernel KK, and positive reference weights bb, smoothing has monotone mean weighted row entropy: h¯ρ,b(Sj(K))≤h¯ρ,b(Sk(K))(0≤j≤k).\overline h_{\rho,b}(S_j(K))\le\overline h_{\rho,b}(S_k(K)) \qquad(0\le j\le k).(18)✦ Suppose that GG has an edge, C≥0C\ge0, the cross mass bound (4) holds, x≥32x\ge32, cuv≥1/xc_{uv}\ge1/x on every edge, and su≤exs_u\le e^x for every vertex. For every nonnegative integer j≤2xj\le2x, Hj≤AClog⁡x.H_j\le A_C\log x.(19)✦ Under these hypotheses with C≥1C\ge1, there is a nonnegative integer j<⌈x⌉j<\lceil x\rceil such that Hj≤AClog⁡xandDj≤BClog⁡xx.H_j\le A_C\log x \quad\text{and}\quad D_j\le B_C\sqrt{\frac{\log x}{x}}.(20)✦

In the paper, the result reads: under positive vertex weights, C≥1C\ge1, the cross mass bound, the presence of an edge, x≥32x\ge32, su≤exs_u\le e^x and cuv≥1/xc_{uv}\ge1/x on edges, with the constants EC,AC,BCE_C,A_C,B_C of (13) and R=⌈x⌉R=\lceil x\rceil, the local kernels KujK_u^j on N(u)N(u) are reversible with stationary measures πu\pi_u and satisfy Kuj(v,y)≤xwyK_u^j(v,y)\le xw_y for every j≥0j\ge0, their averaged weighted row entropies satisfy −log⁡x≤H0≤H1≤⋯≤HR≤AClog⁡x-\log x\le H_0\le H_1\le\cdots\le H_R\le A_C\log x, and there is a single j∈{0,…,R−1}j\in\{0,\ldots,R-1\} for which the ordered-triangle average of TV⁡(Kuj(v,⋅),Kuj(z,⋅))\operatorname{TV}(K_u^j(v,\cdot),K_u^j(z,\cdot)) is at most BClog⁡x/xB_C\sqrt{\log x/x}.

What Is Checked

The local assertions (14), (16), (17), (19) and (20) are stated over the oriented edges of a finite simple graph with positive vertex weights; their edge law, transition and reference weights are (5), (6) and (7). The hypotheses use the masses (1), the cross mass (2), and the growth function (3) in (4).

The general kernel assertions (15) and (18) concern the matrix powers (9) on any finite state set. Detailed balance in (8) alone is assumed in (15); (18) concerns the mean entropy (11) of a stochastic kernel with a stationary probability vector and positive reference weights. The local entropy and variation estimates concern the finite sums (12).