0185-2018 东新复 数学 P96

概率统计 概率论 博弈论

プレイヤーはマシーンと一回のみゲームを行う．$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は，任意の戦略の中で最も優れていることを示せ．

---

解答：
プレイヤーとマシーンがそれぞれ値 $i$ と $j$ を出す事象は独立であるため，プレイヤーが勝つ確率 $P$ は，

$$P=\sum _{k=1}^n{p}_k{q}_k$$

で与えられる．

(問1)
$p_i=1/n$ より，

$$\begin{array}{rl}P& =\sum _{i=1}^n\frac{1}{n}{q}_i\\ & =\frac{1}{n}\sum _{i=1}^n{q}_i\\ & =\frac{1}{n}\end{array}$$ $$\boxed{\frac{1}{n}}$$

(問2)
$\sum _{i=1}^n{p}_i=1,\sum _{i=1}^n{q}_i=1$ より，
$\alpha \ne 1$ のとき $p_1=\frac{1-\alpha }{1-{\alpha }^n}$，$\alpha =1$ のとき $p_1=\frac{1}{n}$．
$\beta \ne 1$ のとき $q_1=\frac{1-\beta }{1-{\beta }^n}$，$\beta =1$ のとき $q_1=\frac{1}{n}$．
勝つ確率 $P$ は，

$$\begin{array}{rl}P& =\sum _{i=1}^n{p}_1{\alpha }^{i-1}{q}_1{\beta }^{i-1}\\ & =p_1{q}_1\sum _{i=1}^n(\alpha \beta {)}^{i-1}\end{array}$$

これより公比の値によって以下に場合分けされる．

$$\boxed{\begin{array}{rl}& \alpha \ne 1,\beta \ne 1,\alpha \beta \ne 1\text{ のとき }\frac{(1-\alpha )(1-\beta )(1-(\alpha \beta {)}^n)}{(1-{\alpha }^n)(1-{\beta }^n)(1-\alpha \beta )}\\ & \alpha \ne 1,\beta \ne 1,\alpha \beta =1\text{ のとき }\frac{n{\alpha }^{n-1}(1-\alpha {)}^2}{(1-{\alpha }^n{)}^2}\\ & \alpha =1\text{ または }\beta =1\text{ のとき }\frac{1}{n}\end{array}}$$

(問3)
(a)
$p_i=q_i$ より，$P=\sum _{i=1}^n{p}_i^2$．
コーシー・シュワルツの不等式により，

$$\begin{array}{rl}n\sum _{i=1}^n{p}_i^2& =\left(\sum _{i=1}^n{1}^2\right)\left(\sum _{i=1}^n{p}_i^2\right)\\ & \ge q{\left(\sum _{i=1}^n{p}_i\right)}^2\\ & =1\end{array}$$

等号成立は $p_1=p_2=\cdots =p_n=1/n$ のときであり，$\sum p_i=1$ を満たす．

$$\boxed{\frac{1}{n}}$$

(b)
条件より $\sum _{i=1}^{n}i{q}_i=\frac{n+1}{2}$ であり，$p_i=q_i$ より $\sum _{i=1}^{n}i{p}_i=\frac{n+1}{2}$ が成り立つ．
(a)で求めた最小値を与える確率分布 $p_i=1/n(i=1,\dots ,n)$ において，

$$\begin{array}{rl}\sum _{i=1}^{n}i\left(\frac{1}{n}\right)& =\frac{1}{n}\cdot \frac{n(n+1)}{2}\\ & =\frac{n+1}{2}\end{array}$$

となり，この期待値の条件も満たす．よって最小値は変わらない．

$$\boxed{\frac{1}{n}}$$

(問4)
(a)
戦略Eを用いたときの勝つ確率は $P_E=\sum _{i=1}^n{p}_i{q}_i=q_n$．
戦略Rを用いたときの勝つ確率は $P_R=\sum _{i=1}^n\frac{1}{n}{q}_i=\frac{1}{n}$．
$q_n$ は $q_1,\dots ,q_n$ の最大値であるから，

$$\begin{array}{rl}1& =\sum _{i=1}^n{q}_i\\ & \le q\sum _{i=1}^n{q}_n\\ & =n{q}_n\end{array}$$

よって $q_n\ge 1/n$ となり，$P_E\ge P_R$ が成り立つ．したがって戦略Eは戦略Rより優れている．(証明終)

(b)
任意の戦略 $(p_1,\dots ,p_n)$ における勝つ確率を $P$ とすると，$p_i\ge 0$ と $q_i\le q_n$ より，

$$\begin{array}{rl}P& =\sum _{i=1}^n{p}_i{q}_i\\ & \le q\sum _{i=1}^n{p}_i{q}_n\\ & =q_n\sum _{i=1}^n{p}_i\\ & =q_n\\ & =P_E\end{array}$$

よって任意の戦略について $P_E\ge P$ が成り立つため，戦略Eは任意の戦略の中で最も優れている．(証明終)

---

本题考察了离散概率分布的基本性质以及博弈论中策略选择的简单应用。胜率的计算本质上是两个概率向量的内积。第二问考察等比数列求和，难点在于准确地根据公比是否为一进行分类讨论，特别是容易遗漏两参数乘积为一但各自不为一的特殊情况。通过概率和为一的前提可以求出各自的首项，进而计算内积。第三问是带约束的最值问题，利用柯西不等式可以求出无额外约束条件下的最小值对应于均匀分布。而均匀分布的期望恰好等于题目所给的限制条件，这意味着无约束情况下的极小值点刚好落在了约束条件的子空间内，因此该极小值也就是增加约束情况下的最小值。第四问反映了针对给定对手策略的最优应对思想，当对手给出的概率分布已知时，玩家能获得最大胜率的策略必然是把所有的概率权重都集中在对手出现概率最大的那个选项上，这种最优的纯策略的胜率是一切混合策略的上限。