練習問題

圧倒的大部分の人は平均より多い本数の指を持つ。この事実が成り立つ理由を説明する文章を次の中から全て選べ。解答の理由を説明せよ。

1. 多くの人は自分でも気付いていない秘密の指を何本か持っている。

2. ほとんどの人は親指を指に含めて数えるのに対して、親指を指に含めない異常者が少数いる。

3. 多趾症 (polydactyly, 生まれつき指の本数が多い疾患) は指の切断より稀である。

4. 世界中の人々が持つ指の本数を合計して世界人口で割ると \(10\) より小さい。

5. 指の本数は負にならないので、Markov の定理から従う。

6. \(5\) 本より少ない指を持つことは \(5\) 本より多い指を持つことより一般的である。

牛に感染する冷牛病 (cold cow disease) と呼ばれる病気が流行している。牛が冷牛病に感染すると体温が下がっていき、\(90^{\circ}\text{F}\) (華氏温度) を下回ると死んでしまう。流行はすさまじく、ある牧場の牛 (死んだ牛を含む) の平均体温は \(85^{\circ}\text{F}\) まで低下した。どの牛の体温も \(70^{\circ}\text{F}\) 以上であり、冷牛病による体温低下以外の理由で死亡する牛はいないと仮定する。

1. Markov の定理 (定理 20.1.1) を使って、死んでいない牛の割合は最大でも \(3/4\) だと示せ。

2. 牧場に \(400\) 頭の牛がいると仮定する。平均体温が \(85^{\circ}\text{F}\) かつ \(3/4\) の牛が死んでいないような牛の体温の分布を示すことで、\(\text{(a)}\) で示した上界が最良だと証明せよ。

3. \(\text{(b)}\) の結果は平均に関する算術的事実から得られたものであり、その導出で確率に関する概念は全く使われていない。しかし、\(\text{(b)}\) で検証された \(\text{(a)}\) の結果は Markov の定理を使って確率変数の期待値からの偏差に関する確率の上界を考えることで得られている。牛の体温 \(T\) を確率変数とみなすことで、このアプローチを正当化せよ。確率変数 \(T\) が定義される確率空間を注意深く説明すること。何が結果となり、それぞれの結果はどのような確率を持つか？ Markov の定理の適用を正当化するのに必要な、牛の平均体温と \(T\) の関係を正確に説明せよ。

\(R\) を非負確率変数とする。Markov の定理 (定理 20.1.1) を使うと、実数 \(x > \operatorname{Ex} [R]\) に対する \(\operatorname{Pr} [R \geq x]\) の上界が得られる。\(R\) の下界が \(b\) なら、\(R - b\) に Markov の定理を適用することで \(\operatorname{Pr} [R \geq x]\) に関する異なる上界が得られる可能性がある。

1. \(b > 0\) なら、\(R - b\) に Markov の定理を適用して得られる \(\operatorname{Pr} [R \geq x]\) の上界は同じ定理を \(R\) に直接適用して得られる上界より優れていると示せ。

2. \(\text{(a)}\) で最も優れた上界を与える \(b \geq 0\) の値を答えよ。

牛に感染する温牛病 (hot cow disease) と呼ばれる病気が流行している。牛が温牛病に感染すると体温が上がっていき、\(90^{\circ}\text{F}\) (華氏温度) を上回ると死んでしまう。流行はすさまじく、ある牧場の牛 (死んだ牛を含む) の平均体温は \(120^{\circ}\text{F}\) まで上昇した。どの牛の体温も \(140^{\circ}\text{F}\) 以下であり、温牛病による体温上昇以外の理由で死亡する牛はいないと仮定する。

1. Markov の定理 (定理 20.1.1) を使って、死んでいない牛の割合は最大でも \(2/5\) だと示せ。

2. \(\text{(a)}\) の結果は平均に関する算術的事実である。しかし、その導出では Markov の定理を使って確率変数の期待値からの偏差に関する確率の上界を考えている。牛の体温 \(T\) を確率変数とみなすことで、このアプローチを正当化せよ。確率変数 \(T\) が定義される確率空間を注意深く説明すること。何が結果となり、それぞれの結果はどのような確率を持つか？ Markov の定理の適用を正当化するのに必要な、牛の平均体温と \(T\) の関係を正確に説明せよ。

ある牧場の全ての牛が奇牛病 (wacky cow disease) に感染した。奇牛病に感染した牛の体温がその牧場の牛の平均体温から \(10^{\circ}\text{F}\) 以上離れると、その牛は死んでしまう。その牧場の牛の平均体温は \(100^{\circ}\text{F}\) (華氏温度) だと判明した。測定に使用した体温計は非常に敏感であり、測定された体温が同じ \(2\) 頭の牛の組は存在しなかった。

測定した牛の体温の収集分散 (collection-variance) は \(20\) だった。ここで実数の集合 \(A\) の収集分散 \(\operatorname{CVar}(A)\) は次のように定義される:

ここで \(\mu\) は \(A\) に含まれる実数の平均値を表す。収集分散は平均二乗偏差 (mean square deviation) とも呼ばれる。

1. ランダムに選択した牛の体温を表す確率変数を \(T\) とする。\(T\) に Chebyshev の定理 (定理 20.2.3) を適用することで、奇牛病が原因で死亡する牛の割合が最大で \(20\%\) だと示せ。

\(\text{(a)}\) の結論は特定の割合に関する主張であり、確率変数の偏差に関する確率を上から抑えることで証明されている。このアプローチを正当化するには、牛の体温を表す確率変数 \(T\) が定義される適切な確率空間を説明する必要がある。

