情報科学 › ソフトウェア設計とテスト › 性質ベーステスト

検出確率と必要な試行回数

定理 3.2（「性質ベーステスト」§3） ・ ✓公理まで証明済み

性質 φ\varphi の生成分布 μ\mu のもとでの失敗率を θ∈[0,1]\theta \in [0, 1] とし、X1,X2,…X_1, X_2, \ldots を分布 μ\mu に従う独立な入力とする。N≥1N \ge 1 について、X1,…,XNX_1, \ldots, X_N の中に少なくとも 1 つ反例がある事象を DND_N とする。

  1. P(DN)=1−(1−θ)N≥1−e−θNP(D_N) = 1 - (1 - \theta)^N \ge 1 - e^{-\theta N}。
  2. 0<δ<10 \lt \delta \lt 1、θ>0\theta \gt 0 とする。N≥ln⁡(1/δ)/θN \ge \ln(1/\delta)/\theta ならば P(DN)≥1−δP(D_N) \ge 1 - \delta。
  3. 0<δ<10 \lt \delta \lt 1、θ>0\theta \gt 0 とする。N<(1−δ)/θN \lt (1 - \delta)/\theta ならば P(DN)<1−δP(D_N) \lt 1 - \delta。
  4. 0<θ<10 \lt \theta \lt 1 とする。最初の反例が現れる番号を τ\tau とすると、P(τ=k)=(1−θ)k−1θP(\tau = k) = (1 - \theta)^{k-1}\theta（k=1,2,…k = 1, 2, \ldots）で、E[τ]=1/θE[\tau] = 1/\theta。

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

閉包の状態

✓ 公理まで証明済み

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

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

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

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

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

関連するノック 3 問