OctoInformBeta

OpenAI preprint, September 2026 · §4. From influence to threshold width

§4: Integrating log odds: Complementary probability levels are controlled by a logistic differential inequality

From variance estimates to threshold width.

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

For an increasing graph property, the threshold width measures the change in edge density between two prescribed probabilities of membership. The relevant analytic bound concerns the distance between complementary levels of a function whose derivative dominates its value times one minus its value.

Let nn be a nonnegative integer and let V={1,…,n}V=\{1,\ldots,n\} be the labelled vertex set. A potential edge ee on VV is a two-element subset of VV, and En=(V2)E_n=\binom{V}{2} is the set of potential edges.✦ A labelled graph xx on VV is an assignment of a Boolean value to each e∈Ene\in E_n, with true meaning that the edge is present.✦ For labelled graphs xx and yy on VV, edge inclusion x⊆yx\subseteq y means that every edge present in xx is present in yy.✦

A Boolean graph property ff on a labelled vertex set VV is a Boolean-valued function of labelled graphs on VV. An increasing Boolean graph property ff on VV is a Boolean-valued function of labelled graphs on VV such that x⊆yx\subseteq y and f(x)=truef(x)=\mathrm{true} imply f(y)=truef(y)=\mathrm{true}.✦ A nontrivial Boolean graph property ff on VV is a Boolean-valued function of labelled graphs on VV such that some graph belongs to ff and some graph does not.✦ The real indicator of a Boolean value bb is 11 when bb is true and 00 when bb is false; means and variances of ff refer to this indicator.✦

For p∈[0,1]p\in[0,1], let GpG_p be the random graph in which edges are present independently with probability pp. The probability mass wp(x)w_p(x) of a labelled graph xx is the product in (1): wp(x)=∏e∈Enx(e)=truep∏e∈Enx(e)=false(1−p).w_p(x)= \prod_{\substack{e\in E_n\\x(e)=\mathrm{true}}}p \prod_{\substack{e\in E_n\\x(e)=\mathrm{false}}}(1-p).(1)✦ The graph probability μp(f)\mu_p(f) is the probability that GpG_p belongs to ff✦, and Var⁡p(f)\operatorname{Var}_p(f) is the expected squared deviation of its real indicator from its mean, as in (2): μp(f)=ℙ(f(Gp)=true),Var⁡p(f)=𝔼[(𝟏{f(Gp)=true}−μp(f))2].\mu_p(f)=\mathbb P\bigl(f(G_p)=\mathrm{true}\bigr), \qquad \operatorname{Var}_p(f)= \mathbb E\!\left[ \bigl(\mathbf 1_{\{f(G_p)=\mathrm{true}\}}-\mu_p(f)\bigr)^2 \right].(2)

For e∈Ene\in E_n, the edge influence Ie,p(f)I_{e,p}(f) is the probability that toggling ee changes ff, when every other edge is independently present with probability pp.✦ The total influence Ip(f)I_p(f) is the sum of these edge influences in (3): Ip(f)=∑e∈EnIe,p(f).I_p(f)=\sum_{e\in E_n} I_{e,p}(f).(3)✦

For a real level α\alpha, the threshold quantile pα(f)p_\alpha(f) is the infimum of the biases in [0,1][0,1] for which the graph probability is at least α\alpha, as defined in (4): pα(f)=inf⁡{p∈[0,1]:μp(f)≥α}.p_\alpha(f)=\inf\{p\in[0,1]:\mu_p(f)\ge\alpha\}.(4)✦ All logarithms are natural logarithms.

The Claim

Theorem 1. Let a≤ba\le b, C∈ℝC\in\mathbb R and 0<ε<10<\varepsilon<1. Suppose that μ:ℝ→ℝ\mu:\mathbb R\to\mathbb R is continuous on [a,b][a,b], takes values strictly between 00 and 11 there, and is differentiable on (a,b)(a,b). Suppose also that μ(a)=ε\mu(a)=\varepsilon, μ(b)=1−ε\mu(b)=1-\varepsilon, and μ(x)(1−μ(x))≤Cμ′(x)\mu(x)(1-\mu(x))\le C\mu'(x) for every x∈(a,b)x\in(a,b). The logistic transition width satisfies (5): b−a≤2Clog⁡1−εε.b-a\le 2C\log\frac{1-\varepsilon}{\varepsilon}.(5)✦

For 0<ε<1/20<\varepsilon<1/2, the logarithmic comparison is (6): log⁡1−εε≤2log⁡12ε.\log\frac{1-\varepsilon}{\varepsilon} \le 2\log\frac{1}{2\varepsilon}.(6)✦

Let ff be an increasing, nontrivial Boolean graph property on nn labelled vertices. Let C≥0C\ge0 and 0<ε<1/20<\varepsilon<1/2, and suppose that Var⁡p(f)≤CIp(f)\operatorname{Var}_p(f)\le C I_p(f) for every p∈(0,1)p\in(0,1). Its quantile width satisfies (7): p1−ε(f)−pε(f)≤4Clog⁡12ε.p_{1-\varepsilon}(f)-p_\varepsilon(f) \le 4C\log\frac{1}{2\varepsilon}.(7)✦

In the paper, the result reads: with C0=217C_0=2^{17} and n≥2n\ge2, the variance estimate implies ddpμp(f)≥[(log⁡n)2/C0]μp(f)(1−μp(f))\frac{d}{dp}\mu_p(f)\ge[(\log n)^2/C_0]\mu_p(f)(1-\mu_p(f)) on (0,1)(0,1), and for 0<ε<1/20<\varepsilon<1/2 integration of log odds between the ε\varepsilon and 1−ε1-\varepsilon quantiles gives p1−ε(f)−pε(f)≤[2C0/(log⁡n)2]log⁡((1−ε)/ε)p_{1-\varepsilon}(f)-p_\varepsilon(f)\le[2C_0/(\log n)^2] \log((1-\varepsilon)/\varepsilon), with log⁡((1−ε)/ε)≤2log⁡(1/(2ε))\log((1-\varepsilon)/\varepsilon)\le2\log(1/(2\varepsilon)) yielding Theorem 1.1.

What Is Checked

The statements concern real functions on closed intervals with the stated differential inequality, and increasing, nontrivial Boolean properties of labelled graphs with product edge measures and infimum quantiles.