論文「Fast Algorithms for Exact Confidence Intervals in Randomized Experiments with Binary Outcomes」の技術的サマリー

この論文は、二値アウトカム（Binary Outcomes）を持つランダム化実験において、平均処置効果（ATE）に対する厳密な信頼区間を構築するための高速アルゴリズムを提案しています。従来の大規模サンプル近似に依存しない手法であり、任意のサンプルサイズに対して有効な信頼区間を、計算コストを劇的に削減して算出可能にします。

以下に、問題設定、手法、主要な貢献、結果、および意義について詳細にまとめます。

1. 問題設定と背景

• 目的: ランダム化実験（医療、教育、経済、コンピュータサイエンスなど）において、有限母集団における平均処置効果（ATE）$\tau$ に対する $(1-\alpha)$ 信頼区間を構築すること。
• 課題:
  • 従来の信頼区間構築法（中心極限定理に基づく漸近近似など）は、サンプルサイズが小さい場合や分布が偏っている場合に精度が低下する。
  • ランダム化推論に基づく厳密な信頼区間は、任意のサンプルサイズで有効であるが、計算コストが極めて高い。
  • 厳密な区間は、観測データと整合するすべての潜在的なアウトカム構成（Potential Outcome Configurations）に対してランダム化検定を反転させることで得られる。探索空間が指数的に増大するため、単純な全探索（Brute-force）は非現実的。
• 対象とする割り当て設計:
  1. バランス型ベルヌーイ設計 (Balanced Bernoulli Design): 各単位が独立に処置群または対照群に割り当てられる（確率 $p=1/2$ の場合、期待値として群サイズが均衡）。
  2. マッチドペア設計 (Matched-pairs Design): 共変量に基づいてペアを形成し、各ペア内でランダムに処置を割り当てる。

2. 主要な手法とアルゴリズム

論文の核心は、**ランダム化検定の反転（Inversion of Randomization Tests）**における計算複雑性の劇的な削減にあります。

2.1 基本的なアプローチ

• 候補となる ATE の値 $\tau_0$ に対して、観測データと整合するすべての潜在的なアウトカム構成 $\tilde{Y}$ について、鋭い帰無仮説（Sharp Null Hypothesis）$H_0: Y = \tilde{Y}$ に対するランダム化検定の $p$ 値を計算する。
• 最大 $p$ 値 $p_{\max}(\tau_0)$ が $\alpha$ 以上であれば、$\tau_0$ を信頼集合 $I_\alpha$ に含める。
• 従来の手法では、整合する構成の数を全探索する必要があり、計算量が膨大だった。

2.2 高速化の鍵：単調性と分散性の利用

著者は、バランス型ベルヌーイ設計とマッチドペア設計の対称性と独立性を利用し、以下の重要な性質を導き出しました。

• 中心化された検定統計量の分布: 整合するアウトカム構成に対応する検定統計量は、独立したラデマッハー変数（Rademacher variables）と半ラデマッハー変数の和として表現でき、ポアソン二項分布の特殊なケースとなる。
• 単調性 (Monotonicity): 整合するアウトカム構成の数（カウントベクトル）を変化させたとき、$p$ 値は特定の方向に単調に変化する。
• 最適解の位置: 最大 $p$ 値を与える構成は、整合する構成集合の**境界点（Boundary Points）**のいずれかに存在する。具体的には、集合 $A_0$（$b=0$ の場合）と $A_1$（$b \ge 1$ の場合）のそれぞれにおいて、辞書式順序で最大の要素（Lexicographically largest element）のみをチェックすればよい。

2.3 アルゴリズムのステップ

1. 二値探索 (Binary Search): 候補集合 $T$ 上で $p_{\max}(\tau_0)$ の単調性を利用して、信頼区間の端点を特定する。これにより、評価が必要な $\tau_0$ の数を $O(\log n)$ に削減。
2. 最大 $p$ 値の計算 (ComputePmax):
   • 各 $\tau_0$ に対して、整合するカウントベクトル $(a, b)$ の境界点（最大値）を $O(1)$ の時間で特定する（整数計画法または単純な計算式による）。
   • 特定された $(a, b)$ に対して、ポアソン二項分布の尾部確率（$p$ 値）を計算する。
3. FFT の利用: ポアソン二項分布の累積分布関数（CDF）を、高速フーリエ変換 (FFT) を用いて $O(n \log n)$ で正確に計算する（モンテカルロシミュレーションではなく、決定論的かつ正確な計算）。

3. 主要な貢献と定理

• 定理 1.1 (計算量): バランス型ベルヌーイ設計およびマッチドペア設計において、厳密な信頼区間は高々 $8 \log_2 n$ 回のランダム化検定で構築可能である。
  • 従来の全探索（$\Theta(n^4)$ 回）や、完全ランダム化設計における最速手法（$O(n \log n)$ 回）と比較して、指数的な高速化を実現。
• 定理 1.2 (情報理論的下界): 任意の設計において、厳密な信頼区間を構築する決定論的アルゴリズムは、最悪ケースで $\Omega(\log n)$ 回のランダム化検定が必要である。
  • 提案アルゴリズムの $O(\log n)$ は、この下界と一致しており、最適であることを示している。
• 定理 1.3 (総計算時間): バランス型ベルヌーイ設計およびマッチドペア設計において、信頼区間の構築時間は $O(n \log^2 n)$ である。
• 一般ベルヌーイ設計への拡張 (定理 1.4): 処置割り当て確率 $p$ が $1/2$ ではない一般の場合でも、$O(n^2)$ 回の検定で構築可能（完全ランダム化設計の一般ケースと同様の複雑度）。

4. 実験結果と性能

• シミュレーション:
  • 小規模サンプル ($n$ が小さい場合) において、提案アルゴリズム（アルゴリズム 1）と全探索法を比較。全探索は $n$ が増えると計算不可能になるが、提案手法は極めて少ない検定回数（例：$n=1000$ で 9 回など）で実行可能。
  • 漸近近似（Wald 区間）と比較。特にスパースなアウトカム（稀な事象）や非対称な分布において、Wald 区間はカバレッジ（被覆率）が不足する（Under-coverage）傾向があるのに対し、提案手法は任意のサンプルサイズで保証されたカバレッジを提供する。
• 実行時間:
  • $n=1000$ の 10,000 回シミュレーションにおいて、バランス型ベルヌーイ設計では 1.5 分未満、マッチドペア設計では 2 時間未満で完了（マッチドペアでは整数計画法の求解が必要となるため若干時間がかかるが、依然として実用的）。

5. 意義と結論

• 設計間の明確な分離: バランス型ベルヌーイ設計やマッチドペア設計は、完全ランダム化設計とは異なり、単位間の独立性構造が強く、これにより $O(\log n)$ という極めて効率的な計算が可能になることを示した。
• 実用性の向上: 従来「計算的に不可能」と考えられていた大規模なランダム化実験（特にオンライン A/B テストや分散型実験）においても、厳密な信頼区間を現実的な時間で算出可能にした。
• 理論的貢献: 情報理論的下界との一致により、この計算効率の限界が理論的に最適であることを証明した。
• オープンソース: 提案アルゴリズムの Python 実装が GitHub で公開されており、研究者や実務者がすぐに利用可能。

この論文は、ランダム化実験の統計的推論において、「厳密性（Exactness）」と「計算効率（Efficiency）」の両立を達成した画期的な成果と言えます。