継続的インテグレーション：パイプライン・不安定なテスト・二分探索とまとめ検査

情報科学ソフトウェア設計とテスト第5章学部無料公開約 44 分2026-10-08

対象読者: 本テーマのビルドと依存関係の章、Git のブランチと併合、二分探索を学び、学部の確率（独立性・期待値）を知っている人。CI サービスの利用経験は仮定しません。

前提となる記事:ビルドと依存関係：依存グラフ・増分ビルドの正しさ・版の解決、バージョン管理システム Git：Merkle DAG としての履歴と共同開発フロー、探索アルゴリズム：二分探索の O(log n) とハッシュ表の平均 O(1)

生 Markdown

0. この記事の要点

チームで1つのプログラムを作るとき、全員が自分の手元でテストを通してから共有の本流に変更を入れても、入れた結果が壊れていることがあります。この記事は、なぜそうなるのか、壊れたときにどの変更が原因かを少ない検査の回数で見つけるにはどうするか、検査の待ち時間をどう減らすかを、確率と帰納法で確かめます。読み終えると、継続的インテグレーションの各仕組みがどんな条件のもとで何を保証し、どこで保証が切れるかを説明できるようになります。

継続的インテグレーション（CI）が守るものは、「主ブランチの先頭は常に全検査に合格している」という不変条件（いつでも成り立っていてほしい約束）です。変更ごとに検査しても、併合した結果を検査しなければ、この不変条件は破れます（定理 3.1）。併合した結果を検査してから先頭を進めるマージキューは、検査が決定的であるかぎり不変条件を保ちます（定理 3.3）。
各々が確率 $q$ で誤って落ちる独立な $n$ 個のテストは、正しいコードでも確率 $1 - (1-q)^n$ で落ちます。 $n = 1000$ 、 $q = 10^{-3}$ で約 $63\%$ です。再実行はこれを下げますが、同じ式で本物の不具合の見逃しを増やします（定理 4.1）。
「あるコミット以降はすべて不良」という単調性があれば、 $n$ 個のコミットの中の最初の不良は $\lceil \log_2 n \rceil$ 回の検査で特定でき、これより少なくはできません（定理 5.1）。検査が確率 $q < 1/2$ で誤るときは、多数決で誤りを指数的に抑えられます（命題 5.4）。
各変更が独立に確率 $p$ で不良のとき、 $b$ 個をまとめて検査すると、1 変更あたりの期待検査回数は $1/b + 1 - (1-p)^b$ です。最適な $b$ は $1/\sqrt{p}$ の程度、回数は $2\sqrt{p}$ の程度で、 $p$ が約 $0.31$ を超えるとまとめないほうがよくなります（定理 6.2）。
所要時間 $t_i$ 、失敗確率 $f_i$ の段階は、 $t_i / f_i$ の小さい順に並べると期待所要時間が最小になります（命題 7.2）。
目標の状態を宣言して差分を適用するデプロイは冪等（何度実行しても結果が同じ）で、途中で失敗しても再実行で同じ状態に収束します（命題 8.2）。

1. 動機：全員の手元で通っていたのに、主ブランチが壊れている

5 人のチームで、各自が自分のブランチでテストを通してから主ブランチに併合しているとします。それでも月に何度か、主ブランチの先頭でテストが落ちます。誰の変更も単独では通っていたのに、です。原因はおおむね 3 つに分かれます。

2 つの変更が、それぞれは正しいのに、合わせると正しくない（意味的な衝突）。
テストが、コードが同じでも通ったり落ちたりする（不安定なテスト）。
手元の環境と、ほかの人の環境・公開先の環境が違う（密閉性の破れ）。

3 は前章の主題でした。この章は 1 と 2 を扱い、さらに「壊れたときにどのコミットが原因かを最小の手間で突き止める」「検査の待ち時間を減らす」という運用の問題を、確率と算法の言葉で定式化します。

継続的インテグレーションという言葉は、1990 年代のエクストリーム・プログラミングで「各自の変更を少なくとも 1 日に 1 回、共有の主線に統合し、そのたびに自動でビルドとテストを走らせる」という実践として広まりました。統合を先送りにするほど、併合のたびに問題がまとまって現れ、どの変更が原因かが分からなくなるからです。現在の CI は、その自動化された検査の仕組み全体を指します。

2. 準備：版・検査・不変条件

リポジトリのある時点の内容全体を版と呼びます。Git の言葉では、コミットが指すファイル木です（定義 4.1［バージョン管理システム Git］）。

定義 2.1（検査・パイプライン・CI と CD）↗

版の集合を $\mathcal{C}$ とする。検査とは、版に対して合格か不合格かを返す手続きである。同じ版に対していつ実行しても同じ結果を返すとき、検査は決定的であるといい、写像 $\chi : \mathcal{C} \to \{\text{合格}, \text{不合格}\}$ と同一視する。

パイプラインとは、検査や生成の段階を頂点とし、「この段階はあの段階の出力を使う」を辺とする有向非巡回グラフである。すべての段階が合格したとき、パイプラインは合格したという。

変更が共有のリポジトリに届くたびにパイプラインを自動で実行する運用を継続的インテグレーション（CI）、合格した版をいつでも公開できる成果物として自動で用意する（あるいは自動で公開する）運用を継続的デリバリー（CD）という。

パイプラインは前章の依存グラフそのものです。実行の順序はトポロジカル順で（定理 3.2［ビルドと依存関係］）、検査が密閉的なら結果は順序によりません。

定義 2.2（主ブランチの不変条件）↗

主ブランチの先頭が指す版の時間的な列を $h_0, h_1, h_2, \ldots$ とする。決定的な検査 $\chi$ について、

\chi(h_k) = \text{合格} \qquad (k = 0, 1, 2, \ldots)

が成り立つことを主ブランチの不変条件という。

この不変条件が保たれていれば、どの開発者も「いま主ブランチから分岐すれば、検査に合格する版から始められる」ことを当てにできます。自分の変更のあとで検査が落ちたら、原因は自分の変更にあります。不変条件が破れていると、この推論ができなくなり、落ちた検査を誰も自分の責任だと思わなくなります。

定義 2.3（不安定なテスト）↗

テスト $\tau$ と版 $c$ について、 $\tau$ を $c$ の上で 1 回実行したときに不合格になる確率を $q_\tau(c) \in [0, 1]$ とする。 $q_\tau(c) \in \{0, 1\}$ のとき $\tau$ は $c$ の上で決定的、 $0 < q_\tau(c) < 1$ のとき不安定（flaky）であるという。

不安定さの源は、テストが宣言していない入力に依存していることです。現在時刻、乱数の種、スレッドやプロセスの実行順、辞書や集合の走査順、ほかのテストが残した状態、ネットワークの先のサービスが典型です。入力の生成が種で決まり、テスト対象が決定的なら、失敗は種から再現できます（性質ベーステストの章を参照してください）。

3. 意味的な衝突とマージキュー

3.1. 変更ごとの検査では足りない

Git の 3-way マージは、ベース $b$ と 2 つの版 $x, y$ について、同じ位置を両方が違う値に変えたときだけ衝突を報告します（定義 5.1［バージョン管理システム Git］、命題 5.2［バージョン管理システム Git］）。衝突がなければ併合の結果 $m_b(x, y)$ が決まりますが、それが検査に合格するとは限りません。

定理 3.1（テキスト上の衝突がなくても併合の結果は検査に落ちうる）✓

位置の集合 $I$ 、値の集合 $V$ 、決定的な検査 $\chi$ 、版 $b, x, y : I \to V$ であって、次の 3 つを同時に満たすものが存在する。

$\chi(b) = \chi(x) = \chi(y) = \text{合格}$ 。
$x$ と $y$ は $b$ を基準として衝突しない。
$\chi(m_b(x, y)) = \text{不合格}$ 。

証明（定理 3.1）

具体例を構成します。位置は 3 つのファイル $I = \{\texttt{lib}, \texttt{app}, \texttt{report}\}$ とし、値は「関数 $g$ を定義する」という文 $\mathrm{def}(g)$ と「関数 $g$ を呼ぶ」という文 $\mathrm{call}(g)$ の有限集合とします。検査 $\chi$ は「どこかのファイルで呼ばれている関数名は、すべてどこかのファイルで定義されている」とき合格、そうでないとき不合格と定めます（リンクが通るかどうかの検査です）。

\begin{array}{c|ccc} & \texttt{lib} & \texttt{app} & \texttt{report} \\ \hline b & \{\mathrm{def}(f)\} & \{\mathrm{call}(f)\} & \emptyset \\ x & \{\mathrm{def}(g)\} & \{\mathrm{call}(g)\} & \emptyset \\ y & \{\mathrm{def}(f)\} & \{\mathrm{call}(f)\} & \{\mathrm{call}(f)\} \end{array}

$x$ は関数の名前を $f$ から $g$ に変え、呼び出しも直した版、 $y$ は新しいファイルで $f$ の呼び出しを足した版です。

1。 $b$ では呼ばれている名前の集合 $\{f\}$ が定義されている名前の集合 $\{f\}$ に含まれます。 $x$ では $\{g\} \subseteq \{g\}$ 、 $y$ では $\{f\} \subseteq \{f\}$ です。3 つとも合格です。

2。定義 5.1［バージョン管理システム Git］の $D_i = \{x(i), y(i)\} \setminus \{b(i)\}$ を計算します。 $D_{\texttt{lib}} = \{\{\mathrm{def}(g)\}\}$ 、 $D_{\texttt{app}} = \{\{\mathrm{call}(g)\}\}$ 、 $D_{\texttt{report}} = \{\{\mathrm{call}(f)\}\}$ で、どれも元の個数は $1$ です。よって衝突しません。

3。併合の結果は、各位置で $D_i$ のただ 1 つの元を取ったもので、

m_b(x, y) = \bigl(\texttt{lib} \mapsto \{\mathrm{def}(g)\},\ \ \texttt{app} \mapsto \{\mathrm{call}(g)\},\ \ \texttt{report} \mapsto \{\mathrm{call}(f)\}\bigr)

