練習問題

ギャンブラーが \(1\) ドルの賭けを繰り返し実行するゲームを遊ぶとする。毎回の賭けの勝率は \(0.49\) であり、勝つと \(1\) ドル獲得でき、負けると \(1\) ドル失う。彼は破産する (資金が \(0\) になる) か資金が \(T\) に達するまで賭けを続ける。

初期資金が \(n\) ドルのギャンブラーがゲーム終了までに行う賭けの回数の期待値を \(t(n)\) とする。このとき、関数 \(t(n)\) は次の形の線形再帰方程式を満たす:

ここで \(a\), \(b\), \(c\) は定数を表す。また \(0 < n < T\) である。

1. \(a\), \(b\), \(c\) を答えよ。

2. \(t(0)\) を答えよ。

3. \(t(T)\) を求めよ。

ギャンブラーの破産問題において、ギャンブラーは \(1\) ドルの賭けを繰り返し実行する。毎回の賭けは独立であり、ギャンブラーは確率 \(p\) で勝って \(1\) ドル獲得し、確率 \(q ::= 1 - p\) で負けて \(1\) ドル失う。彼は破産する (資金が \(0\) になる) か資金が \(T\) に達するまで賭けを続ける。

\(T = \infty\) とする。つまり、ギャンブラーは破産するまで賭けを続ける。ギャンブラーの初期資金が \(n > 0\) ドルのとき、ゲーム中に彼の資金が一度でも \(n - 1\) ドルになる確率を \(r\) とする。

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

   \[ r = q + p r^{2} \]

2. \(p \leq 1/2\) なら \(r = 1\) だと結論付けよ

3. 初期資金がどれだけ大きくても、賭けが公平ならギャンブラーは確実に破産すると示せ。

4. ギャンブラーの資金が現在資金より \(1\) ドル減るまでの賭けの回数の期待値を \(t\) とする。次の等式が成り立つ理由を説明せよ:

   \[ t = q + p (1 + 2t) \]

   初期資金が \(1\) ドルだったとしても、賭けが公平ならギャンブラーは平均して無限に長く賭けを続けられると示せ。

ギャンブラーがルーレットの「先頭 \(1\) ダース」に \(1\) ドルを賭ける。この賭けはボールが \(1\) 以上 \(12\) 以下のマスに入ると勝利であり、\(3\) ドルが払い戻される (\(2\) ドルの儲けとなる)。それ以外の場合は敗北であり、払い戻しはない。ルーレットには \(1\) から \(38\) の整数が順に書かれた \(38\) 個のマスがある。

ギャンブラーの初期資金は \(n\) ドルであり、目標資金は \(T\) ドルである。彼は破産する (資金が \(0\) ドルになる) か資金が \(T\) ドルになるまで賭けを続ける。ギャンブラーが破産する前に資金を \(T\) ドルに増やして勝利する確率を \(w_{n}\) とする。

1. \(w_{n}\) が満たす線形再帰方程式と、その境界条件を示せ。再帰方程式を解く必要はない。

2. ゲームが終わるまでに行われる賭けの回数の期待値を \(e_{n}\) とする。\(e_{n}\) が満たす線形再帰方程式と、その境界条件を示せ。再帰方程式を解く必要はない。

初期資金が \(n\) ドル、目標資金が \(T\) ドル、毎回の賭けが公平なギャンブラーの破産問題のゲームを考える。ゲームが終わる (資金が \(0\) ドルまたは \(T\) ドルになる) までに行う賭けの回数を \(e_{n}\) とする。

1. 次の等式を満たす定数 \(a\), \(b\), \(c\) を答えよ:

   \[ e_{n} = a e_{n-1} + b e_{n-2} + c \tag{21.17}\]

   ここで \(1 < n < T\) とする。

2. \(e_{n}\) を全ての \(n > 1\) に対して式 \(\text{(21.17)}\) で定義する。ただし \(e_{0} = 0\) および \(e_{1} = d\) とする (\(d\) は定数)。母関数 \(E(x) ::= \sum_{n=0}^{\infty} e_{n} x^{n}\) を \(d\) が含まれる閉形式の式で表せ。

3. \(e_{n}\) を \(d\) が含まれる閉形式の式で表せ。

4. \(\text{(c)}\) の解答を \(d\) について解け。

5. \(e_{n} = n (T - n)\) を示せ。

次のランダムウォークグラフ (辺に確率が割り当てられた有向グラフ) を考える:

1. 図 \(\text{21.4}\) のグラフの定常分布における \(x\) の確率を求めよ。

2. 図 \(\text{21.4}\) のグラフの定常分布における \(y\) の確率を求めよ。

3. 図 \(\text{21.4}\) のグラフで頂点 \(x\) から (頂点 \(x\) の確率が \(1\) の確率分布から) ランダムウォークを開始するとき、確率分布は定常分布に収束するか？

4. 図 \(\text{21.5}\) のグラフの定常分布における \(w\) の確率を求めよ。

5. 図 \(\text{21.5}\) のグラフの定常分布における \(z\) の確率を求めよ。