2. \(T\) が定義される確率空間を注意深く説明せよ。何が結果か？ それぞれの結果はどれだけの確率を持つか？

3. 任意の性質 \(P\) を持つ牛の割合は \(\text{(b)}\) で解答した確率空間における \(\operatorname{Pr} [P]\) に等しい理由を説明せよ。

4. \(\operatorname{Var} [T]\) が上記の収集分散に等しいことを示せ。

\(120\) 人の生徒が期末試験を受け、平均点は \(90\) 点だった。平均点以外に試験に関して分かっていることはない。特に、試験が \(100\) 点満点とは限らない。ただし、試験の点数は負にならないとする。

1. \(180\) 点以上を取った学生の人数の最良の上界を求めよ。

2. あるクラスメイトによると、試験の最低点は \(30\) 点だという。この情報が正しいと仮定するとき、\(180\) 点以上を取った学生の人数の最良の上界を求めよ。

公平なコインを \(100\) 回投げたとする。それぞれのコイン投げの結果は相互独立だと仮定する。

1. 表が出る回数の期待値を求めよ。

2. Markov の定理 (定理 20.1.1) を使って、表が出る回数が \(70\) 回以上になる確率の上界を求めよ。

3. 表が出る回数の分散を求めよ。

4. Chebyshev の定理 (定理 20.2.3) を使って、表が出る回数が \(30\) 回以下または \(70\) 回以上になる確率の上界を求めよ。

Albertアルバート は一日中ギャンブルばかりしている。彼は毎日ドローポーカーを \(240\) 回、ブラックジャックを \(120\) 回、スタッドポーカーを \(40\) 回プレイする。彼がプレイするドローポーカーの勝率は \(1/6\), ブラックジャックの勝率は \(1/2\), スタッドポーカーの勝率は \(1/5\) である。Alber が \(1\) 日にギャンブルで勝利する回数を表す確率変数を \(W\) とする。

1. \(\operatorname{Ex} [W]\) を求めよ。

2. Markov の定理 (定理 20.1.1) を使って、Albert が \(1\) 日に勝利する回数が \(216\) 以上になる確率の上界を求めよ。

3. それぞれのギャンブルの勝敗は全組独立だと仮定する。\(\operatorname{Var} [W]\) を求めよ。解答は完全に計算されていない数値式で構わない。

4. Chebyshev の定理 (定理 20.2.3) を使って、Albert が \(1\) 日に勝利する回数が \(216\) 以上になる確率の上界を求めよ。定数 \(v = \operatorname{Var} [W]\) を含む数値式を解答すること。

あるパーティー会場で働いている帽子管理スタッフは散々な一日を過ごしたので、パーティーが終わったときに預かった \(n\) 個の帽子を \(n\) 人の参加者にランダムに返却した。任意の参加者が正しい帽子を受け取る確率は \(1/n\) である。

事象 [\(i\) 番目の参加者が正しい帽子を受け取る] に対応する指示確率変数を \(X_{i}\) とする。正しい帽子を受け取る参加者の人数を表す確率変数を \(S_{n}\) とする。

1. 正しい帽子を受け取る参加者の人数の期待値 \(\operatorname{Ex} [S_{n}]\) を求めよ。

2. \(i \neq j\) に対する \(\operatorname{Ex} [X_{i} \cdot X_{j}]\) を表す簡単な式を求めよ。

   ヒント: \(5\) 人目の参加者が正しい帽子を受け取ったという条件の下で \(2\) 人目の人物が正しい帽子を受け取る確率 \(\operatorname{Pr} [X_{2} = 1 \, | \, X_{5} = 1]\) はいくつか？

3. \(\operatorname{Var} [S_{n}]\) が \(X_{i}\) の分散の和に等しくない理由を説明せよ。

4. \(\operatorname{Ex} [(S_{n})^{2}] = 2\) だと示せ。

   ヒント: \(X_{i}\) は指示確率変数なので \((X_{i})^{2} = X_{i}\) が成り立つ。

5. \(S_{n}\) の分散を求めよ。

6. Chebyshev の定理 (定理 20.2.3) を使って、\(10\) 人以上が正しい帽子を受け取る確率は \(1\%\) 以下だと示せ。

\(R\) を任意の確率変数とする。\(R\) が平均 \(\mu\) と標準偏差 \(\sigma\) を持つとき、Chebyshev の定理 (定理 20.2.3) は任意の \(x > 0\) に対して次の不等式が成り立つと主張する:

任意の実数 \(\mu\) と \(x \geq \sigma > 0\) を満たす任意の \(x\), \(\sigma\) に対して、Chebyshev の定理が示す上界が最良になる、つまり次の等式が成り立つ確率変数 \(R\) が存在すると示せ:

ヒント: まず \(\mu = 0\) と仮定し、\(R\) の値域を \(\left\{ -x, 0, x \right\}\) とする。

あるプログラムは \(1\) 時間が経過するごとに確率 \(p\) でクラッシュする。初めてクラッシュするまでの時間を表す確率変数を \(H\) とする。

1. \(x > 0\) とする。Chebyshev の定理 (定理 20.2.3) を使って、次の確率の上界を求めよ:

   \[ \operatorname{Pr} \hspace{-2pt} \left[ \, \left| H - \frac{1}{p} \right| > \frac{x}{p} \right] \]

2. \(\text{(a)}\) の結果を使って、\(a \geq 2\) なら次の不等式が成り立つと示せ:

   \[ \operatorname{Pr} \hspace{-2pt} \left[ H > \frac{a}{p} \right] \leq \frac{1 - p}{(a - 1)^{2}} \]

   ヒント: \(\displaystyle H > \frac{a}{p} \ \ \longleftrightarrow \ \ \left| H - \frac{1}{p} \right| > \frac{a - 1}{p}\) を示す。