です。呼ばれている名前は $\{g, f\}$ 、定義されている名前は $\{g\}$ で、 $f$ が定義されていません。よって不合格です。

この定理から、「各変更を、分岐した時点の主ブランチに対して検査し、合格したらテキスト上の併合だけで取り込む」という運用では、主ブランチの不変条件（定義 2.2）が保てないことが分かります。 $b$ が先頭のときに $x$ と $y$ がそれぞれ検査に合格し、 $x$ 、 $y$ の順に取り込むと、先頭は $m_b(x, y)$ になり、検査に落ちます。3-way マージが見ているのは位置ごとの値だけで、位置をまたぐ関係（名前の定義と使用、関数の引数の個数、設定の鍵とそれを読むコード）は見ていないからです。

3.2. マージキュー

定義 3.2（変更とマージキュー）↗

変更とは、版に適用すると新しい版か「衝突」を返す操作 $\delta$ である。版 $h$ への適用の結果を $\delta(h) \in \mathcal{C} \cup \{\text{衝突}\}$ と書く（プルリクエストを $h$ に併合した結果である）。

マージキューとは、変更の列 $\delta_1, \delta_2, \ldots$ を順に処理し、先頭 $h$ を次の規則だけで更新する仕組みである。

変更 $\delta$ について $m = \delta(h)$ を計算する。 $m$ が衝突であるか $\chi(m) = \text{不合格}$ ならば、 $\delta$ を却下して $h$ を変えない。そうでなければ $h$ を $m$ に進める。

次の定理は、この規則だけで不変条件が保てることを帰納法で示し、(b) では複数の変更の検査を同時に走らせても結果が変わらないことを示します。(b) の $s_j$ は、待っている変更を順に重ねたときの $j$ 番目の版です。「 $s_1$ が不合格なら、それを含む $s_2, s_3, \ldots$ の検査結果は使えず捨てる」という流れを、記号で書いたものと読んでください。

定理 3.3（マージキューは主ブランチの不変条件を保つ）✓

検査 $\chi$ は決定的で、最初の先頭 $h_0$ は $\chi(h_0) = \text{合格}$ を満たし、先頭はマージキューの規則（定義 3.2）によってのみ更新されるとする。

(a) 先頭の列 $h_0, h_1, h_2, \ldots$ のすべてについて $\chi(h_k) = \text{合格}$ である。

(b) （楽観的な並列化）先頭が $h$ のとき、待っている変更 $\delta_1, \ldots, \delta_k$ に対して $s_0 = h$ 、 $s_j = \delta_j(s_{j-1})$ と順に定め（衝突が出たらそこで止める）、定まった $s_1, s_2, \ldots$ の検査を同時に実行する。 $s_j$ が衝突であるか不合格である最小の $j$ を $j^{*}$ とし（なければ $j^{*} = k + 1$ ）、先頭を $s_{j^{*}-1}$ に進め、 $\delta_{j^{*}}$ を却下し、 $\delta_{j^{*}+1}, \ldots, \delta_k$ を待ち行列に戻して同じことを繰り返す。この方式の先頭の列と却下される変更の集合は、変更を 1 つずつ処理した場合と同じである。特に不変条件は保たれる。

(c) (b) の方式で $k$ 個の変更を処理し終えるまでに実行する検査の回数は、却下が $r$ 個のとき $(r + 1)k$ 以下である。却下が 1 つ出るたびに捨てられる検査の結果は、その変更より後ろに並んでいた変更の個数以下である。

証明（定理 3.3）

(a)。 先頭が進んだ回数 $k$ についての帰納法（定理 3.2［証明の技術］）です。 $k = 0$ は仮定です。 $\chi(h_k) = \text{合格}$ とします。先頭が $h_{k+1}$ に進むのは、規則より、ある変更 $\delta$ について $h_{k+1} = \delta(h_k)$ が衝突でなく、検査を実行した結果が合格だったときに限ります。 $\chi$ は決定的なので、検査を実行した結果は $\chi(h_{k+1})$ そのもので、 $\chi(h_{k+1}) = \text{合格}$ です。

(b)。 待っている変更の個数 $k$ についての完全帰納法（定理 4.3［証明の技術］）で示します。変更を 1 つずつ処理する場合を考えます。先頭 $s_0 = h$ に $\delta_1$ を適用した結果は $s_1$ です。 $j^{*} > 1$ なら $s_1$ は衝突でも不合格でもないので、先頭は $s_1$ に進みます。同様に、 $j < j^{*}$ である間、先頭が $s_{j-1}$ のときに $\delta_j$ を適用した結果は $s_j$ で、先頭は $s_j$ に進みます。 $j^{*} \le k$ なら、先頭が $s_{j^{*}-1}$ のときに $\delta_{j^{*}}$ を適用した結果 $s_{j^{*}}$ は衝突か不合格なので、 $\delta_{j^{*}}$ は却下され、先頭は $s_{j^{*}-1}$ のままです。ここまでの先頭の動きと却下は、楽観的な方式の 1 巡と一致します（楽観的な方式は $h$ から $s_{j^{*}-1}$ まで一度に進めますが、途中の $s_1, \ldots, s_{j^{*}-1}$ はすべて合格しています）。残りの $\delta_{j^{*}+1}, \ldots, \delta_k$ は $k$ 個より少なく、どちらの方式でも先頭 $s_{j^{*}-1}$ から処理を続けるので、帰納法の仮定より以後も一致します。 $j^{*} = k + 1$ のときは残りがなく、そこで終わります。不変条件は (a) から従います。

(c)。 楽観的な方式の 1 巡では、待っている変更の個数（ $k$ 以下）だけ検査を実行します。1 巡は、却下をちょうど 1 つ出して次の巡に進むか、却下を出さずに全体を終えるかのどちらかです。却下が $r$ 個なら巡は高々 $r + 1$ 回なので、検査は $(r + 1)k$ 回以下です。却下 $\delta_{j^{*}}$ が出た巡で、 $s_{j^{*}+1}, \ldots$ の検査の結果は $\delta_{j^{*}}$ を含む版についてのものなので使えず、その個数は高々 $k - j^{*}$ 、すなわち後ろに並んでいた変更の個数です。

(a) の証明は 3 行ですが、仮定が 3 つとも効いています。検査が決定的でなければ、検査を通った版が次に実行すると落ちることがあります（§4）。先頭がマージキュー以外の経路（直接の push、管理者による強制的な併合）で動けば、帰納法の段が成り立ちません。そして検査するのは $\delta(h)$ 、すなわち併合した結果でなければなりません。プルリクエストの枝の先頭を検査するだけでは、定理 3.1 の例が通り抜けます。

(c) は、楽観的な並列化の損得を表しています。却下がなければ、 $k$ 個の検査を同時に実行するので、待ち時間は検査 1 回分です。却下が多いと、検査の回数は最悪で $k$ 倍近くになります。変更の不良率が高いチームでは楽観的な並列化の利得が小さく、§6 のまとめ検査と同じ「不良率 $p$ に応じて方式を選ぶ」問題になります。

4. 不安定なテストと再実行

4.1. 落ちる確率は足し算で効く

定理 4.1（不安定なテストを含む検査が落ちる確率）✓

$n$ 個のテストからなる検査を考え、テストの各回の実行の結果は互いに独立とする（定義 2.3［確率変数と期待値］）。

(a) 正しいコードの上で、各テストが 1 回の実行で確率 $q \in [0, 1]$ で不合格になるとき、検査全体（1 つでも不合格なら不合格）が不合格になる確率は

1 - (1 - q)^n, \qquad 1 - e^{-qn} \ \le\ 1 - (1-q)^n \ \le\ nq

である。

(b) 「各テストを最大 $k$ 回まで実行し、1 回でも合格すればそのテストは合格」とする再実行のもとでは、(a) の確率は

1 - (1 - q^k)^n \ \le\ n q^k

になる。

(c) 本物の不具合があり、それを検出するテストが 1 回の実行で確率 $r \in (0, 1]$ で不合格になるとする（競合状態のように、不具合が毎回は現れない場合を含む）。この不具合を見逃す確率は、再実行なしで $1 - r$ 、(b) の再実行のもとで $1 - r^k$ であり、 $1 - r \le 1 - r^k \le k(1 - r)$ が成り立つ。 $r < 1$ かつ $k \ge 2$ なら左の不等号は真の不等号である。

証明（定理 4.1）

(a)。 検査全体が合格するのは $n$ 個のテストがすべて合格するときで、独立性よりその確率は $(1 - q)^n$ です。よって不合格の確率は $1 - (1-q)^n$ です（余事象の確率、定理 4.2［確率空間とコルモゴロフの公理］の 3）。

右の不等式は、ベルヌーイの不等式 $(1 + h)^n \ge 1 + nh$ （ $h > -1$ 、補題 3.1［指数関数と対数関数］）で $h = -q$ とした $(1 - q)^n \ge 1 - nq$ から従います（ $q = 1$ のときは $1 \le n$ で成り立ちます）。

左の不等式のために、まず $1 - q \le e^{-q}$ を示します。 $q < 1$ とし、整数 $m \ge 1$ を取ると $-q/m > -1$ なので、ベルヌーイの不等式より $(1 - q/m)^m \ge 1 - q$ です。 $m \to \infty$ とすると左辺は $e^{-q}$ に収束するので（定理 5.2［指数・対数・三角関数をきちんと定義する］）、 $e^{-q} \ge 1 - q$ です。 $q = 1$ のときは $e^{-1} > 0$ で成り立ちます。両辺は $0$ 以上なので $n$ 乗しても向きは変わらず、指数関数の加法性（定理 3.3［指数・対数・三角関数をきちんと定義する］の 2）より $(1 - q)^n \le (e^{-q})^n = e^{-qn}$ です。

(b)。 1 つのテストが再実行のもとで不合格になるのは、 $k$ 回の実行がすべて不合格のときで、独立性よりその確率は $q^k$ です。(a) の $q$ を $q^k$ に置き換えれば主張が得られます。

