OctoInformBeta

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

§4: Probability derivative and attained quantiles: The derivative of graph probability is total influence, and interior levels have interior quantiles

Nontrivial increasing properties attain their quantiles.

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 threshold quantile locates a prescribed probability level as the edge bias varies.

Let nn be the number of labelled vertices, and let EnE_n be the set of their two-element subsets, the potential edges.✦ A labelled graph xx on nn labelled vertices is a function x:En→{0,1}x\colon E_n\to\{0,1\}, with xe=1x_e=1 meaning that ee is present.✦ Edge inclusion x⊆yx\subseteq y means that every edge present in xx is present in yy.✦

An increasing graph property ff on labelled graphs is a Boolean function such that f(x)=1f(x)=1 and x⊆yx\subseteq y imply f(y)=1f(y)=1.✦ A nontrivial graph property ff is a Boolean function for which some graph belongs to the property and some graph does not.✦ The real indicator of a Boolean value is 00 for false and 11 for true; in real expressions, f(x)f(x) denotes this indicator.✦

For a real parameter pp, the graph weight wp(x)w_p(x) of a labelled graph xx is the finite product in (1), and the graph mean μp(f)\mu_p(f) of a Boolean graph property ff is the finite weighted sum there: wp(x)=∏e∈En{p,xe=1,1−p,xe=0,μp(f)=∑x∈{0,1}Enwp(x)f(x).w_p(x)=\prod_{e\in E_n} \begin{cases} p,&x_e=1,\\ 1-p,&x_e=0, \end{cases} \qquad \mu_p(f)=\sum_{x\in\{0,1\}^{E_n}}w_p(x)f(x).(1) For 0≤p≤10\leq p\leq1, wp(x)w_p(x) is the probability mass of xx when every potential edge is present independently with probability pp, and μp(f)\mu_p(f) is the probability that the random graph belongs to ff.

Write x⊕ex^{\oplus e} for the graph obtained from xx by toggling ee. For 0≤p≤10\leq p\leq1, the edge influence Ie,p(f)I_{e,p}(f) of an edge ee on a Boolean graph property ff is the probability that toggling ee changes ff, with all other edges independently present with probability pp.✦ The finite expression in (2) defines this influence for real pp; the total influence Ip(f)I_p(f) of a Boolean graph property ff is the sum of its edge influences over potential edges: Ie,p(f)=∑x∈{0,1}Enwp(x)|f(x⊕e)−f(x)|,Ip(f)=∑e∈EnIe,p(f).I_{e,p}(f)=\sum_{x\in\{0,1\}^{E_n}} w_p(x)\lvert f(x^{\oplus e})-f(x)\rvert, \qquad I_p(f)=\sum_{e\in E_n}I_{e,p}(f).(2)

For a real level aa, the threshold quantile pa(f)p_a(f) of a Boolean graph property ff is the infimum of the biases in [0,1][0,1] at which the graph probability is at least aa, as in (3): pa(f)=inf⁡{p∈[0,1]:μp(f)≥a}.p_a(f)=\inf\{p\in[0,1]:\mu_p(f)\geq a\}.(3)✦

The Claim

Theorem 1. Let ff be an increasing graph property on nn labelled vertices. The Russo-Margulis formula (4) holds for every real pp: ddqμq(f)|q=p=Ip(f).\left.\frac{d}{dq}\mu_q(f)\right|_{q=p}=I_p(f).(4)✦ Suppose also that ff is nontrivial. For every a∈[0,1]a\in[0,1], the quantile identity (5) holds: μpa(f)(f)=a.\mu_{p_a(f)}(f)=a.(5)✦ For 0<a<10<a<1, the quantile has the location given by (6): 0<pa(f)<1.0<p_a(f)<1.(6)✦

In the paper, the result reads: for increasing Boolean ff, μp(f)=𝔼pf\mu_p(f)=\mathbb E_p f satisfies ddpμp(f)=Ip(f)\frac{d}{dp}\mu_p(f)=I_p(f); for a nontrivial increasing property, μ0(f)=0\mu_0(f)=0, μ1(f)=1\mu_1(f)=1 and 0<μp(f)<10<\mu_p(f)<1 for 0<p<10<p<1; the variance estimate gives a positive interior derivative, and every 0<a<10<a<1 has an attained interior quantile with μpa(f)(f)=a\mu_{p_a(f)}(f)=a.

What Is Checked

The statements concern Boolean functions on the finite set of labelled graphs, with increasingness defined by edge inclusion and nontriviality requiring both a member and a nonmember.