練習問題

公平なコインを独立に \(2n\) 回投げたときに表が出る回数を \(B\) とする。\(\operatorname{Pr}[B = n]\) と漸近等価な式を次の中から選べ:

1. \(\displaystyle \frac{1}{\sqrt{2n \pi}}\)
2. \(\displaystyle \frac{2}{\sqrt{n \pi}}\)
3. \(\displaystyle \frac{1}{\sqrt{n \pi}}\)
4. \(\displaystyle \sqrt{\frac{2}{n \pi}}\)

1. \(1\) 桁の非負整数を一様ランダムに独立して \(k\) 個選択するとき、\(0\) が選ばれない確率を求めよ。

2. 箱の中に \(90\) 個の良品ネジと \(10\) 個の不良品ネジが入っている。ランダムに取った \(10\) 個のネジに不良品が含まれない確率を求めよ。

3. 数列 \((1, 2, \ldots, n)\) の順番をランダムに変更したとき、つまり \(\left\{ 1, 2, \ldots, n \right\}\) の置換をランダムに選択したとき、\(i\) 番目の数字が \(k\) である確率を求めよ。

4. 公平なコインを \(n\) 回投げた結果を \(\texttt{T}\) または \(\texttt{H}\) が並ぶ長さ \(n\) の列で表したとき、全ての \(\texttt{T}\) が末尾に並ぶ確率を求めよ。\(\texttt{T}\) が含まれない列では、命題「全ての \(\texttt{T}\) が末尾に並ぶ」が空虚に成り立つ。

ニューヨークヤンキースとボストンレッドソックスが二本先取のシリーズで戦うことになった。つまり、両チームは一方が \(2\) 回勝利するまで試合を続け、\(2\) 回勝利したチームがシリーズの勝者となる。それぞれの試合におけるレッドソックスの勝率は常に \(3/5\) だと仮定する。

次の設問に四ステップ法を使って答えよ。設問ごとに樹形図を書き直す必要はない。

1. \(3\) 回の試合でシリーズが終了する確率を求めよ。

2. シリーズの勝者が最初の試合で敗北する確率を求めよ。

3. 「確率的に正しい」チームがシリーズの勝者となる確率を求めよ。

コインを \(2\) 回投げて、二人のプレイヤーから勝者を決めるとする。もし \(1\) 回目の結果が表で \(2\) 回目の結果が裏なら、一人目のプレイヤーの勝利となる。もし \(1\) 回目の結果が裏で \(2\) 回目の結果が表なら、二人目のプレイヤーの勝利となる。これ以外の場合、つまり両方とも表または両方とも裏の場合は、同じ処理をコインを \(2\) 回投げるところからやり直す。

コインを投げたとき表が出る確率が (それまでの結果に関係なく) 常に \(p\) だと仮定する。四ステップ法を使って、一人目のプレイヤーが勝利する確率を求めよ。誰も勝利しない確率はどうなるか？

ヒント: 標本空間は無限集合なので、樹形図を完全に書くことはできない。パターンが分かるまで書けばよい。一人目のプレイヤーが勝利する結果の確率の和を直接求めるのは難しいものの、この問題 ── そして無限標本空間が関係する多くの問題 ── で利用できる素晴らしいテクニックがある: 樹形図全体に含まれる注目している結果の確率の和を \(s\) とする。そうしたとき、特定の部分木に含まれる注目している結果の確率の和を \(s\) の関数として表現できることがある。もしこれが可能なら \(s\) に関する方程式が手に入るので、それを解けば \(s\) が求まる。

ドアが \(4\) 個ある Monty Hall 問題で何が起こるかを考えよう。まず、賞品がいずれかのドアの後ろに隠される。それからプレイヤーが \(1\) 個のドアを選ぶ。続いて、プレイヤーが選択しておらず、かつ賞品が隠されていないのドアを司会者が \(1\) 個選んで開ける。その後プレイヤーにはドアの選択を自身が選択しておらず司会者が開けてもいない \(2\) 個のドアのいずれかに変更する権利が与えられる。プレイヤーの勝利条件は賞品が隠されたドアを選ぶことである。

ドアが \(3\) 個の場合と同様の次の仮定を置く:

• 賞品が隠されるドアは \(4\) 個のドアの中から等しい確率で選択される。

• プレイヤーは最初 \(4\) 個のドアの中から等しい確率でドアを選ぶ。

• 司会者は開けられるドア (プレイヤーが選択しておらず、かつ賞品が隠されていないドア) の中から等しい確率で開けるドアを選ぶ。

四ステップ法を使って次の設問に答えよ。樹形図が大きくなりすぎる場合は全体の構造が分かる分だけ書けば十分である。

1. ニュージャージー州トレントンから参加した衛生技師 Stuスチュー はドアの選択を絶対に変更しない。Stu が賞品を獲得できる確率を求めよ。

