練習問題

\(A\), \(B\) を事象、\(I_{A}\), \(I_{B}\) をそれぞれ \(A\), \(B\) に対応する指示確率変数とする。「\(I_{A}\) と \(I_{B}\) は独立」と「\(A\) と \(B\) は独立」が同値だと示せ。

ヒント: \(A^{1} ::= A\), \(\,A^{0} ::= \overline{\mathstrut A}\) と定めると、\(c \in \left\{ 0, 1 \right\}\) に対して事象 [\(I_{A} = c\)] が \(A^{c}\) に等しくなる。\(B^{1}\), \(B^{0}\) に対しても同様にする。

\(R\), \(S\), \(T\) を終域が有限集合 \(V\) の確率変数とする。

1. \(R\) が一様だと仮定する。つまり、全ての \(b \in V\) に対して次の等式が成り立つとする:

   \[ \operatorname{Pr} [R = b] = \frac{1}{|V|} \]

   さらに、\(R\) は \(S\) と独立だと仮定する。次の議論を読んでみてほしい:

   \(R = S\) となる確率は、\(S\) が取ったのと同じ値を \(R\) が取る確率に等しい。よって次の等式が成り立つ:

   \[ \operatorname{Pr} [R = S] = \frac{1}{|V|} \tag{19.17}\]

   この議論にあなたは納得しただろうか？ 等式 \(\text{(19.17)}\) の注意深い証明を示せ。

   ヒント: 事象 [\(R = S\)] は次のように排反な事象に分割できる:

   \[ [R=S] = \bigcup_{b \in V} [R = b \ \operatorname{\text{\footnotesize AND}} \ S = b] \]

2. \(S \times T\) を \(S\) と \(T\) の値の組を表す確率変数とする¹。\(R\) は一様確率変数で、\(R\) は \(S \times T\) と独立だと仮定する。次の議論はどうだろうか？

   \(R = S\) となる確率は、\(S \times T\) の値の第一要素と同じ値を \(R\) が取る確率に等しい。独立性より、この確率は \(1/|V|\) で変わらない。よって事象 \([R = S]\) は事象 \([S = T]\) と独立である。

   事象 \([R = S]\) が事象 \([S = T]\) と独立だと示す注意深い証明を示せ。

3. \(V = \left\{ 1,2,3 \right\}\) であり、\((R, S, T)\) の値は次の三つ組を等しい確率で取ると仮定する:

   \[ (1, 1, 1),\ (2, 1, 1),\ (1, 2, 3),\ (2, 2, 3),\ (1, 3, 2),\ (2, 3, 2) \]

   次の事実を検証せよ:

   • \(R\) は \(S \times T\) と独立である。

   • 事象 [\(R = S\)] は事象 [\(S = T\)] と独立でない。

   • \(S\) と \(T\) は一様確率変数である。

\(R\), \(S\), \(T\) を相互独立な指示確率変数とする。

一般に事象 [\(S = T\)] は事象 [\(R = S\)] と独立でない。この事実は次のように説明できる: \(S\) が一様だと仮定する。このとき \(S\) は \(0\) と \(1\) を同じ確率で取るので、\(S\) と \(R\) が等しい確率は \(S\) と \(R\) が等しくない確率と同じになる。つまり \(\operatorname{Pr}[R = S] = 1/2\) である。同様に \(\operatorname{Pr}[S = T] = 1/2\) も分かる。

加えて \(R\) と \(T\) はどちらも \(1\) を取る確率が \(0\) を取る確率より高いと仮定する。すると、\(R = S\) だと分かっているなら \(S = 1\) の可能性が高い。さらに、\(S = 1\) の可能性が高いと分かれば \(S = T\) の可能性が高いとも分かる。つまり \(R = S\) なら \(S = T\) の可能性が高い。言い換えれば \(\operatorname{Pr}[S = T \, | \, R = S] > 1/2\) が成り立つ。

では、次の補題を厳密に (直感的な議論を使わずに) 示せ:

\(R\), \(S\), \(T\) が同じ確率空間上の相互独立な確率変数で、どれも集合 \(\left\{ 1, 2, 3 \right\}\) 上の一様分布に従うとする。\(M = \max \left\{ R, S, T \right\}\) としたとき、\(M\) の確率密度関数 \(\operatorname{PDF}_{M}\) の値を計算せよ。

第 19.3.3 項で示した解析によれば、上記の「大きい数当てゲーム」ではチーム \(2\) に勝率 \(4/7\) の戦略が存在する。これより優れた戦略は存在するだろうか？ 答えは「No」である。なぜなら、チーム \(1\) に \(3/7\) の勝率が保証される戦略が存在するからである。その戦略を示し、\(3/7\) の勝率が保証される理由を説明せよ。

確率 \(p\) で表を向く公平でないコインがある。このコインを \(n\) 回独立に投げたとき、表を向く回数を表す確率変数を \(J\) とする。このとき \(J\) は一般二項分布に従う:

ここで \(q ::= 1 - p\) である。

1. 次の命題を示せ:

   • \(\operatorname{PDF}_{J} (k - 1) < \operatorname{PDF}_{J}(k) \quad (k < np + p \text{ のとき})\)
   • \(\operatorname{PDF}_{J} (k - 1) > \operatorname{PDF}_{J}(k) \quad (k > np + p \text{ のとき})\)