3. 次の確率を具体的に求めよ:

   \[ \operatorname{Pr} \hspace{-2pt} \left[ H > \frac{a}{p} \right] \]

   \(p > 0\) を固定するとき、\(\displaystyle H > \frac{a}{p}\) が成り立つ確率は \(\text{(b)}\) で Chebyshev の定理から求めた上界より漸近的に小さい \(a\) の関数だと結論付けよ。

\(R\) を正整数の値を取る確率変数とする。

1. \(\operatorname{Ex} [1/R]\) はどれだけ大きくなれるか？

2. \(R\) が取る値が \(1\) と \(2\) だけのとき、\(\operatorname{Var} [R]\) はどれだけ大きくなれるか？

3. \(\operatorname{Ex} [R] = 2\) のとき、\(\operatorname{Var} [R]\) はどれだけ大きくなれるか？

自宅のドアの前に立つ男が \(n\) 個の鍵を手にしている。その中の \(1\) 個はドアを開く鍵である。男はランダムに選んだ鍵を試し、ドアが開かなかったら試した鍵を足元に置いて同じことを繰り返す。このとき、男は必ず \(n\) 回以内に正しい鍵を見つけられる。

ドアが開くまでに男が試す鍵の個数を表す確率変数を \(T\) とする。問題 19.28 では次の等式を求めた:

\(\operatorname{Var} [T]\) を閉形式の式で表せ。

\(R\) は正整数の値を取る確率変数であり、次の関係を満たすという:

ただし \(c\) は次のように定義される:

1. \(\operatorname{Ex} [R]\) が有限だと示せ。

2. \(\operatorname{Ex} [R^{2}]\) そして \(\operatorname{Var} [R]\) が無限大だと示せ。

この問題の結果を冗談めかして表現すれば「無限の平方根は有限」となる。つまり \(T ::= R^{2}\) としたとき \(\text{(b)}\) からは \(\operatorname{Ex} [T] = \infty\) が分かり、\(\text{(a)}\) からは \(\operatorname{Ex} [\sqrt{T}] < \infty\) が分かる。

自宅のドアの前に立つ男が \(n\) 個の鍵を手にしている。その中の \(1\) 個はドアを開く鍵である。男はランダムに選んだ鍵を試し、ドアが開かなかったら試した鍵を手元に戻して同じことを繰り返す。このとき、男は同じ鍵を何度も試す可能性がある。ドアが開くまでに男が試す鍵の個数を表す確率変数を \(T\) とする。

1. 次の等式が成り立つ理由を説明せよ:

   \[ \begin{aligned} \operatorname{Ex} [T] &= n \\ \operatorname{Var} [T] &= n(n - 1) \end{aligned} \]

\(f_{n}(a)\) を次のように定める:

2. \(n > 1\) を固定するとき、次の関係が成り立つことを Chebyshev の定理 (定理 20.2.3) を使って示せ:

   \[ f_{n} (a) = \Theta \hspace{-2pt} \left( \frac{1}{a^{2}} \right) \tag{20.26}\]

3. \(n\) を固定するときの \(f_{n} (a)\) の上界として関係 \(\text{(20.26)}\) が示すものより漸近的に小さいものを求めよ。

   十分大きい \(n\) に対する次の近似を使って構わない:

   \[ \left( 1 - \frac{1}{n} \right)^{\! cn} \approx \frac{1}{e^{c}} \]

公平なコインと確率 \(3/4\) で表を向く偏ったコインがあり、あなたにいずれか一枚が渡されたとする。渡されたコインを識別する次の手続きを考えよう: 正整数 \(n\) を選び、コインを \(n\) 回投げる。コインが表を向いた回数が \((1/2)n\) より \((3/4)n\) に近いなら「偏ったコインが渡された」と答え、そうでなければ「公平なコインが渡された」と答える。

1. Chebyshev の定理 (定理 20.2.3) を使って、どちらのコインが渡された場合でも \(0.95\) 以上の確率でコインを正しく識別できる \(n\) の値の上界を求めよ。

2. 任意のパラメータ \(n\), \(p\) を持った二項分布の確率密度関数と累積分布関数を計算するプログラムが利用できる (またはグラフや表で値を確認できる) と仮定する。このとき、\(0.95\) 以上の確率で渡されたコインを識別できる \(n\) の最小値はどのように求められるか？ そうして求まる \(n\) の値と \(\text{(a)}\) で求めた上界を比べたとき何が言えると期待できるか？

3. こうして求まった最小値 \(n\) は次の性質を持つ:

   渡されたコインを \(n\) 回投げ、表の出た回数が \((5/8)n\) 以上かどうかでコインを識別すると、その識別結果は \(0.95\) 以上の確率で正しい。

   この事実は次の確率について何を意味するか？

   \[ \operatorname{Pr} [\text{偏ったコインが渡された} \, | \, \text{表の出た回数} \geq (5/8)n] \]

   何も意味しないならそのように答えよ。

実数値確率変数 \(R\) の平均が \(\mu\) のとき、その期待絶対偏差 (expected absolute deviation) は次のように定義される:

この期待絶対偏差は常に標準偏差 \(\sigma\) 以下だと示せ。議論を簡単にするため、\(R\) は有限確率空間上で定義されると仮定してよい。

ヒント: 標本空間に含まれる結果を \(\omega_{1}\), \(\omega_{2}\), \(\ldots\), \(\omega_{n}\) として、\(\textbf{p}\) と \(\textbf{r}\) を次のように定める:

\(n\) 要素ベクトル \(\textbf{v}\), \(\textbf{w}\) の内積を通常通り \(\textbf{v} \cdot \textbf{w} = \sum_{i=1}^{n} v_{i} w_{i}\) と定義する。さらに、\(n\) 要素ベクトル \(\textbf{v}\) のノルムを \(\left| \textbf{v} \right| ::= \sqrt{\textbf{v} \cdot \textbf{v}}\) と定める。このとき、次の等式が成り立つことを利用する:

次に示す「片側」バージョンの Chebyshev の定理を証明せよ:

ヒント: 実数 \(a \geq 0\) に対して \(S_{a} ::= (R - \operatorname{Ex} [R] + a)^{2}\) と定める。このとき \(R - \operatorname{Ex} [R] \geq x\) なら \(S_{a} \geq (x + a)^{2}\) が成り立つ。Markov の定理 (定理 20.1.1) を \(\operatorname{Pr} [S_{a} \geq (x + a)^{2}]\) に適用し、上界が最小になるように \(a\) の値を選ぶ。

分散の全組独立加法性 (定理 20.3.8) を証明せよ:

ヒント: 全ての \(i\) で \(\operatorname{Ex} [E_{i}] = 0\) と仮定して問題ない。なぜか？

次のゲームを考える: プレイヤーはターンを \(n\) 回プレイする。各ターンでプレイヤーはコインを何回か投げる: 最初のターンでは \(1\) 回投げ、第 \(2\) ターンでは \(2\) 回投げ、以下同様に第 \(n\) ターンでは \(n\) 回投げる。全てのコイン投げは相互独立と仮定する。

使用するコインは公平ではなく、表が出る確率が \(p\) である。特定のターンで投げたコインが全て表を向いたら、プレイヤーはそのターンで勝利となる。プレイヤーが勝利するターンの数を表す確率変数を \(W\) とする。

1. \(\operatorname{Ex} [W]\) を閉形式の (総和が含まれない) 式で表せ。

2. \(\operatorname{Var} [W]\) を閉形式の式で表せ。

\(K_{n}\) を \(n\) 頂点の完全グラフとする。\(K_{n}\) の辺に赤・緑・青のいずれかの色をランダムに割り当てる試行を考える。各辺に対する色の割り当ては相互独立であり、任意の辺には \(r\) の確率で赤が、\(b\) の確率で青が、\(g\) の確率で緑が割り当てられるとする。

\(K_{n}\) の異なる \(3\) 頂点を集めた集合を三角形 (triangle) と呼び、全ての頂点が同じ色を持つ三角形を単色 (monochromatic) と呼ぶ。

1. 任意の固定された三角形 \(T\) が単色である確率を \(m\) とする。\(r\), \(g\), \(b\) を使った簡単な式で \(m\) を表せ。

2. 事象 [三角形 \(T\) が単色である] に対応する指示確率変数を \(I_{T}\) とする。\(m\), \(r\), \(g\), \(b\) を使った簡単な式で \(\operatorname{Ex} [I_{T}]\) と \(\operatorname{Var} [I_{T}]\) を表せ。

\(T\), \(U\) を異なる三角形とする。

3. \(T\) と \(U\) が辺を共有しないとき、および \(T\) と \(U\) が辺を共有するときのそれぞれについて、\(T\) と \(U\) が両方とも単色である確率を求めよ。

以降では \(\displaystyle r = g = b = \frac{1}{3}\) と仮定する。

4. \(I_{T}\) と \(I_{U}\) が独立な確率変数だと示せ。

5. \(K_{n}\) に含まれる単色な三角形の個数を表す確率変数を \(M\) とする。\(n\), \(m\) を使った簡単な式で \(\operatorname{Ex} [M]\) と \(\operatorname{Var} [M]\) を表せ。

6. \(\mu ::= \operatorname{Ex} [M]\) とする。Chebyshev の定理 (定理 20.2.3) を使って次の不等式を示せ:

   \[ \operatorname{Pr} \hspace{-2pt} \left[ |M - \mu| > \sqrt{\mu \log \mu} \right] \leq \frac{1}{\log \mu} \]

7. 次の等式が成り立つと結論付けよ:

   \[ \lim_{n \to \infty} \operatorname{Pr} \hspace{-2pt} \left[ |M - \mu| > \sqrt{\mu \log \mu} \right] = 0 \]

確率 \(p\) で表を向く偏ったコインがある。このコインを相互独立に \(n\) 回投げる試行を考える。表の出る回数を表す確率変数を \(H\) とする。

1. \(p\) と \(n\) を使った閉形式の (総和を使わない) 式で \(\operatorname{Ex} [H]\) を表せ。解答を簡単に説明せよ。

2. \(p\) と \(n\) を使った閉形式の式で \(\operatorname{Var} [H]\) を表せ。解答を簡単に説明せよ。

3. Markov の定理 (定理 20.1.1) を使って、表の出る回数がコインを投げる回数の \(1\%\) だけ(\(n/100\) だけ) 期待値より大きくなる確率の上界を求めよ。解答は \(p\) を使った閉形式の式で表せ。

4. Chebyshev の定理 (定理 20.2.3) を使って得られる、\(H\) の値が \(\operatorname{Ex} [H]\) から \(n/100\) 以上離れる確率の上界が次の値だと示せ:

   \[ 100^{2} \frac{p(1 - p)}{n} \]

5. \(\text{(d)}\) で示した上界は、コインを \(n\) 回投げたとき表が出る割合と \(p\) の差が \(0.01\) 以下になる確率が \(95\%\) 以上になるような \(n\) が存在することを示している。この \(n\) を \(p\) を使って表せ。

ある教室には次に示すように \(16\) 個の机が \(4 \times 4\) の格子状に並んでいる:

