ブール関数の分散と変数の影響力を、Python の標準ライブラリだけで計算します。対象はビットの平均値、正規化した和、多数決の 3 種類です。各関数について入力を全列挙し、計算した値が理論式に一致することを確認します。
この 3 種類は、値域の一様有界性、分散の正の下限、次数の固定上界のうち、それぞれ 1 条件を外した反例になっています。数値計算によって、関数がどの条件を保ちながら最大影響力を小さくするかを追跡できます。
検証する三つの関数と成立条件
長さ $N$ の入力を $x=(x_1,\ldots,x_N)\in\{0,1\}^N$ とします。入力は $2^N$ 通りから一様に選ばれます。実数値関数 $f$ の分散は、平均値からの差の二乗平均です。また、$x^{(i)}$ を第 $i$ ビットだけ反転した入力とすると、影響力は反転前後の出力差の二乗平均です[1]。
V(f)=\mathbb{E}_X\left[(f(X)-\mathbb{E}_X[f(X)])^2\right]
I_i(f)=\mathbb{E}_X\left[(f(X)-f(X^{(i)}))^2\right]
ここでは最大影響力 $I_{\max}(f)=\max_i I_i(f)$ を比較します。
ビットの平均値
p_N(x)=\frac{1}{N}\sum_{i=1}^{N}x_i
値域は常に $[0,1]$ で、次数は 1 です。一様分布上では次の式が成り立ちます。
V(p_N)=\frac{1}{4N},\qquad I_{\max}(p_N)=\frac{1}{N^2}
入力数が増えると分散が 0 に近づきます。分散の正の下限を外した例です。
正規化した和
g_N(x)=\frac{1}{\sqrt{N}}\sum_{i=1}^{N}(2x_i-1)
次数は 1、分散は 1 のままですが、値域は $[-\sqrt{N},\sqrt{N}]$ まで広がります。つまり、すべての $N$ に共通する一定の値域上界を持ちません。
V(g_N)=1,\qquad I_{\max}(g_N)=\frac{4}{N}
多数決
奇数 $N$ について、1 のビット数が過半数なら 1、それ以外なら 0 とします。
m_N(x)=\begin{cases}
1 & \text{if }\sum_{i=1}^{N}x_i>N/2,\\
0 & \text{otherwise}.
\end{cases}
値域は $\{0,1\}$、分散は $1/4$ ですが、次数は $N$ です。
V(m_N)=\frac14,\qquad
I_{\max}(m_N)=\frac{\binom{N-1}{(N-1)/2}}{2^{N-1}}
多数決では、注目するビット以外の $N-1$ ビットが同数に分かれた場合にだけ、そのビットを反転すると結果が入れ替わります。最大影響力は $N^{-1/2}$ のオーダーで 0 に近づきます。これらの反例と、低次数・値域・分散の条件が持つ意味は、ブール関数の解析と量子問い合わせ計算量の文脈でも扱われています[2]。
Python 3.12 で全入力を列挙する
検証する入力数は $N=3,5,7,9,11$ です。多数決で同数の場合を避けるため、奇数に統一します。必要な外部パッケージはありません。
python3 --version
python3 boolean_influence.py
以下を boolean_influence.py として保存して実行します。itertools.product が生成するタプルは、二進数の数値順に並びます。そのため、生成順の添字をビット反転マスクと XOR すれば、反転後の関数値を配列から参照できます。product の列挙順は Python の公式文書に基づきます[3]。
from itertools import product
from math import comb, isclose, sqrt
SIZES = (3, 5, 7, 9, 11)
TOLERANCE = 1e-12
def bit_mean(bits):
return sum(bits) / len(bits)
def normalized_sum(bits):
return sum(2 * bit - 1 for bit in bits) / sqrt(len(bits))
def majority(bits):
return int(2 * sum(bits) > len(bits))
def evaluate(function, n):
# product() visits bit strings in the same order as their binary indices.
values = [function(bits) for bits in product((0, 1), repeat=n)]
count = len(values)
mean = sum(values) / count
variance = sum((value - mean) ** 2 for value in values) / count
influences = []
for i in range(n):
mask = 1 << (n - 1 - i)
influences.append(
sum((value - values[index ^ mask]) ** 2
for index, value in enumerate(values)) / count
)
return values, variance, max(influences)
def majority_top_coefficient(n):
return sum(
(-1) ** (n - sum(bits)) * majority(bits)
for bits in product((0, 1), repeat=n)
)
def check_close(actual, expected):
if not isclose(actual, expected, rel_tol=TOLERANCE, abs_tol=TOLERANCE):
raise AssertionError((actual, expected))
def main():
cases = (
("mean", bit_mean),
("sum", normalized_sum),
("majority", majority),
)
print("N function V(calc) V(theory) Imax(calc) Imax(theory)")
for n in SIZES:
for name, function in cases:
values, variance, max_influence = evaluate(function, n)
if name == "mean":
expected_v, expected_i = 1 / (4 * n), 1 / n**2
check_close(min(values), 0)
check_close(max(values), 1)
elif name == "sum":
expected_v, expected_i = 1.0, 4 / n
check_close(min(values), -sqrt(n))
check_close(max(values), sqrt(n))
else:
expected_v = 0.25
expected_i = comb(n - 1, (n - 1) // 2) / 2 ** (n - 1)
check_close(min(values), 0)
check_close(max(values), 1)
expected_coefficient = (-1) ** ((n - 1) // 2) * comb(
n - 1, (n - 1) // 2
)
actual_coefficient = majority_top_coefficient(n)
if actual_coefficient != expected_coefficient:
raise AssertionError((actual_coefficient, expected_coefficient))
check_close(variance, expected_v)
check_close(max_influence, expected_i)
print(
f"{n:2d} {name:9s} {variance:10.6f} {expected_v:12.6f}"
f" {max_influence:12.6f} {expected_i:13.6f}"
)
print("All checks passed.")
if __name__ == "__main__":
main()
math.comb で多数決関数の理論的な影響力を計算し、math.isclose で計算値との一致を検査します。math.sqrt は正規化した和に使います。いずれも Python 標準ライブラリの関数です[4]。
分散と変数の影響力を計算する
evaluate() は、全入力に対する関数値を最初に一度だけ計算します。分散では、$2^N$ 個の関数値の平均を求め、その平均からの二乗差を $2^N$ で割ります。標本分散の不偏補正は行いません。 対象は抽出標本ではなく、有限の入力集合全体だからです。
影響力では、位置 $i$ に対応する mask = 1 << (n - 1 - i) を使います。例えば $N=3$ の 001 は、第 1 ビットを反転すると 101 となり、二進数の添字は 1 ^ 4 = 5 に移ります。この方式では、各入力と各ビットについて、反転後の値を定数時間の配列参照で取得できます。
check_close() は理論値との不一致を AssertionError として検出します。また、各関数の最小値・最大値を調べて、想定した値域も確認します。
多数決関数については、全変数の積 $x_1x_2\cdots x_N$ の係数も検査します。多重線形多項式におけるその係数は次のとおりです。
\sum_{k=(N+1)/2}^{N}(-1)^{N-k}\binom Nk
=(-1)^{(N-1)/2}\binom{N-1}{(N-1)/2}\ne0
最高次の係数が 0 でないため、$\deg(m_N)=N$ と判定できます。majority_top_coefficient() は全入力の関数値からこの係数を計算し、組合せ数による理論値と一致することを検査します。
三つの反例を理論値と照合する
次は Python 3.13.5 で実行した結果です。コードの構文と使用した標準ライブラリの機能は Python 3.12 に対応していますが、実測に使用した処理系のバージョンは区別して記載します。
N function V(calc) V(theory) Imax(calc) Imax(theory)
3 mean 0.083333 0.083333 0.111111 0.111111
3 sum 1.000000 1.000000 1.333333 1.333333
3 majority 0.250000 0.250000 0.500000 0.500000
5 mean 0.050000 0.050000 0.040000 0.040000
5 sum 1.000000 1.000000 0.800000 0.800000
5 majority 0.250000 0.250000 0.375000 0.375000
7 mean 0.035714 0.035714 0.020408 0.020408
7 sum 1.000000 1.000000 0.571429 0.571429
7 majority 0.250000 0.250000 0.312500 0.312500
9 mean 0.027778 0.027778 0.012346 0.012346
9 sum 1.000000 1.000000 0.444444 0.444444
9 majority 0.250000 0.250000 0.273438 0.273438
11 mean 0.022727 0.022727 0.008264 0.008264
11 sum 1.000000 1.000000 0.363636 0.363636
11 majority 0.250000 0.250000 0.246094 0.246094
All checks passed.
各行の V(calc) と V(theory)、Imax(calc) と Imax(theory) は一致しました。計算値を小数点以下 6 桁で表示していますが、判定には表示前の浮動小数点数を使用し、相対誤差・絶対誤差の許容値をともに $10^{-12}$ に設定しています。
例えば $N=5$ では、ビット平均の分散が 0.05、最大影響力が 0.04 です。正規化した和は分散を 1 に保ちつつ最大影響力が 0.8 となり、多数決は分散 0.25、最大影響力 0.375 となります。
入力数の増加による最大影響力の減少を確認する
| 関数 | $N=3$ | $N=5$ | $N=7$ | $N=9$ | $N=11$ |
|---|---|---|---|---|---|
| ビット平均 | 0.111111 | 0.040000 | 0.020408 | 0.012346 | 0.008264 |
| 正規化した和 | 1.333333 | 0.800000 | 0.571429 | 0.444444 | 0.363636 |
| 多数決 | 0.500000 | 0.375000 | 0.312500 | 0.273438 | 0.246094 |
三つの関数の最大影響力はいずれも減少していますが、保たれる条件は異なります。ビット平均では分散が $1/(4N)$ へ減少し、正規化した和では値域の幅が $2\sqrt N$ へ増加します。多数決では次数そのものが $N$ に増えます。
値域の固定、分散の正の下限、次数の固定上界を同時に課すと、これら三つの関数列はすべて対象から外れます。各条件を一つずつ外す必要性が、計算結果と式の両方から確認できます。
全列挙による検証の計算量と限界
evaluate() は $2^N$ 個の関数値を保持します。各変数についてすべての入力の反転差を計算するため、時間計算量は $O(N2^N)$、値を保持する領域は $O(2^N)$ です。$N=11$ では 2,048 個の入力を扱いますが、$N=30$ になると約 10.7 億個の入力が必要になります。
また、今回の照合は 5 種類の入力数に対する個別の計算結果です。最大影響力が 0 に収束するという一般的な結論は、上で示した理論式と漸近評価に依拠します。有限回の数値実験で一般定理を証明したと扱うことはできません。
Turturean の結果は、値域が $[0,1]$、次数が高々 $d\ge1$、分散が正である多項式について、入力数に直接依存しない影響力の正の下界を与えるものです[5]。今回の三つの関数列は、定理の仮定を一つ外したときに何が起こるかを再現するものであり、この一般定理の証明とは役割が異なります。
まとめ
Python の全列挙によって、三つの関数の分散と最大影響力を理論式に照合できました。ビット平均では分散、正規化した和では値域の一様な上限、多数決では次数の固定上界がそれぞれ失われます。そのいずれの場合も、最大影響力を 0 に近づける関数列を構成できます。
今回の実装では、関数値の配列を一度作り、ビット反転を XOR で参照するだけで、定義式に沿った検査を行えます。有限の入力に対する再現可能な数値検証と、一般の関数に対する数学的な保証とを区別することが、結果を解釈する際の判断基準です。
参考文献
- Ryan O'Donnell, Analysis of Boolean Functions（2014-06-05）. https://www.cambridge.org/core/books/analysis-of-boolean-functions/B05A66E4DCC778E02B84C16376F4D1FD
- id774, 量子計算の受理確率は古典計算でも多項式回の問い合わせで近似できる（2026-11-10）. https://blog.id774.net/entry/2026/11/10/5863/
- Python Software Foundation, itertools — Functions creating iterators for efficient looping. https://docs.python.org/3.12/library/itertools.html
- Python Software Foundation, math — Mathematical functions. https://docs.python.org/3.12/library/math.html
- David Turturean, A proof of the Aaronson-Ambainis conjecture（2026-11-06）. https://arxiv.org/abs/2611.09773