2. \(\operatorname{PDF}_{J}\) の最大値は次の値と漸近等価だと示せ:

   \[ \frac{1}{\sqrt{2 \pi npq}} \]

   ヒント: 漸近的な評価をする上では \(np\) が整数だと仮定しても問題ない。このとき \(\text{(a)}\) より最大値は \(\operatorname{PDF}_{J}(np)\) だと分かる。Stirling の公式 (定理 14.5.1) を使う。

\(R_{1}\), \(R_{2}\), \(\ldots\), \(R_{m}\) が相互独立な確率変数で、どれも \([1..n]\) 上の一様分布に従うとする。\(M ::= \max \left\{ R_{i} \; | \; i \in [1..m] \right\}\) と定める。

1. \(\operatorname{PDF}_{M}(1)\) を表す式を書け。

2. さらに一般化した、\(\operatorname{Pr}[M \leq k]\) を表す式を書け。

3. \(k \in [1..n]\) に対する \(\operatorname{PDF}_{M}(k)\) を表す式を書け。\(j \in [1..n]\) に対する \(\operatorname{Pr}[M \leq j]\) を使ってよい。

カフェインを過剰摂取した船乗り Techテック Hinghyディンギー が海沿いの歩道を歩いている。この船乗りは一歩進むごとに \(1\) 単位だけ左または右に移動する。左に進む確率と右に進む確率は等しいとする。

船乗りが最初にいる地点を位置 \(0\) として、右方向に \(1\), \(2\), \(\ldots\) と \(1\) 単位ごとにラベルを付け、左方向に \(-1\), \(-2\), \(\ldots\) と \(1\) 単位ごとにラベルを付けたとする。船乗りが \(t\) 歩進んだときの水平位置を表す確率変数を \(L_{t}\) とする。例えば、船乗りが最初にいる地点は位置 \(0\) なので、次の関係が分かる:

ここから \(1\) 歩進むと、船乗りは位置 \(-1\) または \(1\) に等しい確率で移動する。つまり次の関係が成り立つ:

1. 次の表を埋めることで、\(t = 2, 3, 4\) に対する \(\operatorname{PDF}_{L_{t}}\) の値を示せ。空欄は \(0\) を表す。同じ行にある値には同じ分母を持つ分数を答えること。

   \[ \def\arraystretch{1.2}\begin{array}{c|ccccccccc} & -4 & -3 & -2 & -1 & \,0\, & \hphantom{-}1 & \hphantom{-}2 & \hphantom{-}3 & \hphantom{-}4 \\ \hline \hline t = 0 & & & & & 1 & & & & \\ t = 1 & & & & 1/2 & 0 & 1/2 & & & \\ t = 2 & & & ? & ? & ? & ? & ? & & \\ t = 3 & & ? & ? & ? & ? & ? & ? & ? & \\ t = 4 & ? & ? & ? & ? & ? & ? & ? & ? & ? \end{array} \]

2. Sailingセーリング Pavilionパビリオン (MIT が所有するセーリング施設) のスタッフを助けるために、次の質問に答えよ。解答の導出と、それが正しい理由の説明を示すこと。

   1. \(t\) 歩だけ進んだ船乗りが右方向にちょうど \(i\) 回だけ動いているとき、その船乗りの現在位置はどこか？

   2. その位置に至る \(t\) 歩の動き方は何通りあるか？

   3. その位置に船乗りが至る確率を求めよ。

   4. \(B_{t} ::= (L_{t} + t)/2\) が不偏二項分布に従うと示せ。

Bruleブルール Ceeシー が出演した未公開の映画には、\(5\) 枚の木板を素手で割るシーンがある。撮影当時、彼が \(1\) 枚の木版を割れる確率は \(0.8\) だった ── \(1\) でないのは左手を使うためである。それぞれの木板に対する確率は独立だと仮定する。また、Brule が木板を割るのに失敗した場合でも撮影は中断されず、Brule は常に \(5\) 枚全ての木板に手を出すと仮定する。

1. Brule が \(5\) 枚中ちょうど \(2\) 枚の木板を割る確率を求めよ。

2. Brule が \(5\) 枚中 \(3\) 枚以下の木板を割る確率を求めよ。

3. Brule が撮影を成功させるまでに割る木板の枚数の期待値を求めよ。

カリフォルニア州からアラバマ州に学校関係者が異動するニュースついて、ある新聞は「これで両方の州で平均 IQ が上昇するだろう」という冷淡なコメントを掲載した。どういうことか説明せよ。

サイコロを使った次のゲームを考えよう。公平な六面サイコロを \(3\) 回振り、\(6\) の目が出た回数が:

• ちょうど \(0\) 回なら、\(1\) ドルを失う。

• ちょうど \(1\) 回なら、\(1\) ドルを獲得する。

• ちょうど \(2\) 回なら、\(2\) ドルを獲得する。

• ちょうど \(3\) 回なら、\(k\) ドルを獲得する。

このゲーム²を公平にしたいとき、\(k\) はいくつに設定するべきか？

1. 公平なコインを何度も投げ、裏が \(2\) 回連続で出たら投げるのを止める試行を考える。この試行でコインが投げられる回数を表す確率変数を \(N_{\texttt{TT}}\) とする。\(\operatorname{Ex} [N_{\texttt{TT}}]\) を求めよ。

   ヒント: この試行の樹形図 \(D\) が図 \(\text{19.8}\) のように表せることを説明する。全期待値の法則 (定理 19.4.6) を利用する。