水平方向または垂直方向に隣り合う二つの机を隣接組 (adjacent pair) と呼ぶことにする。各行には水平方向に隣り合う隣接組が \(3\) 個あるので、水平方向に隣り合う隣接組は全部で \(12\) 個ある。同様に垂直方向に隣り合う隣接組も全部で \(12\) 個ある。隣接組の一方に男子が座り、もう一方に女子が座るとき、その隣接組はフラーテーション (flirtation) を持つと言う。

1. 男子と女子が未知の確率でそれぞれの机に割り当てられるとする。Markov の定理 (定理 20.1.1) を使って、フラーテーションの個数が期待値より \(33 \frac{1}{3} \%\) 以上大きくなる確率の上界を求めよ。

それぞれの机には確率 \(p\) (\(0 < p < 1\)) で男子が、確率 \(1 - p\) で女子が相互独立に割り当てられると仮定する。

2. フラーテーションの個数の期待値を \(p\) で表せ。

   ヒント: 事象 [隣接組 \(D\) がフラーテーションを持つ] に対応する指示確率変数を \(I_{D}\) とする。

二つの隣接組が同じ机を共有することを交わる (overlap) と言うことにする。例えば、各行の左から \(1\) 番目の隣接組と \(2\) 番目の隣接組は交わる。\(2\) 番目の隣接組と \(3\) 番目の隣接組も交わるのに対して、\(1\) 番目の隣接組と \(3\) 番目の隣接組は交わらない。

3. \(p = 1/2\) で隣接組 \(D\), \(E\) が交わるなら、\(I_{D}\) と \(I_{E}\) が独立だと示せ。

4. \(p = 1/2\) のとき、フラーテーションの個数の分散を求めよ。

5. Chebyshev の定理 (定理 20.2.3) を使って、フラーテーションの個数と期待値の差が隣接組の個数の \(20\%\) 以下になる確率の上界を求めよ。

6. \(p \neq 1/2\) で隣接組 \(D\), \(E\) が交わるなら、\(I_{D}\) と \(I_{E}\) が独立でないと示せ。

7. \(F_{D_{1}}\), \(F_{D_{2}}\), \(F_{D_{3}}\), \(F_{D_{4}}\) が (\(p = 1/2\) であっても) 相互独立でない ような隣接組 \(D_{1}\), \(D_{2}\), \(D_{3}\), \(D_{4}\) を答えよ。

ある世論調査によると、進化論が「証拠によって十分に支持されている」と考えるアメリカ人 (成人) の割合は \(35\%\) である。この世論調査では \(1928\) 人の一様かつ独立にランダム抽出されたアメリカ人が質問の対象となった。その中で \(675\) 人が進化論を信じると答えたので、世論調査会社は進化論を信じるアメリカ人の割合が \(675/1928 \approx 0.350\) だと結論付けた。さらに、誤差範囲 (margin of error) は \(3\) ポイントとも主張した。つまり、推定値 \(0.350\) と実際の割合の差が \(0.03\) 以下である確率が高いと自信を見せた。

1. 任意の指示確率変数の分散の最大値を求めよ。

2. 全組独立サンプリング定理 (定理 20.4.1) を使って、世論調査会社が上記の主張に対して持つことができる信頼度を求めよ。

3. 世論調査会社は \(35\%\) の推定値に \(99\%\) 以上の信頼度があると主張している。この結論がどのように得られたのか、考えられる可能性を説明せよ。(どのような値を計算したかを答えるだけで構わない。実際に計算する必要はない。)

4. 世論調査会社が収集したデータと行った計算の正確性を全て信じるとき、進化論を信じるアメリカ人の割合が \(35 \pm 3\%\) である確率が高いと結論付けられるか？

\(B_{1}\), \(B_{2}\), \(\ldots\), \(B_{n}\) を整数区間 \([1..d]\) 上の一様分布に従う相互独立な確率変数とする。事象 [\(B_{i} = B_{j}\)] に対応する指示確率変数を \(E_{i,j}\) とする。

事象 [\(B_{i} = B_{j}\)] が成り立つ集合 \(\left\{ i, j \right\} \ (i \neq j)\) の個数を表す確率変数を \(M\) とする。このとき次の等式が成り立つ:

第 17.4 節で見た (そして問題 19.2 で証明した) ように、\(i \neq j\) なら \(\operatorname{Pr} [B_{i} = B_{j}] = 1/d\) であり、\(1 \leq i < j \leq n\) に対する確率変数 \(E_{i,j}\) は全組独立である。

1. \(i \neq j\) に対する \(\operatorname{Ex} [E_{i,j}]\) と \(\operatorname{Var} [E_{i,j}]\) を求めよ。

2. \(\operatorname{Ex} [M]\) と \(\operatorname{Var} [M]\) を求めよ。

3. ある講義には受講者が \(500\) 人いる。最年少の受講者は \(15\) 年前に、最年長の受講者は \(35\) 年前に産まれた。誕生日が同じ受講生の組の個数が \(12\) 以上 \(23\) 以下になる確率が \(50\%\) 以上だと示せ。議論を簡単にするため、受講者の誕生日は \(35\) 年前から \(15\) 年前までの \(7305\) 日間に一様ランダムに分布すると仮定してよい。

   ヒント: 誕生日が同じ受講者の組の個数を表す確率変数を \(D\) とする。このとき同値関係 \(\left| D - \operatorname{Ex} [D] \right| < 6 \ \ \longleftrightarrow \ \ D \in [12..23]\) が成り立つ。