(c)。 再実行なしでは、検出するテストが合格してしまう確率は $1 - r$ です。再実行のもとでは、そのテストが不合格と判定されるのは $k$ 回すべて不合格のときで、確率は $r^k$ です。よって見逃す確率は $1 - r^k$ です。 $0 < r \le 1$ より $r^k \le r$ なので $1 - r \le 1 - r^k$ で、 $r < 1$ 、 $k \ge 2$ なら $r^k < r$ です。右の不等式は、ベルヌーイの不等式で $h = -(1 - r) > -1$ とした $r^k = (1 - (1 - r))^k \ge 1 - k(1 - r)$ から従います。

数値を入れます。 $n = 1000$ 、 $q = 10^{-3}$ のとき $1 - 0.999^{1000} = 0.632$ です。個々のテストは 1000 回に 1 回しか誤らないのに、検査全体は 3 回に 2 回近く誤って落ちます。 $k = 2$ の再実行で $1 - (1 - 10^{-6})^{1000} = 0.0010$ に下がります。

(b) と (c) は同じ式の表と裏です。再実行は「不合格を $k$ 回続けて見たときだけ信じる」という判定なので、誤って落ちる確率を $q$ から $q^k$ に下げると同時に、本物の不具合の検出率も $r$ から $r^k$ に下げます。 $r = 1$ の決定的な不具合は見逃しませんが、5 回に 1 回しか現れない競合状態（複数の処理の実行順しだいで、起きたり起きなかったりする不具合。 $r = 0.2$ ）は、 $k = 3$ の再実行のもとで $1 - 0.2^3 = 99.2\%$ の確率で通り抜けます。再実行で消える失敗は、「テストが不安定」なのか「製品が不安定」なのかを区別していません。

種を固定したシミュレーションで式を確かめます。

# Python 3.9.6 / NumPy 2.0.2／乱数種 20261008
import numpy as np

rng = np.random.default_rng(20261008)
TRIALS, CHUNK = 100_000, 2_000

def false_failure(n, q, k):
    """正しいコードで、n 個のテストのどれかが k 回続けて落ちる頻度"""
    bad = 0
    for _ in range(TRIALS // CHUNK):
        fails = np.ones((CHUNK, n), dtype=bool)
        for _ in range(k):
            fails &= rng.random((CHUNK, n)) < q
        bad += int(fails.any(axis=1).sum())
    return bad / TRIALS

def miss(r, k):
    """1 回の実行で確率 r で落ちる本物の不具合が、k 回のうち 1 回でも通って見逃される頻度"""
    return float((rng.random((TRIALS, k)) >= r).any(axis=1).mean())

print("誤って落ちる確率  n = 1000")
print("     q  k   1-(1-q^k)^n   実験      標準誤差")
for q in (1e-3, 1e-2):
    for k in (1, 2, 3):
        exact = 1 - (1 - q**k) ** 1000
        est = false_failure(1000, q, k)
        se = (exact * (1 - exact) / TRIALS) ** 0.5
        print(f"{q:6.0e} {k:2d} {exact:13.6f} {est:9.5f} {se:11.5f}")
print("見逃す確率")
print("    r  k   1-r^k     実験")
for r in (0.9, 0.5, 0.1):
    for k in (1, 2, 3):
        print(f"{r:5.1f} {k:2d} {1 - r**k:8.4f} {miss(r, k):8.4f}")

誤って落ちる確率  n = 1000
     q  k   1-(1-q^k)^n   実験      標準誤差
 1e-03  1      0.632305   0.63321     0.00152
 1e-03  2      0.001000   0.00089     0.00010
 1e-03  3      0.000001   0.00000     0.00000
 1e-02  1      0.999957   0.99998     0.00002
 1e-02  2      0.095167   0.09664     0.00093
 1e-02  3      0.001000   0.00098     0.00010
見逃す確率
    r  k   1-r^k     実験
  0.9  1   0.1000   0.0995
  0.9  2   0.1900   0.1911
  0.9  3   0.2710   0.2720
  0.5  1   0.5000   0.5029
  0.5  2   0.7500   0.7507
  0.5  3   0.8750   0.8762
  0.1  1   0.9000   0.8995
  0.1  2   0.9900   0.9904
  0.1  3   0.9990   0.9988

上の表の 6 行では、実験の頻度（ $10^5$ 回）が式の値から標準誤差の 2 倍以内にあります。下の表でも、式との差はどの行でも $0.003$ 以下です。

4.2. 不安定か、決定的か

落ちたテストを見て、それが不安定なのか本物の不具合なのかを分類する規則を考えます。

命題 4.2（再実行による分類の誤りと、不安定さの率の推定）✓

不合格になったテストを同じ版の上でさらに $m$ 回実行し、1 回でも合格すれば「不安定」、すべて不合格なら「決定的に不合格」と分類する。実行の結果は互いに独立とする。

(a) 決定的に不合格になるテスト（1 回の実行で不合格になる確率が $1$ ）を「不安定」と誤って分類する確率は $0$ である。

(b) 1 回の実行で不合格になる確率が $q \in (0, 1)$ の不安定なテストを「決定的に不合格」と誤って分類する確率は $q^m$ である。

N \ \ge\ \frac{q(1-q)}{\varepsilon^2 \delta}

ならば $P(|\hat{q} - q| < \varepsilon) \ge 1 - \delta$ である。 $q(1 - q) \le 1/4$ なので、 $q$ を知らなくても $N \ge 1/(4\varepsilon^2\delta)$ で足り、このとき区間 $(\hat{q} - \varepsilon,\ \hat{q} + \varepsilon)$ は信頼係数 $1 - \delta$ の信頼区間（定義 6.1［検定と区間推定］）である。

証明（命題 4.2）

(a)。 確率 $1$ で不合格になるテストが $m$ 回のうち 1 回でも合格する確率は $0$ です。

(b)。 「決定的に不合格」と分類されるのは $m$ 回すべて不合格のときで、独立性よりその確率は $q^m$ です。

(c)。 $X$ は二項分布 $B(N, q)$ に従い、 $E[X] = Nq$ 、 $\mathrm{Var}(X) = Nq(1-q)$ です（定理 3.2［確率分布と統計的な推測］）。 $\hat{q} = X/N$ なので $E[\hat{q}] = q$ 、 $\mathrm{Var}(\hat{q}) = q(1-q)/N$ です（命題 5.3［確率変数と期待値］の 2）。チェビシェフの不等式（系 6.2［確率変数と期待値］）より

P\bigl(|\hat{q} - q| \ge \varepsilon\bigr) \ \le\ \frac{q(1-q)}{N\varepsilon^2} \ \le\ \delta .

最後の不等号は $N$ についての仮定です。 $q(1 - q) = 1/4 - (q - 1/2)^2 \le 1/4$ なので、 $N \ge 1/(4\varepsilon^2\delta)$ ならばどの $q$ についても仮定が満たされます。 $|\hat{q} - q| < \varepsilon$ は $q \in (\hat{q} - \varepsilon, \hat{q} + \varepsilon)$ と同値なので、この区間が $q$ を含む確率はすべての $q$ で $1 - \delta$ 以上です。

(b) より、 $q = 0.5$ の不安定なテストを $m = 5$ 回の再実行で分類すると、 $0.5^5 = 3\%$ の確率で「決定的」と誤ります。 $q$ が $1$ に近い（ほとんど毎回落ちる）不安定なテストほど、決定的な不具合と見分けにくくなります。

注意 4.3

(c) の $N$ はチェビシェフの不等式による保証で、標本が小さくても成り立つ代わりに大きめです。 $\varepsilon = 0.01$ 、 $\delta = 0.05$ なら $N \ge 1/(4 \cdot 10^{-4} \cdot 0.05) = 50000$ 回です。 $N$ が大きいときの漸近的な区間（Wald 区間。定理 6.3［検定と区間推定］）を使うと、必要な回数は $z_{\delta/2}^2\, q(1-q)/\varepsilon^2$ の程度で、同じ条件で $q = 0.02$ なら約 $750$ 回になります。どちらにせよ、 $q = 10^{-3}$ のような小さな失敗率を相対的に良い精度で測るには、 $1/q$ の数倍から数十倍の実行が要ります。CI が毎回の実行結果を蓄積し、テストごとの失敗率を記録しておくことの価値はここにあります。1 回の変更の中で測るには足りない回数が、日々の実行の合計としては自然に集まるからです。

例 4.4（不安定なテストの典型と直し方）

不安定さは、テストが読んでいる「宣言されていない入力」を特定し、それを固定するか、依存をなくすことで直します。

源	典型的な症状	直し方
現在時刻	月末・うるう日・日付の変わり目・夏時間の切り替えの前後でだけ落ちる	時計を引数として渡し、テストでは固定した時刻を返す時計に差し替える
実行順・共有状態	単独では通るが、まとめて実行すると落ちる。順序を変えると落ちるテストが変わる	テストごとに状態を作り直す。順序を無作為に入れ替えて実行し、依存を見つける
走査順	辞書・集合・ディレクトリの列挙の順に出力が依存する	比べる前に整列する。順序に意味があるなら、順序を決める鍵を明示する
並行性	待ち時間（`sleep`）で同期している。負荷の高い実行機でだけ落ちる	時間ではなく条件の成立を待つ。競合が本物なら製品の側を直す
外部のサービス	ネットワークの遅延や相手の障害で落ちる	単体テストではテストダブルに差し替え、実物との結合は別の段階で検査する
乱数	まれな入力でだけ落ちる	種を記録して再現する。落ちたのが性質の反例なら、それは不安定さではなく発見である

最後の 2 行は判断が要ります。乱数の入力で落ちたテストを「不安定」として再実行で流すと、定理 4.1 (c) のとおり本物の不具合を捨てることになります。

5. 回帰を探す：二分探索

以前は通っていた検査が、いまは落ちる。このような劣化を回帰（regression）と呼びます。履歴のどのコミットで壊れたかが分かれば、原因はそのコミットの差分の中にあります。

5.1. 単調性のもとでの最適性

ここで示すのは、履歴を半分ずつに絞れば最初の不良コミットに少ない検査の回数でたどり着けること(a)と、どんな手順もこれより少なくはできないこと(b)です。(b) は、検査結果の良・不良の並びが答えの候補の個数ぶん区別できなければならない、という数え上げで示します。

定理 5.1（最初の不良コミットの二分探索）✓

$n \ge 1$ とし、一直線の履歴 $c_0, c_1, \ldots, c_n$ と決定的な検査を考える。検査に不合格のコミットを不良、合格のコミットを良と呼ぶ。 $c_0$ は良、 $c_n$ は不良と分かっていて、次の単調性が成り立つとする。

ある $f \in \{1, \ldots, n\}$ があって、 $c_i$ が不良であることと $i \ge f$ であることが同値である。

この $c_f$ を最初の不良コミットという。

(a) $c_1, \ldots, c_{n-1}$ のうち高々 $\lceil \log_2 n \rceil$ 個を検査すれば、 $f$ を特定できる。

(b) 次に検査するコミットをそれまでの検査結果だけから決めるどんな決定的な手順も、ある $f$ に対しては少なくとも $\lceil \log_2 n \rceil$ 回の検査を行う。

証明（定理 5.1）

(a)。 $n = 1$ のときは $f = 1$ と決まり、検査は $0 = \lceil \log_2 1 \rceil$ 回です。 $n \ge 2$ とします。長さ $n - 1$ の配列 $A[0..n-2]$ を、 $c_{i+1}$ が良なら $A[i] = 0$ 、不良なら $A[i] = 1$ と定めます。単調性より $A$ は $0$ が $f - 1$ 個並んだあとに $1$ が並ぶ昇順の配列です。 $A[i] < 1$ を満たす添字の個数は $f - 1$ なので、ソート済み配列の下界の位置 $\mathrm{lb}_A(1)$ は $f - 1$ です。

二分探索 lower_bound(A, 1) は $\mathrm{lb}_A(1)$ を返し（定理 3.2［探索アルゴリズム］）、その比較回数は高々 $\lceil \log_2((n-1)+1) \rceil = \lceil \log_2 n \rceil$ 回です（定理 3.3［探索アルゴリズム］）。二分探索が行う比較は「 $A[\mathit{mid}] < 1$ か」だけで、これは「 $c_{\mathit{mid}+1}$ は良か」という検査 1 回に当たります。配列を前もって作る必要はなく、比較のたびに 1 つのコミットを検査すればよいので、検査の回数は比較の回数に等しく、返り値に $1$ を足せば $f$ が得られます。

(b)。 手順が、どの $f$ に対しても高々 $k$ 回の検査で止まるとします。手順は決定的なので、検査結果の列（良・不良の列）が同じなら、検査したコミットの列も、出力する答えも同じです。 $f$ の値が違えば正しい答えが違うので、 $f \mapsto$ （検査結果の列）は単射でなければなりません。

現れうる検査結果の列は、長さ $k$ 以下の 2 値の列で、どの列もほかの列の真の接頭辞ではありません（ある列で手順が止まったなら、その先に続く列は現れないからです）。各列の末尾を任意に埋めて長さ $k$ に延ばした列の集合を考えると、異なる列から作った集合は互いに交わりません。長さ $k$ の 2 値の列は $2^k$ 個なので、現れうる列は $2^k$ 個以下です。単射性より $n \le 2^k$ 、すなわち $k \ge \log_2 n$ で、 $k$ は整数なので $k \ge \lceil \log_2 n \rceil$ です。

(b) の数え上げは、比較による探索の下界（定理 4.1［探索アルゴリズム］、系 4.2［探索アルゴリズム］）と同じ議論です。 $n = 1000$ コミットなら 10 回、 $n = 10^6$ でも 20 回の検査で済みます。前から順に調べれば最悪 $n - 1$ 回です。

例 5.2（git bisect run）

Git にはこの探索が組み込まれています。良と分かっている版（ここではタグ v1.4.0）と不良と分かっている版を与え、検査のスクリプトを渡します。

git bisect start
git bisect bad HEAD
git bisect good v1.4.0
git bisect run ./check.sh
git bisect reset

git bisect run は、スクリプトの終了コードが $0$ なら良、 $1$ から $127$ （ $125$ を除く）なら不良と解釈して探索を進め、最初の不良コミットを報告します。 $125$ は「このコミットは判定できない（ビルドできないなど）」を表し、そのコミットを飛ばします。スクリプトは、探している回帰だけを判定するように書きます。無関係な理由で落ちるコミットを不良に数えると、単調性の仮定が崩れます。履歴が一直線でない場合も、Git は祖先関係（半順序。補題 4.2［バージョン管理システム Git］）の上で、候補をなるべく半分に分けるコミットを選んで同じことをします。

例 5.3（単調性が破れると誤ったコミットを返す）

$c_1, \ldots, c_7$ の良・不良が

\text{良},\ \text{不良},\ \text{良},\ \text{良},\ \text{不良},\ \text{不良},\ \text{不良}

だったとします。 $c_2$ で入った不具合が $c_3$ でいったん直り、 $c_5$ で再び壊れた履歴です。最初の不良コミットは $c_2$ ですが、単調性は成り立ちません。

$c_1, \ldots, c_6$ に対する配列は $A = [0, 1, 0, 0, 1, 1]$ です。lower_bound(A, 1) は、 $\mathit{lo} = 0$ 、 $\mathit{hi} = 6$ から始めて、 $\mathit{mid} = 3$ で $A[3] = 0$ なので $\mathit{lo} = 4$ 、 $\mathit{mid} = 5$ で $A[5] = 1$ なので $\mathit{hi} = 5$ 、 $\mathit{mid} = 4$ で $A[4] = 1$ なので $\mathit{hi} = 4$ とし、 $4$ を返します。報告されるのは $c_5$ です。

$c_5$ は「直前が良で自分が不良」という境界の 1 つではありますが、最初の境界ではありません。二分探索が保証するのは、単調性のもとでの正しさだけです。 $c_5$ の差分に原因が見当たらないときは、単調性を疑い、 $c_5$ より前の区間をもう一度探索します。

5.2. 検査が誤る場合

不安定なテストで二分探索をすると、1 回の誤判定で探索が誤った半分に進み、そのまま戻りません。各点で検査を繰り返して多数決をとります。次の命題は、1 回の誤りやすさ $q$ が $1/2$ より小さければ、繰り返す回数を増やすほど誤りが急に減ることを示します。証明では、まず1つのコミットの多数決が誤る確率を二項分布で見積もり、次に探索の段ごとの誤りを足し合わせます。

命題 5.4（多数決つきの二分探索）✓

定理 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))$ である。