2. 「裏・表」がこの順番で出るまでコインを投げ続けるとき、コインが投げられる回数を表す確率変数を \(N_{\texttt{TH}}\) とする。\(\operatorname{Ex}[N_{\texttt{TH}}]\) を求めよ。

3. 次のゲームを考える: \(\texttt{TT}\) または \(\texttt{TH}\) が連続して出るまでコインを投げ続け、\(\texttt{TT}\) が最初に出た場合は勝利、\(\texttt{TH}\) が最初に出た場合は敗北 (相手の勝利) となる。あなたは \(\operatorname{Ex}[N_{\texttt{TT}}]\) が \(\operatorname{Ex}[N_{\texttt{TH}}]\) より \(50\%\) 大きい事実を相手に伝え、相手が有利だと納得させた。そして、あなたは「もし自分が負けたら \(\$5\) 支払い、自分が勝ったら \(20\%\) 多く ── つまり \(\$6\) ── もらう」というルールを設定した。

   このとき、あなたは相手の未熟な直感を利用して不公平なオッズを受け入れさせている。このゲームの期待収益を求めよ。

Benベン Bitdiddleビットディドル は表が出るまで公平なコインを投げ続けるゲームを解析するよう頼まれた。そのゲームでは、奇数回目のコイン投げで初めて表が出た場合は \(\$2^{n}/n\) を獲得でき、偶数回目のコイン投げで初めて表が出た場合は \(\$2^{n}/n\) を失う。Ben は期待収益を次のように計算した:

これは交代調和級数 (alternating harmonic series) と呼ばれ、実数 \(r > 0\) に収束することが知られている。\(r > 0\) なので、Ben はこのゲームをプレイすることが得だと結論付けた。しかし、いつものごとく軽はずみな Ben の解析は間違っている。どこが間違っているか説明せよ。

正整数の値を取る確率変数 \(T\) が次の関係を満たすという:

ここで \(a\) は次のように定義される:

1. \(\operatorname{Ex} [T]\) が無限大だと示せ。

2. \(\operatorname{Ex} [\sqrt{T}]\) が有限だと示せ。

全てのプレイヤーが自身を除く全員と一度ずつ対戦する方式を総当たり戦 (round-robin tournament) と呼ぶ。それぞれの試合で勝者と敗者が必ず決まるとき、総当たり戦の結果は任意の二頂点間にちょうど \(1\) 個の有向辺が存在するトーナメント有向グラフ (tournament digraph) でモデル化できる。総当たり戦で \(x\) が \(y\) に勝利したとき、かつそのときに限って、対応するトーナメント有向グラフには有向辺 \(\langle x \to y \rangle\) が存在する。

トーナメント有向グラフのランキング (ranking) とは、全ての頂点を含む路を意味する。任意のトーナメント有向グラフは一つ以上のランキングを持つ³。

任意の対戦で両プレイヤーの勝率は等しく、結果は相互独立と仮定し、トーナメント有向グラフをランダムに構築することを考える。\(10\) 頂点のトーナメント有向グラフが持つランキングの個数の期待値を表す式を求めよ。さらに、\(7000\) 個以上のランキングを持つ \(10\) 頂点のトーナメント有向グラフが存在すると結論付けよ。

この問題は確率的手法 (probabilistic method) の例である。確率的手法を使うと、特定のオブジェクトの存在を実際に構築することなく証明できる。

確率 \(p\) で表を向き、確率 \(q ::= 1 - p\) で裏を向くコインを \(3\) 回連続で表が出るまで投げ続ける試行を考える。この試行を表す樹形図 \(D\) を図 \(\text{19.9}\) に示す。

\(D\) の部分木 \(S\) の根に対応する状況から始まるコイン投げの回数の期待値を \(e(S)\) とする。\(e(D)\) を求めるために利用できる \(e(D)\), \(e(B)\), \(e(C)\) に関する小規模な連立方程式を答えよ。連立方程式を解く必要はない。

確率 \(p\) で表を向き、確率 \(q ::= 1 - p\) で裏を向くコインを \(2\) 回連続で同じ結果が出るまで投げ続ける試行を考える。つまり、この試行はコイン投げの結果が \(\texttt{HH}\) または \(\texttt{TT}\) になったら終了する。この試行を表す樹形図 \(A\) を図 \(\text{19.10}\) に示す。

\(A\) の部分木 \(T\) の根に対応する状況から始まるコイン投げの回数の期待値を \(e(T)\) とする。\(e(A)\) を求めるために利用できる \(e(A)\), \(e(B)\), \(e(C)\) に関する小規模な連立方程式を答えよ。連立方程式を解く必要はない。

\(n\) 個の異なるランダムな実数からなるベクトルが与えられる。これらの最大値を求める次の手続きを考える:

現在の最大値が更新される回数の期待値を求めよ。

ヒント: 事象 [ベクトルの第 \(i\) 要素が、それより前にある任意の要素より大きい] に対応する指示確率変数を \(X_{i}\) とする。

公平な六面サイコロを \(6\) の目が出るまで振り続ける試行を考える。様々な条件の下で、サイコロが降られる回数の期待値を求めよう。