交通裁判所で、ある被告が自身に切られた速度超過切符は無効だと主張した。彼は「高速道路では事実上全員が超過速度で走っているので、警察には好きな人物に切符を切ることができる裁量が与えられる。それは憲法違反なので切符も無効だ」と述べた。[この反論を実際に使うことは推奨できない :-)]

自身の主張の論拠として、彼は次のデータを示した: 高速道路を利用する \(3{,}125\) 台の車をランダムにサンプルしたところ、その \(94\%\) がどこかの時点で速度超過をしていた。サンプリング理論 ── 特に全組独立サンプリング定理 (定理 20.4.1) ── を使って計算すると、このとき速度超過している車の割合が \(94 \pm 4\%\) であることの信頼度が \(95\%\) だった。

裁判官は、この推定値の計算に高速道路を実際に利用する車の台数が含まれていないと指摘した。高速道路を利用する車の台数を考えに入れていないのに、\(3{,}125\) 台のサンプルだけで高い信頼度が得られることを彼は疑問に思った。

あなたが被告になったとして、ランダムにサンプルする必要がある車の台数が実際に高速道路を利用する車の台数に依存しないことをどのように説明するか？ 裁判官は数式を解釈する訓練を受けていないので、量的な議論ではなく直感的な説明が必要なことに注意せよ。

全組独立サンプリング定理 (定理 20.4.1) の証明では、全組独立な確率変数 \(R_{1}\), \(R_{2}\), \(\cdots\), \(R_{n}\) が全て同じ平均と分散を持つことが仮定された。

この定理には一般化が存在する: 全組独立な確率変数の平均と分散がそれぞれ異なっていたとしても、分散が定数で抑えられるなら同様の結果が示せる。

1. 一般化された全組独立サンプリング定理を証明せよ。

2. 次の系が成り立つと結論付けよ:

   系[一般化された大数の弱法則 (generalized weak law of large numbers)]

   任意の \(\varepsilon > 0\) に対して次の等式が成り立つ:

   \[ \lim_{n \to \infty} \operatorname{Pr} [\left| A_{n} - \mu_{n} \right| \leq \varepsilon] = 1 \]

\(G_{1}\), \(G_{2}\), \(\ldots\) を平均 \(\mu\) と有限の分散を持つ全組独立な確率変数の無限列とする。次のように \(f(n, \varepsilon)\) を定める:

このとき、大数の弱法則 (系 20.4.2) は次の形の論理式として表現できる:

ここで、\(\textbf{Q}_{0}\), \(\textbf{Q}_{1}\), \(\textbf{Q}_{2}\), \(\textbf{Q}_{3}\) は次に示す量化子のいずれかである:

ただし \(n\), \(n_{0}\) は非負整数の値を取り、\(\delta\), \(\varepsilon\) は非負実数の値を取ると解釈する。\(\textbf{Q}_{0}\), \(\textbf{Q}_{1}\), \(\textbf{Q}_{2}\), \(\textbf{Q}_{3}\) として適切な量化子を答えよ。

あなたは大統領の下で働いており、次の選挙で彼に投票する有権者の割合 \(p\) を推定することになった。この推定はランダムサンプリングを通して行われる。具体的には、ランダムに選んだ有権者に次の選挙で投票する候補者の名前を聞くことを \(n\) 回繰り返す。ランダムな有権者の選択は一様な確率で他の選択と独立した形で行われる。最後に、現職の大統領に投票すると答えた有権者の割合 \(P\) を \(p\) の推定値とする。

1. これまでに学んだサンプリングや確率分布に関する知識を使うと、確率変数 \(P\) が定数 \(p\) の近い値を取ることの信頼度を計算できる。この計算では、有権者および有権者の選び方に関する事実がいくつか利用される。次の文章の中で正しいものを全て選べ:

   1. 特定の有権者が与えられたとき、その有権者が「現職の大統領に投票する」と答える確率は \(p\) である。

   2. \(n\) を大きくしていくと、ある有権者がランダムサンプリングで複数回選択される確率は \(1\) に近づく。

   3. 有権者の人数を大きくしていくと、ある有権者がランダムサンプリングで複数回選択される確率は \(0\) に近づく。

   4. (\(n \geq 3\) なら) \(3\) 人目のサンプルは全ての有権者から等しい確率で選ばれる 。

   5. \(1\) 人目のサンプルが「現職の大統領に投票する」と答えた場合、\(2\) 人目のサンプルが「現職の大統領に投票する」と答える確率は \(p\) より高くなる。

   6. \(2\) 人目のサンプルが \(1\) 人目のサンプルと同じ州の出身という条件の下で、その \(2\) 人目のサンプルが「現職の大統領に投票する」と答える確率は \(p\) と等しくない可能性がある。

2. 確率論の知識を使って計算したところ、考えている \(n\) では次の不等式が成り立つと分かった:

   \[ \operatorname{Pr} [\left| P - p \right| \leq 0.04] \geq 0.95 \]

   また、実際にランダムサンプリングと質問を実行したところ、現職の大統領に投票すると答えた有権者の割合は \(0.53\) だった。以上の結果を大統領に伝えるとき、適当な表現を次の中から全て選べ:

   1. 大統領、\(p = 0.53\) です！

   2. 大統領、少なくとも \(95\%\) の確率で、\(p\) と \(0.53\) の差は \(0.04\) 以下です。

   3. 大統領、\(p\) と \(0.53\) の差が \(0.04\) 以下であるか、非常に奇妙な (\(100\) 回に \(5\) 回以下しか起きない) ことが起きたかのどちらかです。

   4. 大統領、\(p\) と \(0.53\) の差が \(0.04\) 以下であることに \(95\%\) の信頼を置くことができます。