証明（命題 5.4）

(a)。 $2j + 1$ 回のうち誤った結果を返した回数 $X$ は二項分布 $B(2j+1, q)$ に従います。判定が誤るのは $X \ge j + 1$ のときなので、

e_j = \sum_{i=j+1}^{2j+1} \binom{2j+1}{i} q^{i} (1-q)^{2j+1-i} .

$i \ge j + 1$ のとき、 $q < 1/2$ より $q/(1-q) < 1$ なので

q^{i}(1-q)^{2j+1-i} = q^{j+1}(1-q)^{j} \Bigl(\frac{q}{1-q}\Bigr)^{i-j-1} \le q^{j+1}(1-q)^{j} .

二項係数の和については、二項定理（定理 7.3［数え上げと母関数］）で $x = y = 1$ とすると $\sum_{i=0}^{2j+1} \binom{2j+1}{i} = 2^{2j+1}$ です。対称性 $\binom{2j+1}{i} = \binom{2j+1}{2j+1-i}$ により、 $i \ge j + 1$ の項の和と $i \le j$ の項の和は等しいので、 $\sum_{i=j+1}^{2j+1} \binom{2j+1}{i} = 2^{2j}$ です。合わせて

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

2 つ目の不等式は $q \le (4q(1-q))^{1/2}$ と同値で、両辺を 2 乗すると $q^2 \le 4q(1-q)$ 、すなわち $q \le 4/5$ となり、 $q < 1/2$ のもとで成り立ちます。 $4q(1-q) = 1 - (1 - 2q)^2 < 1$ です。

(b)。 探索の段を $1, 2, \ldots$ と数え、「 $i$ 段目が行われ、その多数決が誤る」という事象を $E_i$ とします。段は高々 $\lceil \log_2 n \rceil$ 回です（定理 5.1 (a)）。どの $E_i$ も起きなければ、探索は誤りのない検査と同じ道筋をたどるので、答えは $f$ です。よって誤った答えを返す事象は $\bigcup_i E_i$ に含まれます。

$i$ 段目でどのコミットを調べるかは、 $i - 1$ 段目までの結果で決まります。 $i$ 段目の $2j + 1$ 回の実行はそれまでの実行と独立なので、それまでの結果がどうであっても、 $i$ 段目の多数決が誤る条件つき確率は (a) の $e_j$ 以下です。それまでの結果について足し合わせて $P(E_i) \le e_j$ です。劣加法性（定理 4.2［確率空間とコルモゴロフの公理］の 7）より

P\Bigl(\bigcup_i E_i\Bigr) \le \sum_{i=1}^{\lceil \log_2 n \rceil} P(E_i) \le \lceil \log_2 n \rceil \cdot q\,\bigl(4q(1-q)\bigr)^{j} .

$\beta = 4q(1-q)$ とおくと、右辺が $\delta$ 以下であることは $\beta^{j} \le \delta / (q \lceil \log_2 n \rceil)$ 、すなわち $j \ln(1/\beta) \ge \ln(q \lceil \log_2 n \rceil / \delta)$ と同値です。 $\ln(1/\beta) > 0$ で割れば主張の式になります。 $q$ を固定すると $\ln(1/\beta)$ は定数で、分子は $\ln\lceil \log_2 n \rceil + \ln(1/\delta) + \ln q$ なので、 $j = O(\log(\log n/\delta))$ です。