この試行の自然な標本空間 \(\mathcal{S}\) は \(1\) 以上 \(5\) 以下の整数を並べた有限文字列の末尾に \(6\) を付けた文字列全体の集合であり、これは \(\mathcal{S} ::= [1..5]^{\ast} 6\) と表せる。このとき任意の結果 \(s \in \mathcal{S}\) に対して \(\operatorname{Pr}[s] = (1/6)^{|s|}\) が成り立つ。\(6\) が出るまでにサイコロが振られる回数を表す確率変数を \(T\) とする。つまり \(T(s)\) は \(s\) の長さ \(|s|\) に等しい。

1. サイコロが降られる回数の期待値 \(\operatorname{Ex} [T]\) を求めよ。

\(V\) を事象 [サイコロの目が全て偶数である] とする。言い換えれば \(V = \left\{ 2, 4 \right\}^{\ast}6\) であり、\(V\) には \(2\) または \(4\) だけが連続して出て、最後に初めて \(6\) が出る結果が含まれる。

2. \(\operatorname{Pr}[V] = 1/4 \) だと示せ。

   ヒント: \(V = 2V \cup 4V \cup \left\{ 6 \right\}\)

3. 偶数の目だけが出るという条件の下でサイコロが振られる回数の期待値 \(\operatorname{Ex}[T \, | \, V]\) を、\(s \in V\) に関する和として表す期待値の定義に従って計算せよ。

4. 偶数の目だけが出るとき、可能な目は \(2\), \(4\), \(6\) のみである。よって \(2\), \(4\), \(6\) を二つずつ目に持ったサイコロを振る試行を考えても問題ない。「障害までの平均ステップ数 (幾何分布の性質)」より、初めて \(6\) が出るまでにサイコロが振られる回数の期待値は \(1/(1/3) = 3\) と分かる。つまり \(\operatorname{Ex}[T \, | \, V] = 3\) であり、\(\text{(c)}\) の結果と矛盾する！ 何が間違っているか説明せよ⁴。

確率 \(p\) (\(0 < p < 1\)) で表が出る公平でないコインがある。このコインを表が出るまで投げ続ける試行を考える。この試行を最初に一度行う。その後、第 19.6 節の例と同様に、最初の試行で裏が連続して出た回数より \(10\) だけ小さい回数だけ裏が連続して出るまで試行を繰り返すとする。言い換えれば、初回の試行で \(k\) 回連続で裏が出たなら、\(\operatorname{max} \{k - 10, 0\}\) 回だけ裏が連続で出るまで「表が出るまでコインを投げ続ける」試行を繰り返す。

1. 必要な回数だけ裏が連続して出て全体の試行が終了するまでにコイン投げで表が出る回数 (試行が繰り返される回数) を表す確率変数を \(H\) とする。\(H\) の期待値が無限大だと示せ。

2. \(r < 1\) を正の実数とする。最初の試行で裏が連続で出た回数が \(k\) のとき、全体の試行を終えるには裏が連続して出る回数が \(k - 10\) ではなく \(rk\) になる必要があるとする。こうした場合は表が出るコイン投げの回数の期待値が有限だと示せ。

正整数 \(K\) をランダムに生成する手続きがある。この手続きを複数回使ったときに生成される値は相互独立である。この手続きで整数を一つ生成して \(x\) として、その後 \(x\) 以上の整数が得られるまで同じ手続きで何度も整数を生成し続ける試行を考える。この試行において、初回の \(x\) の後に生成される整数の個数を表す確率変数を \(R\) とする。

1. \(\operatorname{Pr}[K \geq k]\) を使った閉形式の単純な式で \(\operatorname{Ex} [R \; | \; K = k]\) を表し、それが正しい理由を簡単に説明せよ。

\(\operatorname{Pr}[K = k] = \Theta(k^{-4})\) だと仮定する。

2. \(\operatorname{Pr}[K \geq k] = \Theta(k^{-3})\) だと示せ。

3. \(\operatorname{Ex}[R]\) が無限大だと示せ。

MIT の学生は宿題の問題が解けるまで洗濯を後回しにすることがある。この問題で言及される確率変数は全て相互独立だと仮定する。

1. ある忙しいbusy学生は、洗濯を始める前に宿題を \(3\) 問を解かなければならない。それぞれの問題が \(1\) 日で解ける確率は \(2/3\) であり、\(2\) 日で解ける確率は \(1/3\) である。この忙しい学生が洗濯を先延ばしにする日数を表す確率変数を \(B\) とする。\(\operatorname{Ex}[B]\) を求めよ。

   例えば、最初の問題を解くのに \(1\) 日かかり、\(2\) 問目と \(3\) 問目を解くのにそれぞれ \(2\) 日かかるなら \(B = 5\) である。

2. ある気楽relaxedな学生は、朝に公平な六面サイコロを振り、\(1\) の目が出たなら洗濯をすぐに (\(0\) 日の先延ばしで) 行う。それ以外の場合は、その日は洗濯をせずに次の日の朝また同じことを繰り返す。この気楽な学生が洗濯を先延ばしにする日数を表す確率変数を \(R\) とする。\(\operatorname{Ex}[R]\) を求めよ。

   例えば、サイコロを振って出た目が初日から順に \(2\), \(5\), \(1\) なら、\(R = 2\) である。

3. ある不運unluckyな学生は病気にかかっており、\(2\) 個の公平な六面サイコロを振って出た目の積と同じ日数だけ静養する必要がある。この不運な学生が洗濯を先延ばしにする日数を表す確率変数を \(U\) とする。\(\operatorname{Ex}[U]\) を求めよ。

   例えば、\(2\) 個のサイコロの目が \(5\) と \(3\) なら \(U = 15\) である。

