ゲーム論的確率論の導入

　ちゅらデータの k.ueda です。[8日](https://qiita.com/kueda_cs/items/605eb56b0a7ad2703759)に引き続き、[ちゅらデータ Advent Calender](https://qiita.com/advent-calendar/2021/churadata) 2回目のエントリーです。これは22日目の記事です。みなさんはいわゆる**測度論的確率論**をよくご存知のことと思いますが、この記事ではそれとはまた違ったオルタナティブな確率論である**ゲーム論的確率論**を紹介します。

# ゲーム論的確率論とは
　確率論は17世紀にパスカルがフェルマーへ送った手紙から始まった議論から発展したと言われています。その内容に含まれていた**分配問題**は大まかには以下のようなものでした。
>　2人がそれぞれ32ピストールを出し合い、先に3回勝った方が64ピストールを総取りするという賭けを考える。一方が2勝、もう一方が1勝しているときに賭けが中断されたとき、64ピストールはどのように分配されるべきだろうか。

　2人の議論で大きく発展した確率論は、その後1930年代のコルモゴロフによるランダムネスを排した定式化により、現在の測度論的な「確率」の定義を用いたものになりました。モダンな確率論では所与の確率測度 $P$ を持った確率空間 $\left(\Omega, \mathcal{F}, P \right)$ と確率変数（とは名ばかりの決定論的なラベル付け関数）$X$ を用いた議論が進められます。これらの道具立てにより、確率論はランダムネスに触れずに行うことが可能となったのです。
　それから長きに渡り覇権を握ってきた測度論的確率論のオルタナティブとして2001年に Shafer と Vovk による書籍 "Probability and Finance, It's Only a Game!" で発表されたのがゲーム論的確率論です。ゲーム論的確率論では、 **Skeptic**（「結果」を当てる賭けをするプレイヤー ; 統計家, 投資家）と **Reality**（賭けの「結果」を出すプレイヤー ; 自然, マーケット）との間の Skeptic → Reality → Skeptic → Reality → … というターン制の勝負を考えます。Skeptic の目的は資金を無限に増やすこと、Reality の目的はそれを阻止することです。このゲームの結果として「確率」が定まるというのが基本的な考え方です。確率論の "芽生え" だった賭けの問題を基礎とし、ランダムネスを避けずに直接定式化するという、これまでのものとはまったく違う新たな前提から生まれたこの理論を、ここでほんのさわりだけではありますが紹介していきます。

# 大数の法則
## 「賭け」の定式化
　「賭け」を以下のように定式化します。
$K_n \left(n \geq 0\right)$ : Skeptic の時点 $n$ での資金（一旦 $K_n = 0$ となったらそれ以降賭けられないので $K_{n+1}=K_{n+2}=\cdots = 0$）
$e_i \left(1 \leq i \leq k \right)$ : 不確定な事象 $E$ の起こりうる結果たち
$b_j \left(1 \leq j \leq l \right)$ : 賭け口
$m_{ij}$ : 結果が $e_i$ だったときの賭け口 $b_j$ の1口あたりの配当
$M_{nj}$ : Skeptic が $n$ 回目の賭けで $b_j$ に賭ける金額（ただし賭けられる総額は手持ちの資金を超えない :  $\sum_{j=1}^{l} M_{nj} \leq K_{n-1}$ ）

　Skeptic は資金を無限に増やすこと、Reality はそれを阻止することが目的でした。すなわち、$\lim_{n\rightarrow \infty}K_n = \infty$ となるような**戦略**（賭け方）$\mathcal{P}$ があるかどうかが問題となります。「現実には何らかの意味での "中立性" を備えたゲームで一方が無限に儲けられる状況はおかしい」ということで、Reality が Skeptic の勝利を阻止した結果として出てくるもの（「確率」の概念）に正当性が与えられていると考えられます。

## 結果当てゲーム
　結果と Skeptic の予想が完全一致した場合にだけ配当がある**結果当てゲーム**を考えます（予想は複数の結果に対してすることができるので、すべての賭け口にベットすれば必ずどれかひとつ一致させることができます）。このゲームでは各結果に対し賭け口が用意されています（$k = l$）。$m_{ii} = r_i$ の配当が設定され、それ以外の $m_{ij} \left(i\neq j\right)$ はすべて $0$ となっています。結果当てゲームが
$$\sum_{i=1}^{k} \frac{1}{r_i} = 1$$ を満たすとき、**中立**であるといいます。胴元の利益がない、つまり賭け口 $b_i$ に投票した人の比率が $\pi_i$ だったときの配当倍率が $r_i = \pi_i^{-1}$ であるような賭けは $\sum_{i=1}^k r_i^{-1} = \sum_{i=1}^k \pi_i = 1$ となるため、中立です。

　このようなゲームにおいて、Reality は Skeptic の目的を阻止することができるのでしょうか。以下の定理によって、どのような場合に阻止可能なのかがわかります。

>［大数の強法則］
　$c_{ni}$ を $n$ 回目までの結果で $e_i$ が出た回数とする。このとき、Skeptic の戦略で、Reality がすべての $1 \leq i \leq k$ に対して $$\lim_{n\rightarrow\infty}\frac{c_{ni}}{n} = \frac{1}{r_i}$$ となるよう結果を出さない限り必ず勝利する、すなわち $$\lim_{n\rightarrow\infty}K_n=\infty$$ となるようなようなものが存在する。

　つまり、Skeptic の勝利を防ぐために Reality は結果 $e_i$ の出る比率が $r_i^{-1}$ に近づくようにしなくてはなりません。中立結果当てゲームにおいて Reality は一定確率で結果を選ぶことを強いられます。

## コイントスゲーム
　もっとシンプルな場合について見てみましょう。コイントスをして表（$1$）が出るか裏（$0$）が出るかを当てる結果当てゲームを考えます（コイントスといっても、Reality は表と裏を自分で決められます）。$K_0 = 1$ とし、Skeptic の資金は $$K_n = K_{n-1} + M_n\left(x_n-p\right)$$ で表されるとします。ただし、$x_n \in \left\\{0,1 \right\\}$ は Reality が $n$ 回目の賭けで出す結果、$p\in\left(0,1\right)$ は定数です。ここでは賭け金 $M_n$ は負の値も許すことにします。
　この設定のもとでも、大数の法則により、Reality が Skeptic の勝利を阻止するためには確率的に結果を出すことを強いられます。
>［大数の強法則］
　Skeptic の戦略で、Reality が $$\lim_{n\rightarrow\infty}\frac{x_1+x_2+\cdots+x_n}{n} = p$$ となるよう結果を出さない限り必ず勝利するようなものが存在する。

　これは Reality が Skeptic の戦略を最初から知っていても成り立ちます。ゲーム論的確率論では、このように「確率」という概念を用いずに確率論の定理が導けたりします。

　実際に Reality が勝つようコイントスゲームをシミュレートしてみると、出す結果は平均 $0.5$ になることがわかります。ゲーム数を確保するため、Skeptic の破産を考えずに見てみましょう。

```Julia
using Random
using Statistics

# 初期値を設定
K = [1.0]  # 資金
M = [2 * rand() - 1]  # 賭け金は -1 から 1 の間としておく
X = [rand(0:1)]  # 表裏
# 資金の計算
calc_score(x::Int64) = K[end] + M[end] * (x - 0.5)

for i in 1:1000000
    # Skeptic が賭け金を宣言
    push!(M, 2 * rand() - 1)
    # Reality は Skeptic の資金を減らす結果を出し続ける
    push!(X, argmin([calc_score(0), calc_score(1)]) - 1)
    push!(K, calc_score(X[end]))
end

# 出した結果の平均を計算
print(mean(X))
-> 0.5002974997025003
```
　Skeptic が別の戦略で賭け金を宣言した場合も同じ結果となります。

```Julia
for i in 1:1000000
    # Skeptic は直前に出た結果に寄せて賭け金を宣言
    if (X[end] == 1)
        push!(M, M[end] + 0.1)
    else
        push!(M, M[end] - 0.1)
    end
    # Reality は Skeptic の資金を減らす結果を出し続ける
    push!(X, argmin([calc_score(0), calc_score(1)]) - 1)
    push!(K, calc_score(X[end]))
end

# 出した結果の平均を計算
print(mean(X))
-> 0.5000044999955
```

　みなさんの手元でも色々な戦略でシミュレートしてみましょう。


# マルチンゲール
　ここまでは「Skeptic の資金が無限に増えることを防ぐためにはランダムに結果を出さざるを得ない」ということを確認しましたが、逆に「結果がランダムであれば Skeptic は資金を無限に増やせないのか」ということを考えてみます。ここでは確率 $P$ は所与の概念であるとします。

　$n$ 回目の賭けまでの事象の結果 $\xi^n = \left(\varepsilon_1, \varepsilon_2, \cdots, \varepsilon_n \right)$ を**径路**と呼び、これが径路 $\eta^m \left( n \leq m\right)$ の途中までの結果を表すものであるとき $\xi^n \subseteq \eta^m$ と表すことにします。径路の全体 $\Omega = \left\\{ \xi^\infty \right\\} = {\left\\{e_i \middle|1\leq i \leq k \right\\}}^\infty$ を**標本空間**と呼びます。ただし、$\xi^\infty$ は任意の $n\geq 0 $ に対して $\xi^n \subsetneq \xi^\infty$ となるようなものです。**事象** $E$ は径路の集合 $E \subseteq \Omega$ と考えることができます。
　独立な事象の系列 $E_1, E_2, \cdots, E_n, \cdots$ の結果が $e_i$ である確率はすべて $p_i$ (ただし$\sum_{i=1}^{k}p_i = 1$）であるとします。Skeptic の戦略 $\mathcal{P}$ が $n$ 回目の賭けで $\xi^{n-1}$ に基づいて $M_{n1}, M_{n2}, \cdots, M_{nk}$ を決めるものであるとき、すべての賭け口 $b_j$ に対して
$$\sum_{i=1}^{k}\left(m_{ij} - 1\right)p_i = 0$$ となるように配当を設定すれば、賭け方に依らず利益の "期待値" は $0$ となります。このような賭けを**公平**な賭けと呼ぶことにしましょう。**確率変数**を $X_{nj} = m_{ij} - 1$ と定めると、普通の確率論と同様に $$\mathbb{E}\left[X_{nj} \right] = \sum_{i=1}^{k} X_{nj}\ p_i = 0$$ と表記することができます。
　$n$ 回目の賭けの結果の資金 $K_n$ は、賭けの前の資金 $K_{n-1}$ と $\xi^{n-1}$ から戦略 $\mathcal{P}$ が定める賭け金 $M_{n1}\left(\xi^{n-1}\right), M_{n2}\left(\xi^{n-1}\right), \cdots, M_{nl}\left(\xi^{n-1}\right)$ を用いて $$K_n = K_{n-1} + \sum_{j=1}^{l}X_{nj} \ M_{nj}\left(\xi^{n-1}\right)$$ と表されます。径路 $\xi^{n-1}$ のもとでの条件付き期待値を取ると、公平な賭けの場合は
$$
\begin{align}
\mathbb{E}\left[K_n\middle|\xi^{n-1}\right] &= \mathbb{E}\left[K_{n-1} + \sum_{j=1}^{l}X_{nj} \ M_{nj}\left(\xi^{n-1}\right) \middle| \xi^{n-1}\right] \\\
&= K_{n-1} + \sum_{j=1}^{l} \mathbb{E}\left[X_{nj} \middle| \xi^{n-1}\right]\ M_{nj}\left(\xi^{n-1}\right) \\\
&= K_{n-1}
\end{align}
$$
となります。$\mathbb{E}\left[Y_n\middle|\xi^{n-1}\right] = Y_{n-1} \left(n\geq 1\right)$ を満たす確率変数列 $Y_1, Y_2,\cdots,Y_n,\cdots$ は**マルチンゲール**であるといいます。等号 $=$ を不等号 $\leq$ に変えた条件を満たす場合は**スーパーマルチンゲール**であるといいます。

　マルチンゲール列（およびスーパーマルチンゲール列）について、以下の定理が成り立ちます。
>［定理］
　$Y_0 = 1$ の非負マルチンゲール列 $Y_0,Y_1,\cdots,Y_n,\cdots$ について、
$$P\left(\limsup_{n \rightarrow \infty} Y_n = \infty \right) = 0$$ が成り立つ。

　つまり、公平な賭けにおいては Skeptic はほとんど確実に敗北するということです。

# 確率
## 「確率」の定義
　結局のところ、確率をどう定義すればいいのかというところをここまでの議論では曖昧なままにしていました。ゲーム論的確率論では確率というものを具体的にどうとらえればよいのでしょうか。少し面倒なことに、確率を定義するためには問題によって個別にゲームを設定しなければなりません。
　事象 $S\subseteq\Omega$ の確率は上確率 $\overline{P}\left(S\right) = \overline{\mathbb{E}}\left[\delta_S\left(\xi\right)\right]$ と下確率 $\underline{P}\left(S\right) = \underline{\mathbb{E}}\left[\delta_S\left(\xi\right)\right]$ が一致するとき、$P\left(S\right) = \overline{P}\left(S\right) = \underline{P}\left(S\right)$ と定義されます。ただし、$\delta$ は
$$\delta_S\left(\xi\right) = 1 \ \mathrm{if} \ \xi \in S \ \mathrm{else} \ 0$$
で定まる関数です。この確率を定義するために、期待値（期待価格）を導入します。

## 期待価格
　各賭け口 $b_j$ への賭け金 $M_{nj}$ に制限を設けないゲームを考えます。Skeptic は $M_{nj}$ を負にして「売り」に出てもよいですし、借金をして資金を超えた額 $\sum_{j=1}^{l} M_{nj} > K_{n-1}$ を賭けることもできます。また、最初の資金 $K_0$ は $0$ としておきます。Skeptic は借金をして賭けるところからスタートします。
　このような賭けと別に、径路 $\xi$ に応じて価格が決まるデリバティブ商品 $Y\left(\xi\right)$ を考えます。簡単のため、ここで価格は有限径路で決まるとします。この資産を価格 $v$ で買うと、まず $v$ を支払ったのちに $Y\left(\xi\right)$ を得ることとなり、価格 $v$ で売ると、まず $v$ を得たのちに $Y\left(\xi\right)$ を支払うことになります。
　$Y$ の適正価格はどれくらいでしょうか。任意の経路に対して $$K > Y\left(\xi\right) - v$$ となるような戦略が存在するとき、賭けをするほうがこの商品を買うよりも必ず得をすることになります。よって、合理的な価格の上限は $$v^\ast  = \inf_{\mathcal{P}}\sup_{\xi}\left(Y\left(\xi\right) - K\right)$$ となります。逆に、売ることについて考える場合、合理的な価格の下限は $$v_\ast  = \sup_{\mathcal{P}}\inf_{\xi}\left(Y\left(\xi\right) - K\right)$$ となります。すなわち、$Y$ の合理的な価格は**上期待価格** $\overline{\mathbb{E}}\left[Y\right] = v^\ast$ と**下期待価格** $\underline{\mathbb{E}}\left[Y\right] = v_\ast$ を用いて $$\overline{\mathbb{E}}\left[Y\right] \leq v \leq \underline{\mathbb{E}}\left[Y\right]$$ の範囲内といえます。上期待価格と下期待価格が一致するとき、$\mathbb{E}\left[Y\right] = \overline{\mathbb{E}}\left[Y\right] = \underline{\mathbb{E}}\left[Y\right]$ を単に**期待価格**といいます。上期待価格と下期待価格はふたつの商品 $Y_1, Y_2$ に対してそれぞれ
$$\overline{\mathbb{E}}\left[Y_1+Y_2\right] \leq \overline{\mathbb{E}}\left[Y_1\right]+\overline{\mathbb{E}}\left[Y_2\right]$$ $$ \underline{\mathbb{E}}\left[Y_1+Y_2\right] \geq \underline{\mathbb{E}}\left[Y_1\right]+\underline{\mathbb{E}}\left[Y_2\right]$$
を満たすので、期待価格が存在するとき $$\mathbb{E}\left[Y_1+Y_2\right] = \mathbb{E}\left[Y_1\right]+\mathbb{E}\left[Y_2\right]$$ が成り立つことがわかります。

## 「確率」の計算
　定義より、上確率は
$$
\left\\{
\begin{align}
K\left(\xi\right) &\geq 1 - P \ \left(\xi\in S \right)\\\
K\left(\xi\right) &\geq - P \ \left(\xi\notin S\right)
\end{align}
\right.
$$
となるような戦略 $\mathcal{P}$ が存在する $P$ の下限です。また、下確率は
$$
\left\\{
\begin{align}
K\left(\xi\right) &\geq P - 1 \ \left(\xi\in S \right)\\\
K\left(\xi\right) &\geq P \ \left(\xi\notin S\right)
\end{align}
\right.
$$
となるような戦略 $\mathcal{P}$ が存在する $P$ の上限です。

　再度、 $p = 0.5$ のコイントスゲームを考えます。コイントスゲームにおける資金は $K_n = K_{n-1} + M_n\left(x_n - 0.5\right)$ で決まりました。ここで、賭け金 $M_n$ と結果 $x_n$ に対して $\tilde{M}\_n = 0.5 \ M_n$ と $\tilde{x}\_n = 2 \left(x_n - 0.5 \right) $ を考えます。すると、このゲームの資金は $K_n = K_{n-1} + \tilde{M}\_n \tilde{x}\_n $
と表せます。$K_{n-1} = 0$ とし、$S$ を $x_n = 1$ なる径路の集合としたとき、上確率 $\overline{P}\left(S\right)$ は

- $x_n = 1$ なら $K\left(\xi\right) = K_n = \tilde{M}\_n$ だから $\tilde{M}\_n \geq 1 - P$
- $x_n = 0$ なら $K\left(\xi\right) = K_n = - \tilde{M}\_n$ だから $- \tilde{M}\_n \geq - P$

すなわち $1 - P \leq \tilde{M}\_n \leq P$ となるような $P$ の下限だから、$\overline{P}\left(S\right) = 0.5$ であることがわかります。下確率 $\underline{P}\left(S\right)$ は

- $x_n = 1$ なら $K\left(\xi\right) = K_n = \tilde{M}\_n$ だから $\tilde{M}\_n \geq P - 1$
- $x_n = 0$ なら $K\left(\xi\right) = K_n = - \tilde{M}\_n$ だから $- \tilde{M}\_n \geq P$

すなわち $P - 1 \leq \tilde{M}\_n \leq - P$ となるような $P$ の上限だから、同様に $\underline{P}\left(S\right) = 0.5$ であることがわかります。以上より、$P\left(S\right) = 0.5$ となります。このゲームから出てくる確率は $p = 0.5$ のベルヌーイ分布に対応したものとなります。

------
　今回はゲーム論的確率論の導入までを書きました。定理の証明や理論のもっと深い部分はこれから続編記事を書いていこうと思うので、しばしお待ちを。

# 参考文献
- [竹内啓. 賭けの数理と金融工学. サイエンス社, 2004.](https://www.saiensu.co.jp/search/?isbn=978-4-7819-9949-4&y=2018)
- [小島寛之, 松原望. 戦略とゲームの理論. 東京図書, 2011.](http://www.tokyo-tosho.co.jp/books/ISBN978-4-489-02111-4.html)