先日、とある企業が大規模なプログラムを書き上げた。このプログラムを構成する行に含まれるバグを持つ行の割合 \(b\) を推定するため、QA チームは少数の行を一様ランダムかつ独立に選択した (このため、確率は低いものの同じ行が何度も選択される可能性はある)。そして選択した行のそれぞれに対してバグが含まれるかどうかをチェックし、バグを含む行の個数を選択された行の個数で割った値を \(b\) の推定値とした。

この企業には統計の専門家がいたので、彼は実際のバグを含む行の割合 \(b\) と上記の方法で求めた推定値の差が \(97\%\) の信頼度で \(0.006\) 以下になることを保証するために調べる必要があるプログラムの行数 \(s\) を二項分布の推定を利用して計算した。

数学的には、企業が書き上げたプログラムは既に終了した試行から得られた結果である。そしてランダムサンプルとはプログラムの \(s\) 行をランダムに選択するプロセスによって定義される確率変数である。統計の専門家が示した信頼度の正当化では、このプログラムとプロセスに関する性質が仮定されている。その性質の一部が次に示す文章の中に含まれている。性質を正しく説明した文章を全て選び、その理由を説明せよ。

1. プログラムの第 \(9\) 行がバグを含む確率は \(b\) である。

2. ランダムサンプルで \(9\) 番目に選択される行がバグを含む確率は \(b\) である。

3. ランダムサンプルで \(3\) 番目に選択される行は、プログラムの全ての行から等しい確率で選択される。

4. ランダムサンプルで \(1\) 番目に選択される行にバグが含まれるなら、\(2\) 番目に選択される行にバグが含まれる確率は \(b\) より高くなる。

5. プログラムの最後の行にバグが含まれるなら、最後から \(2\) 番目の行にバグが含まれる確率は \(b\) より高い。

6. 事象 [ランダムサンプルで最後に選択される行にバグが含まれる] に対応する指示確率変数の期待値は \(b\) である。

7. ランダムサンプルの最初の \(2\) 行が同種のコード ── 両方とも代入文、両方とも条件分岐文、両方ともループ文 \(\ldots\) ── なら、最初の行がバグを含む確率は \(b\) より高い。

8. ランダムサンプルに含まれる行が全て異なる確率は \(0\) である。

あるギャンブラーは毎日ドローポーカーを \(120\) 回、ブラックジャックを \(60\) 回、スタッドポーカーを \(20\) 回プレイする。彼がプレイするときドローポーカーの勝率は \(1/6\), ブラックジャックの勝率は \(1/2\), スタッドポーカーの勝率は \(1/5\) である。

1. このギャンブラーが一日に勝利する回数の期待値を求めよ。

2. Markov の定理 (定理 20.1.1) を使って、このギャンブラーが一日に \(108\) 回以上勝利する確率の上界を求めよ。

3. ギャンブルの結果が全組独立である (しかし相互独立ではない) と仮定する。ギャンブラーが一日に勝利する回数の分散を求めよ。解答は数値を表す式で構わない (完全に計算する必要はない)。

4. Chebyshev の定理 (定理 20.2.3) を使って、このギャンブラーが一日に \(108\) 回以上勝利する確率の上界を求めよ。解答は数値を表す式で構わない (完全に計算する必要はない)。

5. ギャンブルの結果が相互独立だと仮定する。このとき、このギャンブラーが一日に \(108\) 回以上勝利する確率の上界は \(\text{(d)}\) の解答よりずっと小さくなることを示せ。

   ヒント: \(e^{1-2 \ln 2} \leq 0.7\)

\(10\) 億個のスロットを持つハッシュテーブルに \(20\) 億個のレコードを保存することを考える。各レコードに対するスロットの割り当てが一様ランダムかつ独立に選択されると仮定すれば、各スロットには平均で \(2\) 個のレコードが割り当てられる。もちろん割り当てにはランダム性が絡むので、特定のスロットに \(2\) 個より多い個数のレコードが割り当てられる可能性はある。

1. 特定のスロットに \(24\) 個以上のレコードが割り当てられる確率は \(e^{-36}\) 以下だと示せ。

   ヒント: Chernoff 限界 (定理 20.5.1) を使う。\(\beta(c) ::= c \ln c - c + 1\) に対して \(\beta(12) > 18\) である。

2. いずれかのスロットに \(24\) 個以上のレコードが割り当てられる確率は \(e^{-15}\) 以下だと示せ。これは \(1/3{,}000{,}000\) 未満である。

   ヒント: \(\text{(a)}\) の結果と \(10^{9} < e^{21}\) を使う。

私は家を出るときに忘れ物をすることがある。例えば、履物に関しては次の等式が成り立つ:

1. 履き忘れる履物の個数を表す確率変数を \(X\) とする。\(\operatorname{Ex} [X]\) を求めよ。

2. 異なる履物を履き忘れる事象間の独立性を一切仮定できないとき、\(1\) 個以上の履物を履き忘れる確率の最良の上界を求めよ。

3. Markov の定理 (定理 20.1.1) を使って、\(3\) 個以上の履物を履き忘れる確率の上界を求めよ。

4. 私はそれぞれの履物を独立に履き忘れると仮定する。Chebyshev の定理 (定理 20.2.3) を使って、\(2\) 個以上の履物を履き忘れる確率の上界を求めよ。

5. Murphy の法則 (定理 20.5.4) を使って、\(1\) 個以上の履物を履き忘れる確率の下界を求めよ。