4. ある学生は確率 \(1/2\) で忙しく、確率 \(1/3\) で気楽であり、確率 \(1/6\) で不運だという。この学生が洗濯を先延ばしにする日数を表す確率変数を \(D\) とする。\(\operatorname{Ex}[D]\) を求めよ。

「情報科学のための数学」の講義の期末試験では、次の厳密な手続きによって成績が付けられる:

• 答案は確率 \(4/7\) で TA によって採点され、確率 \(2/7\) で教員によって採点され、確率 \(1/7\) でラジエーターの裏に落とされて無条件に \(84\) 点が付けられる。

• TA は答案の問題をそれぞれ採点し、その和を点数とする:

  • 配点が \(2\) 点の二択問題が \(10\) 問ある。それぞれについて、確率 \(3/4\) で満点が与えられ、確率 \(1/4\) で \(0\) 点が与えられる。

  • 配点が \(15\) 点の問題が \(4\) 問ある。それぞれについて、\(2\) 個の公平な六面サイコロを振って出た目の和に \(3\) を加えた点数が与えられる。

  • 配点が \(20\) 点の問題が \(1\) 問ある。この問題に対しては \(12\) 点または \(18\) 点が等しい確率で与えられる。

• 教員は公平な六面サイコロを \(2\) 回投げ、出た目の積に次の「印象点」を加えたものを点数とする:

  • 確率 \(4/10\) で印象点は \(40\) である。

  • 確率 \(3/10\) で印象点は \(50\) である。

  • 確率 \(3/10\) で印象点は \(60\) である。

この採点プロセスに含まれるランダムな選択は相互独立だと仮定する。

1. TA が採点する答案の点数の期待値を求めよ。

2. 教員が採点する答案の点数の期待値を求めよ。

3. この期末試験の答案の点数の期待値を求めよ。

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

男女の組が横方向または縦方向に並ぶとき、その組をフラーテーション (flirtation) と呼ぶ。一人の学生が複数のフラーテーションに属する可能性もある。例えば、四隅の学生は最大で \(2\) 個のフラーテーションに、中央部分の学生は最大で \(4\) 個のフラーテーションに属する。それぞれの机に男女が等しい確率で座るとき、フラーテーションの個数の期待値を求めよ。

ヒント: 期待値の線形性を利用する。

リテラル (literal) とは任意の命題変数 \(P\) またはその否定 \(\overline{\mathstrut P}\) を指す。ここで \(\overline{\mathstrut P}\) は通常通り \(\operatorname{\text{\footnotesize NOT}} (P)\) の略記である。異なる命題変数に関する \(3\) 個のリテラルを \(\operatorname{\text{\footnotesize OR}}\) で結んだ命題論理式を \(3\)-節 (\(3\)-clause) と呼ぶ。例えば

は \(3\)-節である。一方で \(P_{1} \ \operatorname{\text{\footnotesize OR}}\ \overline{\mathstrut P_{1}} \ \operatorname{\text{\footnotesize OR}}\ P_{2}\) は \(P_{1}\) に関するリテラルを \(2\) 個持つので \(3\)-節ではない。\(3\)-節を \(\operatorname{\text{\footnotesize AND}}\) で結んだ命題論理式を \(3\)-CNF と呼ぶ。例えば

は \(3\)-CNF である。

\(G\) を \(7\) 個の \(3\)-節からなる \(3\)-CNF とする。\(G\) に含まれる命題変数のそれぞれに \(\textbf{T}\) または \(\textbf{F}\) を等しい確率で独立に割り当てる試行を考える。

1. \(n\) 番目の \(3\)-節が \(\textbf{T}\) になる確率を求めよ。

2. \(\textbf{T}\) になる \(G\) の \(3\)-節の個数の期待値を求めよ。

3. \(\text{(b)}\) が \(6\) より大きい事実を利用して、\(G\) が充足可能だと示せ。

リテラル (literal) とは任意の命題変数 \(P\) またはその否定 \(\overline{\mathstrut P}\) を指す。ここで \(\overline{\mathstrut P}\) は通常通り \(\operatorname{\text{\footnotesize NOT}} (P)\) の略記である。異なる命題変数に関する \(k\) 個のリテラルを \(\operatorname{\text{\footnotesize OR}}\) で結んだ命題論理式を \(k\)-節 (\(k\)-clause) と呼ぶ。例えば

は \(4\)-節である。一方で

は \(V\) に関するリテラルを \(2\) 個持つので \(4\)-節でない。

\(\mathcal{S}\) を \(n\) 個の異なる \(k\)-節からなる集合、\(v\) を \(\mathcal{S}\) に含まれる式で使われる異なる命題変数の個数とする。\(\mathcal{S}\) に含まれる異なる二つの \(k\)-節に含まれる命題変数は完全に一致するか、全く異なるかのいずれかだと仮定する。ここから \(k \leq v \leq nk\) が分かる。

\(\mathcal{S}\) で使われる \(v\) 個の命題変数のそれぞれに \(\textbf{T}\) または \(\textbf{F}\) を等しい確率で独立に割り当てる試行を考える。

1. \(\mathcal{S}\) に含まれる特定の \(k\)-節が \(\textbf{T}\) になる確率を求めよ。解答は \(n\), \(k\), \(v\) を使った式で表せ。