6. 図 \(\text{21.5}\) のグラフで頂点 \(w\) から (頂点 \(w\) の確率が \(1\) の確率分布から) ランダムウォークを開始するとき、確率分布は定常分布に収束するか？

   ヒント: 最初の数ステップを実際にシミュレートし、何が起こるか観察する。

7. 図 \(\text{21.6}\) のグラフには何個の定常分布が存在するか？

8. 図 \(\text{21.6}\) のグラフで頂点 \(b\) から (頂点 \(b\) の確率が \(1\) の確率分布から) ランダムウォークを開始するとき、定常分布における頂点 \(d\) の確率を求めよ。

有向グラフのシンク (sink) とは、出次数が \(0\) の頂点を意味する。つまりシンクを始点に持つ有向辺は存在しない。辺に確率が割り当てられた有限有向グラフがちょうど \(2\) 個のシンクを持つとき、その定常分布に関して成り立つ命題を次の中から選べ:

1. 存在しない可能性がある。

2. 一意である可能性がある。

3. ちょうど二つ存在する。

4. 加算無限個存在する可能性がある。

5. 非加算無限個存在する可能性がある。

6. 常に非加算無限個存在する。

次のランダムウォークグラフ (辺に確率が割り当てられた有向グラフ) に定常分布が非加算無限個存在する理由を説明せよ:

1. 図 \(\text{21.7}\) のランダムウォークグラフ (辺に確率が割り当てられた有向グラフ) の定常分布を求めよ。

2. 図 \(\text{21.7}\) のランダムウォークグラフで頂点 \(x\) から (頂点 \(x\) の確率が \(1\) の確率分布から) ランダムウォークを開始すると、確率分布は定常分布に収束しない。定常分布に収束するのは最初の確率分布がどのようなときか答えよ。

3. 図 \(\text{21.8}\) のランダムウォークグラフの定常分布を求めよ。

4. 図 \(\text{21.8}\) のランダムウォークグラフで頂点 \(w\) から (頂点 \(w\) の確率が \(1\) の確率分布から) ランダムウォークを開始するとき、確率分布は定常分布に収束するか？ 最初の数ステップを書いて何が起こるか説明せよ。数学的な証明は必要ない。

5. 図 \(\text{21.9}\) のランダムウォークグラフが非加算個の定常分布を持つと示せ。

6. 図 \(\text{21.9}\) のランダムウォークグラフで頂点 \(b\) から (頂点 \(b\) の確率が \(1\) の確率分布から) ランダムウォークを開始するとき、頂点 \(d\) の確率はどのような値に近づくか？ 解答が正しい理由を説明せよ。

7. 強連結でないものの定常分布が一意なランダムウォークグラフの例を示せ。

   ヒント: 自明な例がある。

本講義の期末試験を終えた学生の典型的な動きを有向グラフ \(G\) 上のランダムウォークグラフでモデル化してみよう。

学生はグラフの特定の頂点で表された教室で期末試験を受ける。試験を終えた学生は満身創痍で頭がぼんやりしているので、その行動は確率的にしか予測できない。\(G\) の辺には確率が割り当てられ、各ステップで頂点 \(u\) にいる学生は \(u\) を始点とする有向辺の中から一つをその確率に沿って選び、その終点に移動する。

\(n ::= |V(G)|\) として、ベクトル \(P^{(j)}\) を次のように定義する:

ここで \(p_{i}^{(j)}\) は \(j\) ステップ後に学生が頂点 \(i\) にいる確率を表す。

1. 次の簡単な有向グラフを \(G\) とする。学生が試験を受ける場所が頂点 \(1\) に対応するとき、\(P^{(0)}\), \(P^{(1)}\), \(P^{(2)}\) を求めよ。また、\(P^{(n)}\) を表す式を答えよ。

   

2. 任意の有向グラフ \(G\) に対して、\(p_{k}^{(j - 1)}\) (\(k = 1, 2, \ldots, n\)) を使って \(p_{i}^{(j)}\) を表現する方法を説明せよ。

3. 本講義で言及した線形方程式系の中に、\(\text{(b)}\) の解答と似た形をしたものが存在する。それを答えよ。

4. 極限分布 (limiting distribution) \(\pi\) を次のように定義する:

   \[ \pi ::= \lim_{k \to \infty} \frac{\sum_{i=1}^{k} P^{(i)}}{k} \]

   \((a)\) で考えた有向グラフの極限分布を答えよ。最初の分布が \(P^{(0)} = (1/2,\, 1/2)\) または \(P^{(0)} = (1/3,\, 2/3)\) のとき、極限分布は変化するか？

5. 続いて、次の有向グラフを \(G\) とする。期末試験が複数の教室を使って行われるために、最初に学生が頂点 \(1\) にいる確率が \(0.5\) で、学生が頂点 \(2\) に確率が \(0.5\) だとする。このとき \(P^{(0)}\), \(P^{(1)}\), \(P^{(2)}\) そして極限分布を答えよ。

   