誤りのない場合と、誤りのある検査に多数決を付けた場合を、シミュレーションで比べます。

# Python 3.9.6（標準ライブラリのみ）／乱数種 20261008
import math, random

rng = random.Random(20261008)

def bisect(n, first_bad, q, j):
    """c_1..c_n のうち最初の不良を探す。c_n は不良と分かっている。各点を 2j+1 回調べて多数決"""
    lo, hi, runs = 0, n - 1, 0                 # 答えは lo+1 .. hi+1 のどれか
    while lo < hi:
        mid = (lo + hi) // 2                   # コミット c_{mid+1} を調べる
        truth = (mid + 1) >= first_bad         # 本当に不良か
        votes = sum((truth != (rng.random() < q)) for _ in range(2 * j + 1))
        runs += 2 * j + 1
        if votes > j:                          # 多数決で「不良」
            hi = mid
        else:
            lo = mid + 1
    return lo + 1, runs

n, trials = 1024, 20_000
steps = math.ceil(math.log2(n))
print(f"n = {n}, 判定の回数 = {steps}")
print("    q  j  実行回数   誤り率   上界 steps*q*(4q(1-q))^j")
for q in (0.0, 0.1, 0.2):
    for j in (0, 1, 2, 4, 8):
        if q == 0.0 and j > 0:
            continue
        wrong = total = 0
        for _ in range(trials):
            f = rng.randint(1, n)
            ans, runs = bisect(n, f, q, j)
            wrong += ans != f
            total += runs
        bound = steps * q * (4 * q * (1 - q)) ** j
        print(f"{q:5.1f} {j:2d} {total / trials:8.1f} {wrong / trials:9.5f} {min(bound, 1):12.5f}")

n = 1024, 判定の回数 = 10
    q  j  実行回数   誤り率   上界 steps*q*(4q(1-q))^j
  0.0  0     10.0   0.00000      0.00000
  0.1  0     10.0   0.65655      1.00000
  0.1  1     30.0   0.24550      0.36000
  0.1  2     50.0   0.08600      0.12960
  0.1  4     90.0   0.00805      0.01680
  0.1  8    170.0   0.00025      0.00028
  0.2  0     10.0   0.89275      1.00000
  0.2  1     30.0   0.67125      1.00000
  0.2  2     50.0   0.44915      0.81920
  0.2  4     90.0   0.18120      0.33554
  0.2  8    170.0   0.02525      0.05629

誤りのない検査（ $q = 0$ ）では、 $n = 1024$ に対してちょうど 10 回で必ず正解します。 $q = 0.1$ の検査を多数決なし（ $j = 0$ ）で使うと、 $66\%$ の探索が誤った答えを返します。10 回の判定のどれか 1 つが誤れば全体が誤るからで、 $1 - 0.9^{10} = 0.651$ とほぼ一致します。多数決を付けると誤り率は指数的に下がり、どの行でも命題の上界の内側にあります。

6. まとめ検査：何個の変更を 1 回で調べるか

検査に 30 分かかり、1 日に 100 個の変更が届くとします。1 つずつ検査すると 50 時間分の検査が要ります。ほとんどの変更が良なら、いくつかをまとめて 1 回で検査し、落ちたときだけ犯人を探すほうが安く済みます。これは、1943 年に Dorfman が血液検査について考えた集団検査（group testing。多くの試料を混ぜて1回で調べ、陽性のときだけ個別に調べる方法）と同じ問題です。

補題 6.1

$0 \le p \le 1$ 、整数 $b \ge 0$ について

(1-p)^{b} \ \le\ 1 - bp + \frac{b(b-1)}{2}\,p^{2}

が成り立つ。

証明（補題 6.1）

$b$ についての帰納法です（定理 3.2［証明の技術］を $b + 1$ に適用します）。 $b = 0$ のとき両辺は $1$ です。 $b$ で成り立つとすると、 $1 - p \ge 0$ を掛けて

(1-p)^{b+1} \le (1-p)\Bigl(1 - bp + \frac{b(b-1)}{2}p^2\Bigr) = 1 - (b+1)p + \Bigl(b + \frac{b(b-1)}{2}\Bigr)p^2 - \frac{b(b-1)}{2}p^3 .

$b + b(b-1)/2 = (b+1)b/2$ で、最後の項は $0$ 以下なので、右辺は $1 - (b+1)p + \frac{(b+1)b}{2}p^2$ 以下です。

次の定理の (b) の下界は、まとめ方をどれだけ工夫しても、2 段階の方式では 1 変更あたりの検査回数が $\sqrt{p}$ の程度より下がらないことを言うためのものです。上界だけでは「もっとよい $b$ があるかもしれない」という疑いが残るので、場合分けをして下からも押さえます。

定理 6.2（まとめ検査の期待回数と最適な大きさ）✓

各変更が独立に確率 $p \in (0, 1)$ で不良であり、いくつかの変更をまとめた版の検査は「不良な変更を 1 つでも含めば不合格、含まなければ合格」を決定的に返すとする。

(a) （2 段階の方式） $b \ge 2$ 個をまとめて 1 回検査し、不合格なら $b$ 個を 1 つずつ検査する。このとき 1 変更あたりの期待検査回数は

E(b) = \frac{1}{b} + 1 - (1-p)^{b}

である。まとめない場合は $E(1) = 1$ とする。

(b) $b = \lceil 1/\sqrt{p} \rceil$ とすると $E(b) \le 2\sqrt{p} + p$ である。また、すべての $b \ge 2$ について $E(b) \ge \min\bigl(\sqrt{2p},\ (1-p)/2\bigr)$ である。特に $p \le 1/10$ ならば

\sqrt{2p} \ \le\ \min_{b \ge 1} E(b) \ \le\ 2\sqrt{p} + p .

(d) （二分する方式） $b = 2^{k}$ 個をまとめて検査し、不合格なら半分ずつに分けてそれぞれを同じ方式で検査する（1 個になったらそれ以上分けない）。この方式は不良な変更をすべて特定し、1 変更あたりの期待検査回数は $\dfrac{1}{b} + 2p \log_2 b$ 以下である。

証明（定理 6.2）

(a)。 1 つのまとまりに対する検査の回数は、まとめた検査が合格なら $1$ 、不合格なら $1 + b$ です。合格するのは $b$ 個がすべて良のときで、独立性よりその確率は $(1-p)^b$ です。期待値は $1 + b\,(1 - (1-p)^b)$ で、 $b$ で割ると主張の式になります。

(b) の上界。 $0 < p < 1$ より $1/\sqrt{p} > 1$ なので $b = \lceil 1/\sqrt{p} \rceil \ge 2$ です。 $b \ge 1/\sqrt{p}$ より $1/b \le \sqrt{p}$ です。ベルヌーイの不等式（補題 3.1［指数関数と対数関数］、 $h = -p$ ）より $(1-p)^b \ge 1 - bp$ なので、 $1 - (1-p)^b \le bp$ です。 $b \le 1/\sqrt{p} + 1$ より $bp \le \sqrt{p} + p$ です。合わせて $E(b) \le 2\sqrt{p} + p$ です。

(b) の下界。 $b \ge 2$ とします。

$bp \le 1$ の場合。補題 6.1 より

1 - (1-p)^b \ \ge\ bp - \frac{b(b-1)}{2}p^2 \ \ge\ bp - \frac{(bp)^2}{2} = bp\Bigl(1 - \frac{bp}{2}\Bigr) \ \ge\ \frac{bp}{2} .

よって $E(b) \ge 1/b + bp/2$ です。相加相乗平均の不等式（定理 3.2［式と証明］、 $n = 2$ ）より $1/b + bp/2 \ge 2\sqrt{(1/b)(bp/2)} = \sqrt{2p}$ です。

$bp > 1$ の場合。 $b_0 = \lfloor 1/p \rfloor$ とおくと、 $1 \le b_0 \le 1/p < b$ で、 $b_0 p \le 1$ かつ $b_0 > 1/p - 1$ 、すなわち $b_0 p > 1 - p$ です。 $0 < 1 - p < 1$ なので $(1-p)^b \le (1-p)^{b_0}$ で、上の計算を $b_0$ に使うと

1 - (1-p)^{b} \ \ge\ 1 - (1-p)^{b_0} \ \ge\ \frac{b_0 p}{2} \ >\ \frac{1-p}{2} .

よって $E(b) > (1-p)/2$ です。

2 つの場合を合わせて $E(b) \ge \min(\sqrt{2p}, (1-p)/2)$ です。 $p \le 1/10$ のとき、 $\sqrt{2p} \le \sqrt{0.2} < 0.448$ 、 $(1-p)/2 \ge 0.45$ なので最小値は $\sqrt{2p}$ で、 $E(1) = 1 \ge \sqrt{2p}$ と合わせて、すべての $b \ge 1$ で $E(b) \ge \sqrt{2p}$ です。

(c)。 $E(b) < 1$ は $1/b < (1-p)^b$ 、すなわち $1 - p > b^{-1/b}$ と同値です。まず、すべての整数 $b \ge 2$ について $b^3 \le 3^b$ を示します。 $b = 2$ では $8 \le 9$ 、 $b = 3$ では $27 \le 27$ です。 $b \ge 3$ で成り立つとすると、 $(b+1)^3 = b^3 (1 + 1/b)^3 \le b^3 (4/3)^3 = \frac{64}{27} b^3 < 3 b^3 \le 3^{b+1}$ です。帰納法により、すべての $b \ge 2$ で成り立ちます。 $b^3 \le 3^b$ の両辺を $1/(3b)$ 乗すると $b^{1/b} \le 3^{1/3}$ 、すなわち $b^{-1/b} \ge 3^{-1/3}$ で、等号は $b = 3$ で成り立ちます。よって $b^{-1/b}$ の $b \ge 2$ での最小値は $3^{-1/3}$ で、「ある $b \ge 2$ で $1 - p > b^{-1/b}$ 」は $1 - p > 3^{-1/3}$ と同値です。 $3^{-1/3} = 0.69336\ldots$ です。