2. \(\mathcal{S}\) に含まれる \(\textbf{T}\) に等しい \(k\)-節の個数の期待値を求めよ。解答は \(n\), \(k\), \(v\) を使った式で表せ。

3. 命題論理式の集合が充足可能 (satisfiable) とは、全ての命題が \(\textbf{T}\) になるような命題変数への真理値割り当てが存在することを言う。\(\text{(b)}\) の結果を使って、\(n < 2^{k}\) なら \(\mathcal{S}\) が充足可能だと示せ。

「情報科学のための数学 (MCS)」と「信号処理入門 (SP)」の講義を両方受講する学生は今期 \(n\) 人いる。採点の負担を軽減するため、二つの講義を担当する教授らは「受講者のリストをランダムな置換を取り、その順番通りに成績を付ける」という (多くの学生が想像する通りの) 方式を採用することに決めた。全ての置換が等しい確率で独立に選択されると仮定する。SP における順位が MCS における順位より下位で、その差が \(k\) 以上である学生の人数の期待値を求めよ。

ヒント: \(X_{r}\) を事象 [MCS で順位が \(r\) の学生の SP における順位が \(r + k\) 以下] に対応する指示確率変数とする。

自宅のドアの前に立つ男が \(n\) 個の鍵を手にしている。その中の \(1\) 個が目の前のドアを開く鍵である。男はドアが開くまでランダムな鍵を試す試行を繰り返す。ドアが開くまでに男が試す鍵の個数を表す確率変数を \(T\) とする。

1. 男が鍵を試して開かなかったとき、その鍵を手の中に戻すと仮定する。このとき男は間違った鍵を何度も試す可能性がある。\(\text{{Ex}[T]}\) を求めよ。

   ヒント: この問題は「初めてクラッシュするまでの平均ステップ数」と同じことを尋ねている。

男は開かなかった鍵を脇に置いておくと仮定する。つまり、男はまだ試していない鍵の中からランダムに選んだものを試していく。このとき正しい鍵は \(n\) 回以下の試行で必ず見つかる。

2. \(m\) 個の鍵を試して正しい鍵が見つからなかったとき、次に試す鍵が正しい確率を求めよ。

3. \(k - 1\) 個の鍵を試して正しい鍵が見つからなかったとき、\(k\) 個目の鍵も正しくない確率が次の式で与えられることを検証せよ:

   \[ \operatorname{Pr}[T > k \, | \, T > k - 1] = \frac{n - k}{n - (k - 1)} \]

4. 次の等式を示せ:

   \[ \operatorname{Pr}[T > k] = \frac{n-k}{n} \tag{19.18}\]

   ヒント: \(\text{(c)}\) の結果を使った数学的帰納法を使う。直接示すこともできる。

5. この仮定の下では次の等式が成り立つと示せ:

   \[ \operatorname{Ex} [T] = \frac{n + 1}{2} \]

独立な確率変数 \(R\), \(S\) は次の等式を満たす:

この事実の証明を次に示す。各行の式変形を正当化せよ:

証明

■

公平なコインを使った次の賭けを考える:

• 公平なコインを投げる。

• もし表が出たら勝利となり、賭け金の \(2\) 倍の額を獲得できる。

• もし裏が出たら敗北となり、賭け金を全て失う。

例えば、プレイヤーが \(\$10\) を賭けて勝利したら獲得金額は \(\$20\) であり、全体で \(\$10\) の儲けとなる。\(\$10\) を賭けて敗北したら獲得金額は \(\$0\) であり、\(\$10\) の損失となる。

ギャンブラーはこういったゲームで確実に勝つ戦略を見つけようと努力を続けている。倍賭け (bet doubling) と呼ばれる有名な戦略では、勝つまで賭け金を倍にし続ける。例えば、最初のゲームでは \(\$10\) 賭ける。もし最初のゲームで勝利したなら、\(\$10\) を儲けてギャンブルを終了する。最初のゲームで敗北したら、賭け金を倍の \(\$20\) にしてもう一度ゲームを行う。二度目のゲームで勝利したなら、\(\$40\) を受け取ってギャンブルを終了する。このとき儲けは \(\$40 - \$20 - \$10 = \$10\) となる。以下同様であり、もし三度目のゲームで勝利したら儲けは \(\$80 - \$40 - \$20 - \$10 = \$10\) となる。

こういった戦略で確実な儲けが出ることはあり得ないと思うかもしれない: これは期待収益 \(0\) の公平なゲームであり、どんな戦略を使ってもそれは変わらない。この考えを厳密に言い換えれば次のようになる:

だがちょっと待ってほしい！ \(\$10\) から始める倍賭けの戦略を用いるギャンブラーに関する次の問いに答えよ:

1. ギャンブラーは賭けを途中でやめない限り確実にゲームに勝利できると示せ。

2. ゲームに勝利した場合、総収益は \(\$10\) になると示せ。

3. ギャンブラーが勝利するなら総収益は \(\$10\) であり、ゲームには確実に勝利できる。これは次の関係を示している:

   \[ \operatorname{Ex} [W] = 10 \]

   しかし、これは等式 \(\text{(19.19)}\) と矛盾する。誤った結論 \(\text{(19.19)}\) が導かれる原因となった間違いを指摘せよ。

等式 \(\text{(19.13)}\) の導出で見たように、期待値の線形性を使うと一般二項分布に従う確率変数 \(f_{n,p}\) の期待値が直ちに得られる:

この等式は複雑な見た目をしているものの、二項定理 (定理 15.6.3) の等式とよく似ている点に注目すれば代数的な証明も簡単に分かる。

1. 二項定理が示す \((x + y)^{n}\) に関する恒等式を利用して、次の等式を示せ:

   \[ xn (x + y)^{n-1} = \sum_{k=0}^{n} k \binom{n}{k} x^{k} y^{n-k} \tag{19.21}\]

2. 等式 \(\text{(19.20)}\) の成立を結論付けよ。

Short-term Capital Management (STCM) は、あなたが次のルールに従って資産を投資することを望んでいる: まず、\(100\) 万ドルを Forward Looking Internet Package (FLIP) に投資する。FLIP に対する投資用の口座にある資金は \(1\) 年ごとに等しい確率で半減または倍増する。その後 STCM はその口座の金額の \(10\%\) に等しい額を配当金としてあなたに支払う。

1. 投資を初めて \(k\) 年目が終了した時点で口座にある金額の期待値を求めよ。\(k\) を使った簡単な式を答えること。

   ヒント: 投資を始めた時点では \(\$1{,}000{,}000\) が口座にある。\(X_{i}\) を \(i\) 年目の投資で口座の資金がどれだけ変化するかを表す確率変数とすれば、\(X_{i}\) は \(2\) または \(1/2\) を等しい確率で取る確率変数となる。\(1\) 年目の終わりに口座にある金額は \(X_{1} \cdot \$1{,}000{,}000\)であり、\(1\) 年目の配当金は \((1/10) X_{1} \cdot \$1{,}000{,}000\) である。

2. \(10\) 年目の終わりまでに支払われる配当金の総額の期待値を表す閉形式の式を求めよ。実際に計算する必要はない。

3. Adamアダム Smithスミス はこの投資を次のように解析した。ある年の終わりに口座の残高が倍増するなら \(Y_{i} = 1\) となり、半減するなら \(Y_{i} = -1\) となる確率変数 \(Y_{i}\) を導入する。このとき \(k\) 年目が終わった時点の口座の残高は次のように表せる:

   \[ 10^{6} 2^{Y_{1}} 2^{Y_{2}} \cdots 2^{Y_{k}} = 10^{6} 2^{Y_{1} + Y_{2} + \cdots + Y_{k}} \]

   設定より \(\operatorname{Ex}[Y_{i}] = 0\) なので、次を得る:

   \[ 2^{\operatorname{Ex} [Y_{1} + Y_{2} + \cdots + Y_{k}]} = 2^{\operatorname{Ex}[Y_{1}] + \operatorname{Ex}[Y_{2}] + \cdots + \operatorname{Ex}[Y_{k}]} = 2^{k \cdot 0} = 2^{0} = 1 \]

   つまり、口座の残高の期待値は常に投資を始めた時点の残高に等しい。

   Adam Smith の解析に含まれる間違いを指摘せよ。

\(\texttt{TTH}\) (裏・裏・表) の列が得られるまでコインを投げ続ける試行を考える。連続するコイン投げは独立で、コインが表を向く確率は \(p\) だとする。\(\texttt{TTH}\) が出て試行が終了するまでのコイン投げの回数を表す確率変数を \(N_{\texttt{TTH}}\) とする。\(\operatorname{Ex}[N_{\texttt{TTH}}]\) を最小化する \(p\) の値を答えよ。

(第二次世界大戦で起こった実話)

軍は \(n\) 人の兵士に対して病気の検査を行う必要がある。病気を持つ兵士から採取した血液サンプルを血液検査にかけると、病気は正確に検出される。軍はこれまでの経験から、この病気を持つ兵士の割合は小さい正の実数 \(p\) にほぼ等しいと考えた。

検査のアプローチが二つ考えられる:

• それぞれの兵士を個別に血液検査する。このとき \(n\) 回の血液検査が必要になる。

• ランダムな \(k\) 人の兵士からなるグループを \(g\) 個作る (\(n = gk\))。その上で、\(k\) 個の血液サンプルを一つにまとめてから血液検査にかける。この検査結果が陰性なら、そのグループに病気の兵士は一人もいないと分かる。もし検査結果が陽性なら、そのグループに病気の兵士が一人以上いると分かる。その場合はグループに属する兵士を一人ずつ個別に血液検査する。そのため、病気の兵士が一人以上含まれるグループに対しては全部で \(k + 1\) 回の血液検査が必要になる。

二つ目のアプローチの有用性について考えよう。各グループに属する兵士はランダムに選ばれるので、それぞれの兵士が病気にかかっている確率は \(p\) であり、ある兵士の病気の感染は他の兵士の病気の感染と独立すると仮定する。

1. 兵士の人数 \(n\), 有病率 \(p\), グループのサイズ \(k\) を使って、実施される検査の回数の期待値を表せ。

2. 検査の回数の期待値を近似的に \(n \sqrt{p}\) としたいとき、\(k\) に設定すべき値を求めよ。

   ヒント: \(p\) が小さいので \((1 - p)^{k} \approx 1\) と \(\ln (1 - p) \approx -p\) が成り立つ。

3. 兵士の人数が \(100\) 万人で有病率が \(1\%\) のとき、一つ目のアプローチの代わりに二つ目のアプローチを使うことで節約できる検査の回数を割合として示せ。

4. グループのグループを利用するさらに優れた検査方式を考案できるか？

