Tokyo-University
東京大学 新領域創成科学研究科 複雑理工学専攻 2018年度 専門基礎科目 第4問
Author 之遥
Description プレイヤーはマシーンと一回のみゲームを行う。 \(i = 1, 2, \dots, n\) とし、プレイヤーが値 \(i\) を出す確率を \(p_i\) とし、 \(\sum_{i=1}^n p_i = 1\) とする。 \(j = 1, 2, \dots, n\) とし、マシーンが値 \(j\) を出す確率を \(q_j\) とし、 \(\sum_{j=1}^n q_j = 1\) とする。プレイヤーとマシーンは、\(1\) から \(n\) までの自然数を、この確率分布に従い出すものとする。プレイヤーとマシーンが同じ数を出したとき、プレイヤーの勝ちとする。このとき、以下の問いに答えよ。
(問1)
\(i = 1, 2, \dots, n\) に対して、 \(p_i = 1/n\) とする。プレイヤーが勝つ確率を求めよ。
(問2)
\(i = 1, 2, \dots, n\) に対して、 \(p_i = p_1 \alpha^{i-1}\) とし、 \(j = 1, 2, \dots, n\) に対して、 \(q_j = q_1 \beta^{j-1}\) とする。プレイヤーが勝つ確率を、 \(\alpha, \beta, n\) のみを用いて表せ。
(問3)
\(i = 1, 2, \dots, n\) に対して、 \(p_i = q_i\) とする。
(a) プレイヤーが勝つ確率の最小値を求めよ。
(b) マシーンが出す値の期待値が \((n + 1)/2\) であるとする。プレイヤーが勝つ確率の最小値を求めよ。
(問4)
\((p_1, p_2, \dots, p_n)\) をプレイヤーの戦略と呼ぶことにする。以下の二つの戦略を考える。
戦略 \(E\) : \((p_1, p_2, \dots, p_{n-1}, p_n) = (0, 0, \dots, 0, 1)\)
戦略 \(R\) : \((p_1, p_2, \dots, p_n) = (1/n, 1/n, \dots, 1/n)\)
ここで、 \(q_1, q_2, \dots, q_n\) のうち、 \(q_n\) が最大であるとする。
(a) 戦略 \(E\) は、戦略 \(R\) より優れていることを示せ。ここで、戦略 \(A, B\) に対して、戦略 \(A\) を用いたときのプレイヤーが勝つ確率が、戦略 \(B\) を用いた時のプレイヤーが勝つ確率以上のとき、戦略 \(A\) は戦略 \(B\) より優れているという。
(b) 戦略 \(E\) は、任意の戦略の中で最も優れていることを示せ。
Kai (問1)
\[
P(\text{Player wins}) = \sum_{1}^{n}p_iq_i = \frac{1}{n}\sum_{1}^{n}q_i = \frac{1}{n}
\]
(問2)
\[
\left\{
\begin{aligned}
&1 = \sum_{1}^{n}p_i = \sum_{1}^{n}p_1\alpha^{i-1} = p_1\frac{1 - \alpha^n}{1 - \alpha} \\
&1 = \sum_{1}^{n}q_j = \sum_{1}^{n}q_1\beta^{j-1} = q_1\frac{1 - \beta^n}{1 - \beta}
\end{aligned}
\right. ,\qquad
\left\{
\begin{aligned}
&p_1 = \frac{1 - \alpha}{1 - \alpha^n} \\
&q_1 = \frac{1 - \beta}{1 - \beta^n}
\end{aligned}
\right.
\]
\[
\begin{aligned}
&P(\text{Player wins}) = \sum_{1}^{n}p_iq_i = \sum_{1}^{n}p_1q_1(\alpha\beta)^{i-1} = p_1q_1\frac{1 - (\alpha\beta)^n}{1 - \alpha\beta} \\
&= \frac{1 - \alpha}{1 - \alpha^n}\frac{1 - \beta}{1 - \beta^n}\frac{1 - (\alpha\beta)^n}{1 - \alpha\beta}
\end{aligned}
\]
(問3)
(a)
\[
P(\text{Player wins}) = \sum_{1}^{n}p_iq_i = \sum_{1}^{n}p_i^2 = n\Big(\sqrt{\frac{\sum_{1}^{n}p_i^2}{n}}\Big)^2 \ge n\Big(\frac{\sum_{1}^n p_i}{n}\Big)^2 = \frac{1}{n}
\]
When \(p_i = \frac{1}{n}(i = 1,2,\dots,n)\) , \(P(\text{Player wins})\) obtains its minimum \(\frac{1}{n}\) .
(b)
When \(p_i = \frac{1}{n}(i = 1,2,\dots,n)\) , \(E[\text{Machine's output}] = \sum_{1}^{n}\frac{i}{n} = \frac{n + 1}{2}\) satisfies the condition. So it can obtain its minimum in (問3).(a) , which is \(\frac{1}{n}\) .
(問4)
(a)
\[
\begin{aligned}
&P_{E}(\text{Player wins}) = \sum_{1}^{n}p_iq_i = q_n \\
&P_{R}(\text{Player wins}) = \sum_{1}^{n}p_iq_i = \frac{\sum_{1}^{n}q_i}{n} = \frac{1}{n} \\
&\because q_n \ge q_1,q_2,\cdots,q_{n-1} \\
&\therefore 1 = q_1 + q_2 + \cdots + q_{n - 1} + q_n \le q_n + q_n + \cdots + q_n + q_n = nq_n \\
&q_n \ge \frac{1}{n} \\
&\therefore P_{E}(\text{Player wins}) \ge P_{R}(\text{Player wins}) , \text{ which means that the strategy E is superior to the strategy R}.
\end{aligned}
\]
(b)
Sulution 1
\[
P_{\text{any}}(\text{Player wins}) = \sum_{1}^{n}p_iq_i \le \sum_{1}^{n}p_iq_n = q_n\sum_{1}^{n}p_i = q_n = P_{E}(\text{Player wins})
\]
So the strategy E is superior to any strategies.
Solution 2
For any strategy \(A\) , let \(p_1 = \Delta_1 ,p_2 = \Delta_2 \cdots p_{n-1} = \Delta_{n-1},p_n = 1 - \sum_{1}^{n-1}\Delta_i\) , where \(0 \le \Delta_i \le 1(i=1,2,\dots,n-1)\) .
\[
\begin{aligned}
&\quad P_{E}(\text{Player wins}) - P_{A}(\text{Player wins}) \\
&= (0 - \Delta_1)q_1 + (0 - \Delta_2)q_2 + \cdots + (0 - \Delta_{n-1})q_{n-1} + \sum_{1}^{n}\Delta_{i}q_n \\
&= \Delta_1(q_n - q_1) + \Delta_2(q_n - q_2) + \cdots + \Delta_{n-1}(q_n - q_{n-1}) \ge 0 \\
&\therefore P_{E}(\text{Player wins}) \ge P_{A}(\text{Player wins})
\end{aligned}
\]
So the strategy E is superior to any strategies.