(d)。 検査されるまとまりは、 $b = 2^k$ 個の変更を葉とする深さ $k$ の完全二分木の頂点に対応します。根は必ず検査されます。根でない頂点が検査されるのは、親の検査が不合格だったとき、すなわち親が不良な変更を含むときです。不良な変更は、それを含む頂点をたどって葉（1 個のまとまり）まで必ず検査が進むので、その葉の検査が不合格になることで特定されます。良の変更の葉は、検査されても合格するので、不良と誤られることはありません。

検査の回数は、 $1 +$ （不合格になった内部頂点の個数） $\times 2$ です。不合格になる内部頂点は不良な変更を含み、1 つの不良な変更を含む内部頂点は、その葉の祖先である深さ $0, 1, \ldots, k-1$ の $k$ 個です。まとまりの中の不良な変更の個数を $D$ とすると、不合格になる内部頂点は高々 $kD$ 個なので、検査の回数は $1 + 2kD$ 以下です。 $D$ は $b$ 個の指示関数の和で、期待値の線形性より $E[D] = bp$ です（定理 3.2［確率分布と統計的な推測］）。よって期待検査回数は $1 + 2kbp$ 以下で、 $b$ で割ると $1/b + 2pk$ 、 $k = \log_2 b$ です。

(b) の 2 つの評価から、2 段階の方式の最適な期待回数は、 $p$ が小さいとき $\sqrt{p}$ の定数倍（ $\sqrt{2} \approx 1.41$ 倍から $2$ 倍の間）です。不良率が $1\%$ なら検査は約 $5$ 分の $1$ に、 $0.1\%$ なら約 $16$ 分の $1$ になります。(d) の方式は、 $b$ を $1/p$ の程度に取ると $2p + 2p\log_2(1/p)$ の程度になり、 $p$ が小さいほど 2 段階の方式より大きく得をします。(c) は逆の端で、不良率が $31\%$ を超えるようなら、まとめずに 1 つずつ検査するのが最適です。

# Python 3.9.6（標準ライブラリのみ）／乱数種 20261008
import math, random

def dorfman(b, p):                 # 2 段階のまとめ検査の、1 変更あたりの期待検査回数
    return 1.0 if b == 1 else 1 / b + 1 - (1 - p) ** b

def halving(flags):                # まとめて検査し、落ちたら半分に分けて両方を再帰的に検査する
    if len(flags) == 1 or not any(flags):
        return 1
    half = len(flags) // 2
    return 1 + halving(flags[:half]) + halving(flags[half:])

rng = random.Random(20261008)
print("     p   最適 b   E(b)    下界 √(2p)   上界 2√p+p   b=⌈1/√p⌉ の E")
for p in (0.001, 0.01, 0.05, 0.1, 0.2, 0.3, 0.31):
    best = min(range(1, 400), key=lambda b: dorfman(b, p))
    b0 = math.ceil(1 / math.sqrt(p))
    print(f"{p:6.3f} {best:6d} {dorfman(best, p):8.4f} {math.sqrt(2 * p):10.4f} {2 * math.sqrt(p) + p:11.4f} {dorfman(b0, p):12.4f}")
print("二分する版（b は 2 のべき、20000 バッチの標本平均）")
print("     p     b   実験     上界 1/b + 2p log2 b")
for p in (0.001, 0.01, 0.05, 0.2):
    for b in (4, 16, 64, 256):
        tests = sum(halving([rng.random() < p for _ in range(b)]) for _ in range(20_000))
        print(f"{p:6.3f} {b:5d} {tests / (20_000 * b):8.4f} {1 / b + 2 * p * math.log2(b):10.4f}")

     p   最適 b   E(b)    下界 √(2p)   上界 2√p+p   b=⌈1/√p⌉ の E
 0.001     32   0.0628     0.0447      0.0642       0.0628
 0.010     11   0.1956     0.1414      0.2100       0.1956
 0.050      5   0.4262     0.3162      0.4972       0.4262
 0.100      4   0.5939     0.4472      0.7325       0.5939
 0.200      3   0.8213     0.6325      1.0944       0.8213
 0.300      3   0.9903     0.7746      1.3954       1.0100
 0.310      1   1.0000     0.7874      1.4236       1.0239
二分する版（b は 2 のべき、20000 バッチの標本平均）
     p     b   実験     上界 1/b + 2p log2 b
 0.001     4   0.2537     0.2540
 0.001    16   0.0705     0.0705
 0.001    64   0.0274     0.0276
 0.001   256   0.0192     0.0199
 0.010     4   0.2886     0.2900
 0.010    16   0.1420     0.1425
 0.010    64   0.1229     0.1356
 0.010   256   0.1321     0.1639
 0.050     4   0.4394     0.4500
 0.050    16   0.4081     0.4625
 0.050    64   0.4396     0.6156
 0.050   256   0.4517     0.8039
 0.200     4   0.8999     1.0500
 0.200    16   1.0430     1.6625
 0.200    64   1.0944     2.4156
 0.200   256   1.1062     3.2039

上の表では、最適な $b$ （ $p = 0.01$ で $11$ 、 $0.05$ で $5$ 、 $0.2$ で $3$ ）が $1/\sqrt{p}$ （それぞれ $10$ 、 $4.5$ 、 $2.2$ ）の近くにあり、 $E(b)$ が (b) の 2 つの評価の間にあります。 $p = 0.3$ では $b = 3$ でわずかに $1$ を下回り、 $p = 0.31$ ではまとめないのが最適で、(c) のしきい値 $0.3066$ と合っています。下の表では、二分する方式の標本平均がどの行でも (d) の上界以下で、 $p = 0.001$ のとき $b = 256$ で $0.019$ まで下がります（2 段階の方式の最適値は $0.063$ ）。

注意 6.3

この定理の仮定は 2 つとも現実には近似です。1 つ目は独立性で、同じ人の連続した変更や、同じ機能に触る変更は、良・不良が相関します。2 つ目は「まとめた版が不合格 ⇔ 不良な変更を含む」で、定理 3.1 のとおり、単独では良の変更どうしが合わさって不合格になることがあります。その場合、(d) の方式は「どの葉も合格なのに親が不合格」という結果で意味的な衝突を見つけることになり、それはそれで欲しい情報です。集団検査の理論（検査回数の情報理論的な下界や、適応的でない方式）については、Du と Hwang の本（参考文献）に体系的な解説があります。

7. 検査を速くする：テストの選択と段階の並べ方

7.1. 変更に影響されるテストだけを走らせる

命題 7.1（依存グラフによるテストの選択の安全性）✓

テストを前章のビルドの記述のタスクとして表し、テスト $\tau$ の出力（合格・不合格）を $v_x(\tau)$ と書く。記述は密閉的で（依存の宣言が完全で、テストの結果が宣言した依存だけで決まる）、前の版 $x$ ではすべてのテストが合格していたとする。版 $x'$ で変更されたファイルの集合を $C$ 、 $C$ から依存グラフで到達できるタスクの集合を $R$ とする。このとき

\text{$x'$ ですべてのテストが合格する} \iff \text{$x'$ で $R$ に属するテストがすべて合格する}

が成り立つ。

証明（命題 7.1）