幸運のルーレット (wheel-of-fortune) の周りには \(1\) から \(2n\) までの整数が等間隔に配置される。ルーレットを回すと、一つの数字とその反対側にある数字が選択される。次の値の期待値を最大化したいとき、どのように数字を配置すべきか答えよ。また、達成される最大の期待値を答えよ:

1. 選ばれる二つの数字の和

2. 選ばれる二つの数字の積

ヒント: \(\text{(b)}\) では、連続する二つの整数がルーレットで反対側にあるとき (\(1\) が \(2\) の反対側、\(3\) が \(4\) の反対側、\(5\) が \(6\) の反対側 \(\cdots\) にあるとき) に積の期待値が最大化されると示す。

\(R\) と \(S\) を独立な確率変数とする。関数 \(f\) と \(g\) が \(\operatorname{domain}(f) = \operatorname{codomain}(R)\) と \(\operatorname{domain}(g) = \operatorname{codomain}(S)\) を満たすなら、\(f(R)\) と \(g(S)\) も独立な確率変数だと示せ。

ヒント: 事象 [\(f(R) = a\)] は \(f(r) = a\) を満たす全ての \(r\) に関する事象 [\(R = r\)] の和集合 (非交和) である。

Peetaピータ は毎日 \(1\) 個以上 \(2n\) 個以下のパンを焼いて販売している。彼は毎朝、公平な \(n\) 面サイコロを振って出た \(1\) 以上 \(n\) 以下の目を \(m\) として、それから公平なコインを投げる。彼はコインが表を向いたら \(m\) 個のパンを焼き。コインが裏を向いたら \(2m\) 個のパンを焼く。

1. 任意の正整数 \(k \leq 2n\) に対して、任意の日に Peeta が \(k\) 枚のパンを焼く確率を求めよ。

   ヒント: 解答には場合分けが含まれる。

2. 任意の日に Peeta が焼くパンの個数の期待値を求めよ。

3. Peeta がパンを焼く生活を \(30\) 日続けるとき、Peeta が焼くパンの総個数の期待値を求めよ。

箱に \(n\) 個の黒いボールが入っている。箱からランダムにボールを取り出し次の操作を実行する試行を考える:

• 取り出したボールが黒いなら、確率 \(p > 0\) で表を向くコインを投げる。表が出たら白いボールを箱に入れ、裏が出たら黒いボールを箱に戻す。

• 取り出したボールが白いなら、その白いボールをそのまま箱に戻す。

この試行を箱の中身が白いボールだけになる (白いボールが \(n\) 個になる) まで繰り返す。

箱の中身が白いボールだけになるまでに箱から取り出されるボールの個数を表す確率変数を \(D\) とする。このとき、次の等式が成り立つと示せ:

ここで \(H_{n}\) は \(n\) 次調和数を表す。

ヒント: \(i\) 番目の白いボールが箱に入ってから \(i + 1\) 番目の白いボールが箱に入るまでの間に箱から取り出されるボールの個数を表す確率変数を \(D_{i}\) とする。

ギャンブラーがルーレットの「赤」に \(\$10\) を賭けた。勝率は \(18/38\) であり、\(1/2\) より少しだけ小さい。彼は勝った場合は \(\$10\) の儲けを手にしてカジノを去り、負けた場合は賭け金を倍にして同じことを繰り返すつもりでいる。

例えば、もし彼が最初の \(2\) 回のスピンで負けて \(3\) 回目のスピンで勝ったなら、彼は \(\$10 + \$20 + \$40 = \$70\) を失ってから \(\$40 + \$40 = \$80\) を獲得するので総収益は \(\$10\) となる。

1. ギャンブラーが勝つまでに賭けるスピンの回数の期待値を求めよ。

2. ギャンブラーがいずれ勝つ確率を求めよ。

3. ギャンブラーの最終的な総収益 (獲得した金額から失った金額を引いた値) の期待値を求めよ。

4. この倍賭け (bet doubling) 戦略を使うと不公平なゲームで確実に儲けを得ることができる。しかし、この戦略はギャンブラーとカジノの両方が資金を無限に持つことを要求するので、現実には実行できない。この事実を「最後のスピンにおけるギャンブラーの賭け金の期待値が無限大である」と証明することで示せ。

\(1\) から \(6\) までの整数が書かれたカードが \(2\) 枚ずつ計 \(12\) 枚ある。これをシャッフルして一列に並べる試行を考える。例を次に示す:

この例では、同じ数字が連続して並ぶ箇所が二つ (\(3\) と \(5\)) ある。同じ数字が連続して並ぶ箇所の個数の期待値を求めよ。

\(1\) から \(6\) までの整数が書かれたカードが \(3\) 枚ずつ計 \(18\) 枚ある。これをシャッフルして一列に並べる試行を考える。例を次に示す:

この例では、同じ数字が \(3\) 枚連続して並ぶ箇所が二つ (\(3\) と \(5\)) ある。

1. \(4\) 番目、\(5\) 番目、\(6\) 番目のカードが同じ数字 (全て \(1\), 全て \(2\), \(\cdots\)) になる確率を求めよ。

2. \(p ::= \operatorname{Pr}[\text{\(4\) 番目、\(5\) 番目、\(6\) 番目のカードが同じ数字}]\) とする。つまり、\(p\) を \(\text{(a)}\) の解答とする。\(p\) を使って、同じ数字が \(3\) 枚連続で並ぶ箇所の個数の期待値を表せ。