6. これで現実の問題に取り掛かる準備が整った。試験を終えた憐れな学生が試験会場のドアを開けると、そこは \(n\) 個のドアが並んだ長い廊下だった。彼は気が付いていないものの、極楽 (講義からの解放、そして何といっても長期休暇) があるのは遠く離れた最後のドアの向こうである。ドアには魔法がかけられており、彼はドアを開けるたびに確率 \(1/2\) で最初にいた試験会場の部屋にテレポート (一瞬で移動) する。この憐れな学生が廊下から脱出するまでにかかる時間を考えよう。この問題を次の有向グラフでモデル化するとき、\(P^{(0)}\), \(P^{(1)}\), \(P^{(2)}\) そして極限分布を答えよ。

   

7. 廊下を脱出するまでに発生するテレポートの回数の期待値が \(2^{n-1} - 1\) だと示せ。

有限のランダムウォークグラフ (辺に確率が割り当てられた有向グラフ) で「頂点上の一様分布が定常分布」と「任意の頂点に対して、その頂点に向かう有向辺の確率の和が \(1\)」が同値だと示せ。後者の条件は次のように表現できる:

ここで \(\operatorname{into}(w) ::= \left\{ v \; | \; \langle v \to w \rangle \text{ が有向辺} \right\}\) と定義される。

任意の頂点に対して「その頂点を始点に持つ全ての有向辺が同じ確率を持つ」が成り立つランダムウォークグラフ (辺に確率が割り当てられた有向グラフ) を Google グラフと呼ぶ。つまり、Google グラフでは任意の有向辺 \(\langle v \to w \rangle\) が確率 \(1 / \operatorname{outdeg}(v)\) を持つ。

有向グラフが対称 (symmetric) とは、有向辺 \(\langle v \to w \rangle\) が存在するとき逆向きの有向辺 \(\langle w \to v \rangle\) も必ず存在することを意味する。有限かつ対称な Google グラフの各頂点 \(v\) に対して次のように \(d(v)\) を定める:

ここで \(e\) はグラフ全体が持つ辺の本数を表す。

1. \(d\) を使ってウェブページをランク付けするとき、任意のページのランクを高くするハックが可能になる。どのようなハックか説明せよ。有向グラフの対称性を仮定しない「本物の」ページランクではそのハックが通用しない理由を簡単に説明せよ。

2. \(d\) が定常分布だと示せ。

有向グラフが強連結 (strongly connected) とは、任意の \(2\) 頂点間を結ぶ路が双方向に存在することを言う。この問題では強連結な有限ランダムウォークグラフ (辺に確率が割り当てられた有向グラフ) を考える。

1. \(G\) を強連結な有限ランダムウォークグラフ、\(d_{1}\), \(d_{2}\) を \(G\) の頂点上の異なる確率分布とする。\(d_{2}\) から見た \(d_{1}\) の最大拡大率 (maximum dilation) \(\gamma\) を次のように定義する:

   \[ \gamma ::= \max_{x \in V} \frac{d_{1}(x)}{d_{2}(x)} \]

   \(d_{1}(x) / d_{2}(x) = \gamma\) が成り立つ頂点 \(x\) を最大拡大 (dilated) と呼ぶことにする。最大拡大でない頂点 \(y\) から最大拡大な頂点 \(z\) への有向辺 \(\langle y \to z \rangle\) が存在すると示せ。

   ヒント: 最大拡大な頂点 \(x\) を任意に取り、\(x\) を終点に持つ路の始点となる最大拡大な頂点全体の集合を \(D\) とする。\(D \neq V\) である理由を説明し、グラフが強接続である事実を使う。

2. 強連結な有限ランダムウォークグラフの定常分布の個数は \(1\) 個以下だと示せ (実際には定常分布は常に存在するものの、それは証明しなくて構わない)。

   ヒント: \(d_{1}\) を定常分布、\(d_{2}\) を \(d_{1}\) と異なる定常分布として、\(\text{(a)}\) の条件を満たす頂点 \(z\) を選ぶ。\(d_{2}\) から初めてランダムウォークを \(1\) ステップ進めると、\(z\) の確率は変化することが示せる。

図 \(\text{21.10}\) に示すランダムウォークグラフ (辺に確率が割り当てられた有向グラフ) の中で、頂点上の一様分布が定常分布であるものを答えよ。辺に書かれた数字は辺の確率を表す。解答が正しい理由を説明せよ。

ランダムウォークグラフ (辺に確率が割り当てられた有向グラフ) \(G\) のトラップ (trap) とは、\(G\) の部分有向グラフ \(H\) であって \(H\) の任意の頂点を始点とする \(G\) における全ての有向辺の終点が \(H\) の頂点であるものを言う。

あるランダムウォークグラフにはトラップがちょうど \(2\) 個あり、それらは頂点を共有しないという。このグラフの定常分布に関する次の命題の中で成り立つものを選べ:

1. 存在しない可能性がある。

2. 一意である。

3. ちょうど \(2\) 個ある。

4. 有限個しか存在しない。

5. 加算無限個ある。

6. 加算無限個ある場合もあれば、非加算無限個ある場合もある。

7. 非加算無限個ある。