2. モンタナ州ヘレナから参加したエイリアンによる拉致行為研究家 Zeldaゼルダ はドアの選択を必ず変更し、そのとき選択可能な \(2\) 個のドアの中から等しい確率で新しいドアを選択する。Zelda が賞品を獲得できる確率を求めよ。

司会者がドアを選ぶ方法に関する仮定を変更してみよう。ドアに \(A\), \(B\), \(C\), \(D\) と名前が付いていて、Carolキャロル (司会者) は必ず開けられるドアの中で最も左のドア、つまりプレイヤーが選択しておらず賞品が隠されてもいないドアの名前をアルファベット順で並べたとき先頭にある名前のドアを開けると仮定する。

この仮定があるとき、マサチューセッツ州ケンブリッジから参加した工学部の学生 Mergatroidマーガトロイド は賞品の位置に関する情報を少しだけ多く手にできる。Mergatroid は必ずドアの選択を変更し、そのとき選択可能な \(2\) 個のドアの中で最も左にあるものを選択する。

3. Mergatroid が賞品を獲得できる確率を求めよ。

この世界には不死の戦士が全部で \(n\) 人いる。しかし、不死の戦士は一人でいい。不死の戦士たちの当初の計画は「全員で世界をさまよい、ドラマチックな舞台を見つけたら古代の剣を使った決闘で一人を消滅させる。これを最後の一人になるまで数世紀繰り返す」というものだった。しかし、確率に関する啓蒙的な議論の後、彼らは次のプロトコルを試してみることにした:

1. 投げたとき確率 \(p\) で表が出るコインを鋳造する。

2. それぞれの戦士がそのコインを一回ずつ投げる。

3. 表が出た戦士がちょうど \(1\) 人なら、その戦士を「選ばれし者」とする。そうでなければ、このプロトコルは失敗となる。戦士たちは平和な解決を諦め、古代の剣を使った決闘の旅に出る。

ある戦士 (ロシアの草原地帯出身の Kurganクルガン) は、このプロトコルが成功する確率は \(n\) が大きくなるとき \(0\) に向かうと指摘した。これに対して別の戦士 (スコットランドの山岳地帯highland出身の McLeodマクラウド) は、\(p\) を注意深く選べばそうはならないと主張した。

1. この問題をモデル化する上で自然な標本空間は、\(\texttt{H}\) または \(\texttt{T}\) が並んだ長さ \(n\) の列全体の集合 \(\left\{ \texttt{H}, \texttt{T} \right\}^{n}\) である: 列の第 \(i\) 要素が \(i\) 人目の戦士によるコイン投げの結果を表す。樹形図のアプローチを使って、それぞれの結果に割り当てられる確率が結果に含まれる \(\texttt{H}\) の個数 \(h\) と \(p\), \(n\) だけに依存することを説明せよ。

2. 上記のプロトコルが成功する確率を \(p\) と \(n\) を使って表せ。

3. 上記のプロトコルが成功する確率を最大化したいとき、コインの表が出る確率 \(p\) に設定すべき値を求めよ。

4. \(p\) が \(\text{(c)}\) で回答した値であるとき、プロトコルの成功確率を求めよ。不死の戦士の人数 \(n\) が無限大に向かうとき、成功確率はどんな値に向かうか？

\(52\) 枚のカードからなる通常のトランプデッキには、赤いカードと黒いカードが \(26\) 枚ずつ含まれる。デッキをシャッフルして、机の上に裏返しに (どのカードが一番上にあるか分からないように) して置いたとする。あなたはデッキの一番上のカードを「テイク」または「スキップ」できる。「テイク」するとゲームは終了し、一番上のカードが黒い場合はあなたの勝ち、赤い場合はあなたの負けとなる。「スキップ」した場合は一番上のカードをデッキから取り除いて机の上に表向きに置き、それから再度「テイク」または「スキップ」を行う。カードが残り \(1\) 枚になったときは、あなたはそのカードを「テイク」しなければならない。最初に「テイク」するより優れた ── 勝率が \(1/2\) を上回る ── 戦略が存在しないことを示せ。

ヒント: 数学的帰納法を使って、より一般的な命題「赤いカードと青いカード (枚数が半々とは限らない) からなる \(n\) 枚のデッキをシャッフルして同じゲームを行うとき、最初に「テイク」するより優れた戦略は存在しない」を示す。

あるシステムは \(n\) 個のコンポーネントから構成され、過去の運用実績からは任意のコンポーネントが一年間に障害を起こす確率が \(p\) だと分かっている、言い換えれば、特定の一年間に \(i\) 番目のコンポーネントが障害を起こす事象を \(F_{i}\) (\(1 \leq i \leq n\)) とするとき、次の等式が成り立つ:

コンポーネントが一つでも障害が起こすとシステム全体で障害が発生する。特定の一年間にシステム全体が障害を起こす確率について何が言えるだろうか？

システム全体が障害を起こす事象を \(F\) とする。\(\operatorname{Pr}[F]\) の正確な値は仮定を増やさなければ分からないものの、その有用な上界と下界は求められる。具体的には、次の関係が成り立つ:

以降では \(p < 1/n\) を仮定する (この仮定が成立しないとき上界は自明となる)。例えば \(n = 100\) と \(p = 10^{-5}\) なら、一年間に障害が起こる頻度は最大でも \(1000\) 回に \(1\) 回であり、最低でも \(100{,}000\) 回に \(1\) 回だと分かる。

この上記の状況を次のようにモデル化する: 標本空間を \(S ::= \operatorname{pow}([1..n])\) とする。結果 \(s \in \mathcal{S}\) は \(n\) 以下の正整数からなる集合であり、\(s\) の各要素は一年間に障害を起こすコンポーネントにちょうど対応する。例えば、結果 \(\left\{ 2, 5 \right\}\) は一年間に \(2\) 番目と \(5\) 番目のコンポーネントが障害を起こし、それ以外のコンポーネントは障害を起こさない状況を意味する。また、システムが障害を起こさない状況は空集合 \(\varnothing\) によって表現される。

1. 結果に対する適切な確率の割り当てを説明し、\(p\) がシステムが障害を起こす確率の下界だと示せ。解答する確率の割り当てにおいて、結果の確率の和が \(1\) だと示すこと。

2. 結果に対する適切な確率の割り当てを説明し、\(np\) がシステムが障害を起こす確率の上界だと示せ。解答する確率の割り当てにおいて、結果の確率の和が \(1\) だと示すこと。

3. 不等式 \(\text{(17.10)}\) を示せ。

確率に関する便利な法則を次にいくつか示す。これらはどれも確率に関する加算則 (規則 17.5.3) から導かれる。証明せよ:

和集合上界則 (union bound) と呼ばれる次の不等式を証明せよ:

ヒント: \(A_{1}\), \(A_{2}\), \(\ldots\), \(A_{n}\), \(\ldots\) を排反な事象に置き換え、加算則 (規則 17.5.3) を適用する。

全てのプレイヤーが自身を除く全員と一度ずつ対戦する方式を総当たり戦 (round-robin tournament) と呼ぶ。それぞれの試合で勝敗が決定する (引き分けが起こらない) とき、総当たり戦の結果は任意の二頂点間にちょうど \(1\) 個の有向辺が存在するトーナメント有向グラフ (tournament digraph) でモデル化できる。以降の議論では「頂点」と「辺」ではなく「プレイヤー」と「勝利する」の言葉を使う。

正整数 \(n\) と \(k \in [0,n)\) に対して、\(n\) 人の総当たり戦の結果が \(k\)-中立 (\(k\)-neutral) とは、\(k\) 人のプレイヤーの集合 \(P\) を任意に取ったとき、\(P\) に属する全員に勝利するような \(P\) に属さないプレイヤーが常に存在することを意味する。例えば、総当たり戦の結果が \(1\)-中立とは、自分以外の全員に勝利する「最強の」プレイヤーが存在しないことを意味する。

この問題では、命題「\(k\) を任意に固定したとき、\(n\) が十分大きければ \(n\) 人の総当たり戦の結果であって \(k\)-中立であるものが存在する」を示す。\(n\) を任意に固定し、\(n\) 個の頂点のそれぞれの組を結ぶ両方向の辺に等しい確率を割り当てることで、\(n\) 頂点のトーナメント有向グラフのそれぞれに確率を割り当てたとする。

1. \(k\) 人のプレイヤーからなる任意の集合 \(S\) に対して、\(S\) に属するプレイヤー全員に勝利するプレイヤーが存在しない事象を \(B_{S}\) とする。\(n\) と \(k\) を使って \(\operatorname{Pr}[B_{S}]\) を表せ。

2. トーナメント有向グラフが \(k\)-中立でない事象を \(Q_{k}\) とする。次の不等式を示せ:

   \[ \operatorname{Pr}[Q_{k}] \leq \binom{n}{k}\alpha^{n-k} \]

   ここで \(\displaystyle \alpha ::= 1 - \left( \frac{1}{2} \right)^{\! k} \) である。

   ヒント: 次の関係と Boole の不等式を利用する:

   \[ Q_{k} = \bigcup_{S} B_{S} \]

   ここで \(S\) はプレイヤーからなる \(k\) 要素集合を意味する。

3. \(n\) が (\(k\) と比べて) 十分大きいなら \(\operatorname{Pr}[Q_{k}] < 1\) だと結論付けよ。

4. \(\text{(c)}\) の結果から、命題「\(k\) を任意に固定したとき、\(n\) が十分大きければ \(n\) 人の総当たり戦の結果であって \(k\)-中立であるものが存在する」の成立が言える理由を説明せよ。

コインを何回も投げ、連続する \(3\) 回のコイン投げの結果が「表・表・裏」または「裏・裏・表」になったら終了する試行を考える。この試行が「表・表・裏」で終わる確率を求めよ。適切な確率空間を定義して操作をモデル化し、それを使って解答を説明せよ。

ヒント: 表と裏の対称性を利用する。