6. 私が身に着ける必要があるものは他にも多くある: 服、時計、バックパック、ノートパソコン、手帳、ボールペン、ティッシュ、身分証明書、鍵 \(\ldots\) も忘れてはいけない。私が忘れずに身に着ける物品の個数を表す確率変数を \(X\) とする。それぞれの物品を私が身に着ける事象は相互独立で、\(\operatorname{Ex} [X] = 36\) だと仮定する。Chernoff 限界 (定理 20.5.1) を使って、私が \(48\) 個以上の物品を身に着ける確率の上界を求めよ。

7. 私が \(108\) 個以上の物品を身に着ける確率の上界を求めよ。

Chernoff 限界 (定理 20.5.1) を使うと最近発生したサブプライム住宅ローンの崩壊を大まかに説明できる。最初に住宅ローンマーケットの基本的な用語を説明しておく。議論を簡単にするために簡略化した部分がある:

• ローン (loan) とは借り手に貸与される金銭を指す。借り手がローンを返せないとき、そのローンは「デフォルト (default) を起こした」と表現される。ローンがデフォルトを起こすと、担保が差し押さえられる。住宅ローンでは借り手の住宅が担保となる。

• ボンド (bond) とは複数のローンを集めて一つにした金融商品である。ボンドを順序付けて分割したものをトランシェ (tranche) と呼ぶ。例えば \(1000\) 個のローンからなるボンドを \(10\) 個のトランシェに分割した場合は、それぞれのトランシェが \(100\) 個のローンを含む。同じボンドから作られたトランシェには順序が付いており、デフォルトが起きると最も順位の低いトランシェから順に影響を受ける。例えばデフォルトが \(150\) 件起きると、まずトランシェ \(1\) で \(100\) 件のデフォルトが処理され、次にトランシェ \(2\) で \(50\) 件のデフォルトが処理される。

• 一つのボンドから作られたトランシェの中で最も順位の低いトランシェをメザニントランシェ (mezzanine tranche) と呼ぶ。

• トランシェからさらに「スーパーボンド」を作ることもできる。異なるボンドのメザニントランシェを集めた金融商品を債務担保証券 (collateralized debt obligation, CDO) と呼ぶ。このスーパーボンド自身もトランシェに分割でき、そのときは通常のトランシェと同様に損失を受ける順序が割り当てられる。

1. \(1000\) 個のローンが作られたボンドが \(10\) 個のトランシェに分割されている。それぞれのローンがデフォルトを起こす確率は \(5\%\) である。ローンのデフォルトが相互独立に発生すると仮定するとき、最後から \(2\) 番目のトランシェまでデフォルトが及ぶ確率の上界、そして最上位のトランシェまでデフォルトが及ぶ確率の上界を求めよ。

2. ローンの独立性を仮定しないとき、最後から \(2\) 番目のトランシェまでデフォルトが及ぶ確率の最良の上界、そして最上位のトランシェまでデフォルトが及ぶ確率の最良の上界を求めよ。解答した上界が最良だと示せ。

   ヒント: Markov の定理 (定理 20.1.1) を使う。

3. ローンが相互独立だと仮定できるとき、メザニントランシェに影響するデフォルトの発生件数の期待値を求めよ。

4. \(100\) 個のボンドからメザニントランシェを集めて CDO を作ったとする。この CDO に影響するデフォルトの発生件数の期待値を求めよ。

5. この CDO を \(10\) 個のトランシェに分割したとする。このとき、それぞれのトランシェには \(1000\) 個のローンが含まれる。デフォルトの相互独立性を仮定するとき、最上位のトランシェまでデフォルトが及ぶ確率を求めよ。また、上から \(3\) 番目のトランシェまでデフォルトが及ぶ確率を求めよ。

6. デフォルトの相互独立性を仮定せずに \(\text{(e)}\) と同じ質問に答えよ。

コインが \(2\) 枚ある: 一方は公平であり、もう一方は表が出る確率が \(3/4\) である。いずれかのコインを \(1\) 枚選び、それを \(n\) 回投げる。Chernoff 限界 (定理 20.5.1) を使って、どちらのコインが選択されたかを \(95\%\) の信頼度で識別するのに必要な \(n\) を求めよ。

Murphy の法則 (定理 20.5.4) には無限バージョンが存在する: 「期待値の和が無限大に発散する無限個の相互独立な事象があるとき、その中で有限個しか起きない確率は \(0\) である」が成り立つ。この結果は Borelボレル-Cantelliカンテリ の補題 (Borel-Cantelli lemma) と呼ばれる。

1. 相互独立な事象の無限列 \(A_{0}\), \(A_{1}\), \(\ldots\) が次の等式を満たすと仮定する:

   \[ \sum_{n \in \mathbb{N}} \operatorname{Pr} [A_{n}] = \infty \tag{20.28}\]

   このとき \(\operatorname{Pr} [\text{どの \(A_{n}\) も起きない}] = 0\) だと示せ。

   ヒント: \(B_{k}\) を事象 [全ての \(n \leq k\) に対して \(A_{n}\) が起きない] とする。事象 [どの \(A_{n}\) も起きない] を \(B\) とすれば、\(B\) は次の等式を満たす:

   \[ B = \bigcap_{k \in \mathbb{N}} B_{k} \]

   後は Murphy の法則 (定理 20.5.4) を使う。

2. \(\operatorname{Pr} [\text{有限個の \(A_{n}\) だけが起きる}] = 0\) だと結論付けよ。

   ヒント: \(C_{k}\) を事象 [\(n \geq k\) を満たす \(A_{n}\) が一つも起こらない] とする。事象 [有限個の \(A_{n}\) だけが起きる] を \(C\) とすれば、\(C\) は次の等式を満たす:

   \[ C = \bigcup_{k \in \mathbb{N}} C_{k} \]

   後は \(\text{(a)}\) の結果を \(C_{k}\) に適用する。