定理 4.2［ビルドと依存関係］より、ストアが $v_x$ の状態から入力を $x'$ に書き換えて $R$ のタスクだけを再実行すると、最後のストアは $v_{x'}$ に一致します。 $R$ に属さないテスト $\tau$ は再実行されないので、そのストアでの値は $v_x(\tau)$ のままです。よって $v_{x'}(\tau) = v_x(\tau)$ で、仮定よりこれは合格です。したがって、 $x'$ で不合格になりうるテストは $R$ に属するものだけで、主張の同値が成り立ちます。

この命題は主ブランチの不変条件と組になっています。「前の版ではすべて合格していた」という仮定を与えるのが不変条件で、不変条件が破れていると、選ばれなかったテストがすでに落ちていることを見逃します。また、密閉性の仮定が崩れていれば（テストがデータベースの中身や、宣言していない設定ファイルを読んでいれば）、選択は不合格を見逃します。そのため実務では、マージ前は選択したテストだけを走らせ、主ブランチでは定期的に全テストを走らせる、という二重の構えを取ることが多くなります。

7.2. 待ち時間と段階の順序

次の命題の (a) は、検査の順番待ちの長さを見積もる式です。M/M/1 待ち行列とは、変更がばらばらの間隔で届き、窓口（実行機）が1つで、1件の処理時間もばらつくという、最も単純な待ち行列のモデルです。(b) は、落ちやすく速い段階を先に置くと、無駄な実行が減るという話です。

命題 7.2（待ち時間の増え方と、段階の最適な順序）✓

(a) 実行機が 1 台で、変更が強度 $\lambda$ のポアソン過程で届き、検査の所要時間が平均 $S$ の指数分布に独立に従い、先着順に処理するとする。利用率 $\rho = \lambda S$ が $1$ 未満ならば、変更が届いてから検査が終わるまでの平均時間 $W$ と、待っている変更と検査中の変更を合わせた平均個数 $L$ は

W = \frac{S}{1 - \lambda S}, \qquad L = \lambda W = \frac{\lambda S}{1 - \lambda S}

である。

(b) パイプラインが $k$ 個の段階からなり、段階 $i$ の所要時間を $t_i > 0$ 、不合格になる確率を $f_i \in (0, 1]$ とし、段階の合否は互いに独立とする。段階を順列 $\pi$ の順に 1 つずつ実行し、不合格が出たところで打ち切るとき、期待所要時間は

T(\pi) = \sum_{j=1}^{k} t_{\pi(j)} \prod_{l < j} \bigl(1 - f_{\pi(l)}\bigr)

である。 $T(\pi)$ は、段階を $t_i / f_i$ の小さい順に並べたとき最小になる。

証明（命題 7.2）

(a)。 サービス率を $\mu = 1/S$ とおくと、これは M/M/1 待ち行列で、 $\rho = \lambda/\mu = \lambda S < 1$ です。命題 5.2［クラウドコンピューティング］より $W = 1/(\mu - \lambda) = S/(1 - \lambda S)$ 、 $L = \rho/(1 - \rho)$ です。 $L = \lambda W$ はリトルの法則（定理 5.1［クラウドコンピューティング］）の形で、上の 2 式からも直接確かめられます。

(b)。 順列 $\pi$ の $j$ 番目の段階が実行されるのは、それより前の段階がすべて合格したときで、独立性よりその確率は $\prod_{l<j}(1 - f_{\pi(l)})$ です。所要時間は「 $j$ 番目の段階が実行されたら $t_{\pi(j)}$ 、されなければ $0$ 」という量の和なので、期待値の線形性（定理 6.3［確率］）より $T(\pi)$ の式になります。

隣り合う 2 つの段階を入れ替えたときの差を計算します。 $\pi$ の $j$ 番目が $a$ 、 $j + 1$ 番目が $b$ であるとし、この 2 つを入れ替えた順列を $\pi'$ とします。 $Q = \prod_{l<j}(1 - f_{\pi(l)}) \ge 0$ とおくと、 $j$ 番目より前の項は共通で、 $j + 2$ 番目以降の項も、掛かる積が $Q(1-f_a)(1-f_b)$ で共通です。違うのは 2 つの項だけで、

T(\pi) - T(\pi') = Q\bigl[t_a + (1 - f_a)t_b\bigr] - Q\bigl[t_b + (1 - f_b)t_a\bigr] = Q\,(f_b t_a - f_a t_b) .

$f_a, f_b > 0$ なので、 $f_b t_a - f_a t_b \le 0$ は $t_a/f_a \le t_b/f_b$ と同値です。よって、 $t_a / f_a > t_b / f_b$ である隣り合う組（逆転している組）を入れ替えると、 $T$ は増えません。

任意の順列 $\pi$ から始めて、逆転している隣り合う組がある限り入れ替えます。1 回の入れ替えで、「 $t/f$ の大小が位置の前後と逆になっている組」の総数はちょうど $1$ 減るので、有限回で止まり、止まったとき段階は $t_i/f_i$ の小さい順に並んでいます。途中で $T$ は増えないので、 $T(\pi) \ge T(\text{小さい順の並び})$ です。 $t/f$ が等しい段階の順序は、上の差が $0$ なので $T$ に影響しません。したがって、小さい順の並びはどれも同じ $T$ の値をもち、それが最小値です。

(a) の式は、利用率が $1$ に近づくと待ち時間が $1/(1 - \rho)$ の形で増えることを表しています。検査が $S = 30$ 分で、変更が 1 時間に 1 個届くなら $\rho = 0.5$ で $W = 60$ 分、1 時間に $1.8$ 個なら $\rho = 0.9$ で $W = 300$ 分です。到着が $1.8$ 倍になっただけで、待ち時間は $5$ 倍になります。実行機を足す、検査を速くする（§7.1）、まとめて検査する（§6）のどれも、 $\rho$ を下げる手段です。到着と所要時間の分布についての仮定は理想化で、実際の値はこれと違いますが、 $\rho$ が $1$ に近いところで待ち時間が急に増えるという定性的な結論は変わりません。

(b) の規則は「速い段階を先に」と「落ちやすい段階を先に」を 1 つの比にまとめたものです。静的検査（数秒で、よく落ちる）を最初に、端から端までの結合テスト（数十分）を最後に置くという定石が、ここから出ます。

# Python 3.9.6（標準ライブラリのみ）
from itertools import permutations

STAGES = {"lint": (1, 0.10), "unit": (5, 0.20), "build": (8, 0.05), "e2e": (30, 0.15)}   # (所要時間 [分], 失敗確率)

def expected_time(order):
    total, alive = 0.0, 1.0
    for name in order:
        t, f = STAGES[name]
        total += alive * t           # ここまで全部通ったときだけ実行する
        alive *= 1 - f
    return total

ranked = sorted(permutations(STAGES), key=expected_time)
for order in ranked[:3] + ranked[-2:]:
    print(f"{expected_time(order):7.3f}  " + " → ".join(order))
by_ratio = tuple(sorted(STAGES, key=lambda s: STAGES[s][0] / STAGES[s][1]))
print("t/f の小さい順:", " → ".join(by_ratio), " 最小と一致:", by_ratio == ranked[0])

 31.780  lint → unit → build → e2e
 31.996  lint → unit → e2e → build
 32.080  unit → lint → build → e2e
 41.241  e2e → build → lint → unit
 41.483  e2e → build → unit → lint
t/f の小さい順: lint → unit → build → e2e  最小と一致: True

$t/f$ はそれぞれ $10$ 、 $25$ 、 $160$ 、 $200$ で、24 通りの順列のうち期待所要時間が最小のものは、この比の小さい順と一致します。最悪の順との差は約 $10$ 分です。

注意 7.3

(b) は、段階をどの順に実行してもよい場合の結果です。実際には「ビルドの成果物をテストが使う」といった依存があり、順序は依存グラフのトポロジカル順の中から選ぶことになります。依存のない段階は並列に実行でき、そのときの所要時間は前章の並列ビルドの評価に従います。段階の合否が独立でない場合（静的検査で落ちる変更は単体テストでも落ちやすい）は、条件つきの失敗確率で同じ議論をすることになります。

8. 公開する：冪等なデプロイとロールバック

検査に合格した版を公開先に反映する操作がデプロイです。デプロイは途中で失敗します。ネットワークが切れ、実行機が再起動され、人が中断します。そのあとで「もう一度実行すればよい」と言えるかどうかが、設計の分かれ目です。

定義 8.1（冪等な操作）↗

公開先の状態の集合を $\mathcal{S}$ とする。操作 $g : \mathcal{S} \to \mathcal{S}$ が冪等であるとは、すべての $s \in \mathcal{S}$ について $g(g(s)) = g(s)$ が成り立つことをいう。

次の命題で使う「調整ループ」とは、現在の状態と望ましい状態を見比べ、違う対象を1つずつ直していく操作を、違いがなくなるまで繰り返す仕組みのことです。仮定 (A1)〜(A3) の中身は、リンク先の記事に書いてあります。ここでは、この仕組みなら途中で止まっても最初からやり直せば同じ状態に着く、という結論を確かめます。

命題 8.2（宣言的なデプロイは冪等で、再実行で収束する）✓

公開先の対象の有限集合を $\mathcal{O}$ 、望ましい状態を $d$ とし、デプロイを「現在の状態 $s$ と $d$ の食い違いを減らす操作を、食い違いがなくなるまで繰り返す」調整ループ（定義 6.1［Docker と Kubernetes］）として実装する。命題 6.2［Docker と Kubernetes］の仮定 (A1)〜(A3) が成り立つとし、どの状態 $s$ から始めても最後まで実行した結果を $\mathrm{apply}_d(s)$ と書く。

(a) すべての $s$ について $\mathrm{apply}_d(s) = d$ であり、繰り返しの回数は $s$ と $d$ が食い違っている対象の個数以下である。

(b) $\mathrm{apply}_d$ は冪等である。

証明（命題 8.2）

(a) 命題 6.2［Docker と Kubernetes］より、食い違いの個数 $D(s)$ は 1 回の繰り返しで少なくとも $1$ 減り、高々 $D(s)$ 回で $s = d$ に到達し、到達後は操作が行われません。

(b) (a) より $\mathrm{apply}_d(s) = d$ で、 $D(d) = 0$ なので $\mathrm{apply}_d(d) = d$ です。よって $\mathrm{apply}_d(\mathrm{apply}_d(s)) = \mathrm{apply}_d(d) = d = \mathrm{apply}_d(s)$ です。

(c) 仮定 (A1) より、各回の操作は $(d, s)$ だけから決まり、それまでの経緯によりません。中断後の $s'$ は、単に別の開始状態です。(a) を $s'$ に適用して $\mathrm{apply}_d(s') = d$ です。

例 8.3（手続き的なスクリプトが冪等でない例）

設定ファイルに 1 行を足し、サービスを再起動するスクリプトを考えます。

echo "max_connections = 200" >> /etc/app/app.conf
systemctl restart app

1 行目の操作 $g$ は「ファイルの末尾に行を足す」で、 $g(g(s)) \ne g(s)$ です。再起動に失敗してスクリプトをもう一度実行すると、設定ファイルには同じ行が 2 つ入ります。カウンタを 1 増やす、利用者を作成する（2 度目は「すでに存在する」で失敗する）、データベースの列を追加する、といった操作も同じです。

宣言的に書き直すと、「app.conf の内容は、リポジトリにあるこのファイルと同じであること」になります。操作は「現在の内容と比べ、違えば置き換える」で、何度実行しても結果は同じです。命題 8.2 の言葉では、望ましい状態 $d$ がファイルの内容全体で、食い違いがなければ何もしません。

宣言的なデプロイでは、ロールバックも同じ操作です。前の版の望ましい状態 $d_{\text{old}}$ を取り出して $\mathrm{apply}_{d_{\text{old}}}$ を実行すれば、(a) より $d_{\text{old}}$ に戻ります。 $d$ がリポジトリにあれば、どの版の $d$ もコミットから取り出せます。ただし、これは状態が $\mathcal{O}$ の上の値で尽くされている場合の話です。データベースの中身のように、操作の履歴が積み重なる状態は、望ましい状態を宣言し直すだけでは元に戻りません。スキーマの変更は「古い版のコードでも新しい版のコードでも動く中間の形」を挟んで段階的に行う、というのが定石です。

注意 8.4

この記事で定理にしなかった話題を 3 つ挙げます。

段階的な公開。 新しい版を利用者の一部（たとえば $1\%$ ）にだけ出し、誤り率や応答時間を旧版と比べてから全体に広げる方法です。比べる判定は 2 標本の仮説検定で、検出したい差が小さいほど多くの観測が要ります。稼働中のレプリカを少しずつ入れ替えるときの所要時間の下界は命題 7.7［Docker と Kubernetes］にあります。可用性の定義は定義 6.1［クラウドコンピューティング］を参照してください。
ブランチの運用。 短命の枝を頻繁に主ブランチへ併合する運用（トランクベース開発）と、長命の枝を使う運用の比較は、チームの大きさや公開の頻度に依存する経験的な議論です。定理 3.1 は、枝が長く離れているほど併合時に検査で初めて見つかる問題が増えうることを示唆しますが、どちらがよいかを定理として述べることはできません。
供給網の安全性。 CI は、ソースから成果物を作る過程そのものなので、攻撃の対象になります。成果物への署名、どのソースからどの手順で作られたかの記録（来歴）、前章のロックファイルと再現可能なビルドが対策の柱です。CI の設定に鍵やトークンを直接書かず、実行環境の秘密情報の仕組みから渡すのは、その最低限の作法です。

8.1. 最小のパイプライン

依存の固定・検査・ビルドの 3 段階からなる CI の設定の最小例を示します（GitHub Actions の書式）。

name: ci
on:
  pull_request:
  push:
    branches: [main]
jobs:
  check:
    runs-on: ubuntu-24.04
    steps:
      - uses: actions/checkout@v4
      - uses: actions/setup-node@v4
        with:
          node-version: 22
      - run: npm ci             # ロックファイルどおりに依存を入れる
      - run: npm run validate   # 検査（速く、よく落ちる）
      - run: npm run build      # ビルド（遅い）

各行がこの記事と前章の命題に対応しています。実行環境と言語処理系の版を明示するのは、宣言していない依存を減らすためです。npm ci はロックファイルに書かれた版だけを入れ、宣言と食い違えば失敗します（前章のロックファイルの命題）。検査をビルドの前に置くのは命題 7.2 (b) の順序です。pull_request で走る検査は、多くの CI では枝の先頭ではなく主ブランチと併合した結果に対して実行されますが、検査の後で主ブランチが進めば定理 3.1 の隙間が残るので、不変条件を厳密に保つにはマージキューを使います。

例 8.5（教科書サイトのパイプライン：検査 → ビルド → 公開）

定理や定義に識別子を付けて相互参照する教科書サイトを考えます。変更は記事の追加や修正で、パイプラインは次の 3 段階です。

検査。 記事の書式、識別子の一意性、相互参照の解決、数式の構文、証明のない定理が増えていないかを調べる。数十秒で終わり、書き手の誤りの大半をここで止める。
ビルド。 前処理（番号の採番と索引の生成）のあと、静的サイトを生成する。数分かかる。
公開。 生成物を配信先に置く。置く内容は「この版の生成物」と宣言されるので、冪等である（命題 8.2）。

この並びは、所要時間が短く落ちやすい順（命題 7.2 (b)）であり、依存の順でもあります。検査が決定的であること、つまり同じ版に対して同じ違反の一覧を返すことが、主ブランチの不変条件（定理 3.3）の前提です。検査の中身がどのような定理に支えられているかは、次章の事例研究で読みます。

9. 演習

演習 9.1易

テストが $n = 200$ 個あり、各テストは正しいコードの上でも 1 回の実行で独立に確率 $q = 0.005$ で不合格になる。

検査全体が誤って不合格になる確率を求めよ。
「2 回のうち 1 回でも合格すれば合格」とする再実行を入れたとき、その確率はいくらになるか。
同じ再実行のもとで、1 回の実行で確率 $r = 0.3$ でしか現れない競合状態を見逃す確率は、再実行なしの場合と比べてどう変わるか。

解答

定理 4.1 を使う。

$1 - (1 - 0.005)^{200} = 1 - 0.995^{200} = 0.633$ 。上界 $nq = 1$ 、下界 $1 - e^{-1} = 0.632$ の間にある。
$q^2 = 2.5 \times 10^{-5}$ なので $1 - (1 - 2.5 \times 10^{-5})^{200} = 0.00499$ 。上界 $nq^2 = 0.005$ とほぼ等しい。誤って落ちる確率は約 $127$ 分の $1$ になった。
再実行なしでは見逃す確率は $1 - r = 0.7$ 、再実行ありでは $1 - r^2 = 1 - 0.09 = 0.91$ である。検出できる確率は $0.3$ から $0.09$ に下がる。誤検出を $127$ 分の $1$ にした代償として、この種の不具合の検出率が $3$ 分の $1$ 以下になっている。

演習 9.2標準

3 つの段階 A・B・C の（所要時間、失敗確率）が A: $(2, 0.5)$ 、B: $(1, 0.1)$ 、C: $(10, 0.5)$ であるとする（合否は独立）。

最も短い段階 B を最初に置いた順 B → A → C と、命題 7.2 (b) の規則による順の期待所要時間を計算して比べよ。
失敗確率がすべて等しいとき、および所要時間がすべて等しいとき、最適な順はそれぞれどうなるか。

解答

$t/f$ は A が $4$ 、B が $10$ 、C が $20$ なので、規則による順は A → B → C である。

T(\mathrm{A, B, C}) = 2 + 0.5 \cdot 1 + 0.5 \cdot 0.9 \cdot 10 = 2 + 0.5 + 4.5 = 7.0,

T(\mathrm{B, A, C}) = 1 + 0.9 \cdot 2 + 0.9 \cdot 0.5 \cdot 10 = 1 + 1.8 + 4.5 = 7.3 .

B は最も短いが、 $10$ 回に $1$ 回しか落ちないので、先に置いても後ろの段階をほとんど省けない。A は B の $2$ 倍の時間がかかるが、 $2$ 回に $1$ 回落ちるので、先に置くと後ろを半分省ける。 2. $f_i = f$ がすべて等しいとき、 $t_i/f_i$ の順は $t_i$ の順なので、所要時間の短い順が最適である。 $t_i = t$ がすべて等しいとき、 $t/f_i$ の小さい順は $f_i$ の大きい順なので、落ちやすい順が最適である。「速い順」「落ちやすい順」という 2 つの経験則は、どちらもこの規則の特別な場合である。

演習 9.3標準

変更の不良率が $p = 0.04$ で、定理 6.2 の仮定が成り立つとする。

2 段階の方式で $b = 5$ と $b = 6$ のときの 1 変更あたりの期待検査回数を求め、(b) の評価 $\sqrt{2p} \le \min_b E(b) \le 2\sqrt{p} + p$ と比べよ。
検査 1 回が 20 分で、1 日に 60 個の変更が届く。1 つずつ検査する場合と $b = 6$ でまとめる場合の、1 日の検査時間の期待値を比べよ。
まとめ検査が不合格のとき、定理 5.1 の二分探索で不良を 1 つ特定することを考える。まとまりの中の不良が 2 つ以上あるとき、単調性の仮定に当たるものは何か。

解答

$E(5) = 1/5 + 1 - 0.96^5 = 0.2 + 1 - 0.8154 = 0.3846$ 、 $E(6) = 1/6 + 1 - 0.96^6 = 0.1667 + 1 - 0.7828 = 0.3839$ 。 $b = 6$ のほうがわずかに小さい。評価は $\sqrt{0.08} = 0.283$ と $2 \cdot 0.2 + 0.04 = 0.44$ で、どちらの値もこの間にある。
1 つずつなら $60 \times 20 = 1200$ 分。まとめると $60 \times 0.3839 \times 20 = 461$ 分で、約 $38\%$ になる。
まとまりの変更を $\delta_1, \ldots, \delta_b$ の順に重ねた版 $s_0, s_1, \ldots, s_b$ （定理 3.3 (b) の $s_j$ ）を履歴とみる。「不良な変更を 1 つでも含めば不合格」という仮定のもとでは、 $s_j$ が不合格であることと、 $\delta_1, \ldots, \delta_j$ の中に不良があることが同値なので、最初の不良な変更の番号を $f$ とすると「 $s_j$ が不合格 $\iff j \ge f$ 」となり、単調性が成り立つ。二分探索は $\lceil \log_2 b \rceil$ 回で最初の不良 $\delta_f$ を特定する。2 つ目以降の不良は、 $\delta_f$ を取り除いてから残りを検査し直して探す。

参考文献

M. Fowler, “Continuous Integration”, https://martinfowler.com/articles/continuousIntegration.html — 継続的インテグレーションの実践をまとめた解説。主線を常に健全に保つという考え方の出典です。
J. Humble, D. Farley, Continuous Delivery: Reliable Software Releases through Build, Test, and Deployment Automation, Addison-Wesley, 2010 — デプロイのパイプラインと、冪等な公開・ロールバックの設計。
T. Winters, T. Manshreck, H. Wright (eds.), Software Engineering at Google, O’Reilly Media, 2020 — 不安定なテスト、テストの選択、大規模な CI の運用を扱う章があります。
R. Dorfman, “The detection of defective members of large populations”, The Annals of Mathematical Statistics 14(4) (1943), 436–440 — 2 段階の集団検査の原論文。定理 6.2 (a) の式はここにあります。
D.-Z. Du, F. K. Hwang, Combinatorial Group Testing and Its Applications, 2nd ed., World Scientific, 2000 — 集団検査の理論の教科書。
Q. Luo, F. Hariri, L. Eloussi, D. Marinov, “An empirical analysis of flaky tests”, Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE 2014) — 不安定なテストの原因の分類についての実証研究。
Git Documentation, “git-bisect”, https://git-scm.com/docs/git-bisect — git bisect run の終了コードの約束を含む一次資料。

このテーマの 100 本ノック（50 問）

執筆: Claude Code（Opus 5.5）、Claude Code（Sonnet 5.5）・監査 2 回（Claude Code）・最終 2026-10-12

この記事の誤りを報告する・運営: 夢現技研合同会社・料金・利用条件・特定商取引法に基づく表記