OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

§1: Biased probability, quantiles, variance, and pivotal influence: Product weights give graph probabilities, infimum quantiles, variance, and the influence of changing an edge

Graph probability and pivotal edge influence.

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 graph property on a fixed vertex set is a Boolean function of its possible edges.

Let nn be the number of vertices and let EnE_n be the set of two-element subsets of {1,…,n}\{1,\ldots,n\}.✦ A labelled graph configuration x∈Ωn={0,1}Enx\in\Omega_n=\{0,1\}^{E_n} assigns a presence indicator xex_e to every potential edge e∈Ene\in E_n.✦ For a graph property f:Ωn→{0,1}f:\Omega_n\to\{0,1\}, write f(x)=1f(x)=1 when xx belongs to ff. The real indicator of a Boolean value is the real number that is 00 at false and 11 at true, and these are the values used in real expressions involving ff.✦

For a graph configuration x∈Ωnx\in\Omega_n, an edge e∈Ene\in E_n, and b∈{0,1}b\in\{0,1\}, the modified configuration xe←b∈Ωnx^{e\gets b}\in\Omega_n is the configuration that agrees with xx off ee and has value bb at ee.

The Definition

Definition 1. Let p,a∈ℝp,a\in\mathbb R, let f:Ωn→{0,1}f:\Omega_n\to\{0,1\} be a graph property, and let e∈Ene\in E_n. The graph weight wp(x)w_p(x) of a configuration x∈Ωnx\in\Omega_n is the product in (1): wp(x)=(∏d∈Enxd=1p)(∏d∈Enxd=0(1−p)).w_p(x)= \left(\prod_{\substack{d\in E_n\\x_d=1}}p\right) \left(\prod_{\substack{d\in E_n\\x_d=0}}(1-p)\right).(1)✦ The graph mean μp(f)\mu_p(f) of a graph property f:Ωn→{0,1}f:\Omega_n\to\{0,1\} at a real parameter pp is the weighted sum in (2): μp(f)=∑x∈Ωnwp(x)f(x).\mu_p(f)=\sum_{x\in\Omega_n}w_p(x)f(x).(2)✦ For a real threshold aa and a graph property f:Ωn→{0,1}f:\Omega_n\to\{0,1\}, the infimum quantile pa(f)p_a(f) is the infimum in (3): pa(f)=inf⁡{p∈[0,1]:μp(f)≥a}.p_a(f)=\inf\{p\in[0,1]:\mu_p(f)\ge a\}.(3)✦ The variance Varp(f)\mathrm{Var}_p(f) of a graph property f:Ωn→{0,1}f:\Omega_n\to\{0,1\} at a real parameter pp is the weighted centered second moment in (4): Varp(f)=∑x∈Ωnwp(x)(f(x)−μp(f))2.\mathrm{Var}_p(f)= \sum_{x\in\Omega_n}w_p(x)\bigl(f(x)-\mu_p(f)\bigr)^2.(4)✦ For a real parameter pp, a graph property f:Ωn→{0,1}f:\Omega_n\to\{0,1\}, and an edge e∈Ene\in E_n, the pivotal edge influence Ie,p(f)I_{e,p}(f) is the weighted disagreement in (5): Ie,p(f)=∑x∈Ωnwp(x)|f(xe←1)−f(xe←0)|.I_{e,p}(f)=\sum_{x\in\Omega_n}w_p(x) \left|f(x^{e\gets1})-f(x^{e\gets0})\right|.(5)✦ The total influence Ip(f)I_p(f) of a graph property f:Ωn→{0,1}f:\Omega_n\to\{0,1\} at a real parameter pp is the sum in (6): Ip(f)=∑e∈EnIe,p(f).I_p(f)=\sum_{e\in E_n}I_{e,p}(f).(6)✦

In the paper, the result reads: under independent Bernoulli-pp edges, μp(f)\mu_p(f) is the probability of the property ff; for 0<a<10<a<1, pa(f)=inf⁡{p∈[0,1]:μp(f)≥a}p_a(f)=\inf\{p\in[0,1]:\mu_p(f)\ge a\}; for Boolean ff, Ie,p(f)I_{e,p}(f) is the probability over coordinates other than ee that f(xe←1)≠f(xe←0)f(x^{e\gets1})\ne f(x^{e\gets0}), and Ip(f)I_p(f) is the sum of these influences over edges; variance is the second centered moment.

What Is Checked

These definitions are stated over labelled graph configurations on nn vertices, Boolean graph properties, and individual potential edges, with real parameters pp and aa.