多数決つきの二分探索

命題 5.4（「継続的インテグレーション」§5）・ ✓公理まで証明済み

定理 5.1 の設定で、検査の 1 回の実行が確率 $q < 1/2$ で本当の良・不良と逆の結果を返し、実行の結果は互いに独立とする。 $j \ge 0$ を整数とし、各コミットを $2j + 1$ 回検査して多い方の結果を採用する。

(a) 1 つのコミットの判定が誤る確率 $e_j$ は

e_j \ \le\ q\,\bigl(4q(1-q)\bigr)^{j} \ \le\ \bigl(4q(1-q)\bigr)^{j + 1/2}

を満たす。 $q < 1/2$ より $4q(1-q) < 1$ なので、これは $j$ について指数的に小さくなる。

(b) 二分探索全体が $f$ と異なる答えを返す確率は $\lceil \log_2 n \rceil \cdot q\,(4q(1-q))^{j}$ 以下である。 $q > 0$ のとき、これを $\delta$ 以下にするには

j \ \ge\ \frac{\ln\bigl(q \lceil \log_2 n \rceil / \delta\bigr)}{\ln\bigl(1 / (4q(1-q))\bigr)}

で足りる。 $q$ を固定すると、1 つのコミットあたりの検査の回数 $2j + 1$ は $O(\log(\log n / \delta))$ である。

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 6 件、定義なども含めて 8 件）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

二項定理✓定理 7.3・数え上げと母関数
- 二項係数定義 7.1・数え上げと母関数
最初の不良コミットの二分探索✓定理 5.1・継続的インテグレーション
- 二分探索の正当性✓定理 3.2・探索アルゴリズム
- 二分探索の比較回数✓定理 3.3・探索アルゴリズム
  - 二分探索の正当性✓定理 3.2・探索アルゴリズム
確率測度の基本性質✓定理 4.2・確率空間とコルモゴロフの公理
- σ-加法族が閉じている演算✓命題 3.2・確率空間とコルモゴロフの公理
  - σ-加法族と可測空間定義 3.1・確率空間とコルモゴロフの公理

証明で明示的に参照している定理は、まだありません。