情報科学 › 研究のための計算の実務 › 検算と検証

無作為な反例探索で言える範囲

定理 6.2（「検算と検証」§6）・ ✓公理まで証明済み

入力の集合の上の確率分布を 1 つ固定し、命題の反例である入力の集合の確率を $\theta \in [0, 1]$ とする。この分布に従う独立な $N \ge 1$ 個の標本 $X_1, \ldots, X_N$ を調べる。

反例が 1 つも出ない確率は $(1 - \theta)^N$ で、 $(1 - \theta)^N \le e^{-\theta N}$ 。
$0 \lt \delta \lt 1$ とする。 $\theta \gt \ln(1/\delta)/N$ ならば、反例が 1 つも出ない確率は $\delta$ より小さい。
どの $N$ についても $(1 - \theta)^N \ge 1 - N\theta$ 。とくに $\theta \le 1/(100N)$ である偽の命題（ $\theta \gt 0$ ）は、確率 $0.99$ 以上で反例が出ないまま検査を通過する。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

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

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

前提をたどる証明が使う定理・定義（直接 2 件）

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

確率変数の独立性定義 2.3・確率変数と期待値
導関数の符号と単調性✓系 3.4・平均値の定理とテイラーの定理
- ラグランジュの平均値の定理✓定理 3.3・平均値の定理とテイラーの定理
  - ロルの定理✓定理 3.1・平均値の定理とテイラーの定理
    最大値・最小値の定理✓定理 2.3・平均値の定理とテイラーの定理この先をたどる →
    極大・極小定義 2.1・平均値の定理とテイラーの定理
    フェルマーの補題✓補題 2.5・平均値の定理とテイラーの定理この先をたどる →

これを使っている定理証明で参照している 2 件

検出確率と必要な試行回数✓定理 3.2・性質ベーステスト
ペアワイズ網羅の大きさ✓定理 5.2・テストの理論

関連するノック 3 問