シン・破産確率

こんにちは、[@richwomanbtc](https://twitter.com/richwomanbtc)です！

[仮想通貨botter Advent Calender 2021](https://qiita.com/advent-calendar/2021/botter)の22日目の記事です。

この記事に関して質問、誤りのご指摘等ありましたらぜひコメントお願いします！

また、この記事の内容に参考にしてトレード等を行い損害が発生したとしても責任は負いかねます。ご了承ください。

今回は破産確率について、私なりに~~実験してみた~~まとめてみた結果を載せたいと思います。(実験する時間がなかったのでまとめただけになりました。ごめんなさい。いつか必ず追記します)
よくweb上の記事に「バルサラの破産確率」の図が出回っていますが、「バルサラの破産確率」はいくつかの仮定を置き、現実の問題を単純化したものに対しての破産確率を示しています。
この記事では、仮定しているものを明確にした上で破産確率を導出、あるいは数値計算することで、より正確な破産確率を求めてみよう、というものです。

## Gambler's ruin problem

問題 (gambler's ruin problem):
掛け金を$R>0$を指定する。勝つと$WR>0$を得て、負けると$LR>0$を失う($-LR$を得る)ゲームがある。このゲームに勝つ確率を$p$とする。
最初の所持金が$N_0$であるとして、このゲームを際限なく繰り返すとき所持金が$C\geq0$に達する確率$Q(N_0)$はいくらか。
ただし、所持金が目標額$M>N_0$に達した場合も繰り返しを終了する。

$Q(N_0)$が破産確率と呼ばれます。
ruin problemにおいて、払い戻し$W, L$や勝率$p$が各ゲームで異なるケースも考えられます。
また、掛け金を各ゲームで変えることができるケースもできます。
簡単なケースからはじめて、徐々に難しいケース(より現実的なケース)を考えていきたいと思います。

### 簡単なケース
まず、$R=1, N_0\in \mathbb{N}$(自然数)とした場合を考えます。各ゲームの勝率$p$は各ゲームで一定であり、$W=L=1$とします。また、$C=0$とします。つまり、

問題1:
勝つと$1$を得て、負けると$1$を失うゲームがある。このゲームに勝つ確率を$p$とする。
最初の所持金が$N_0\in \mathbb{N}$であるとして、このゲームを際限なく繰り返すとき所持金が$0$に達する確率$Q(N_0)$はいくらか。
ただし、所持金が目標額$M>N_0$に達した場合も繰り返しを終了する。

問題1を解くためには$Q(N_0\pm1)$を考えます。
所持金が$N_0$の場合に破産するパターンは二通りあります。

1.「ゲームを行い、所持金が$N_0+1$になったあと破産する」パターン
2.「ゲームを行い、所持金が$N_0-1$になったあと破産する」パターン

です。この2つのパターンでの破産確率を合計すれば$Q(N_0)$が得られます。数式で書くと

$$
Q(N_0)=p Q(N_0+1) + (1-p)\times Q(N_0-1)
$$

という(確率)漸化式が得られます。
この漸化式を解けば一般項$Q(N_0)$を求めることができます。
これは隣接三項間漸化式というタイプの漸化式で、特性方程式と呼ばれる方程式の解と2つの境界条件を用いて解くことができます。
(ちなみに高校数学の範囲内です。)

漸化式の特性方程式は

$$
x=px^2+(1-p)
$$

であり、その解は

$$
x = 1, \frac{1-p}{p}
$$

です。

境界条件は次のように得られます。
$N_0=0$の場合は定義から破産確率$1$で、$N_0=M$の場合は繰り返しを終了するので破産確率は$0$となります。つまり、

$$
Q(0)=1, Q(M)=0
$$

が境界条件です。

これらを用いると漸化式を解くことができて、(ただし、一般項を求める前に$Q(1)$を求める必要があることに注意してください)

$$
Q(N_0) = \frac{\alpha^{N_0}-\alpha^M}{1-\alpha^M}, p\neq1/2
$$

$$
Q(N_0) =1-\frac{N_0}{M}, p=1/2
$$

が得られます。ここで、$\alpha=\frac{1-p}{p}$と置きました。
より詳細な導出手順を知りたい方は[^1]や[^2]を参考にしてみてください。

### もうちょっと難しいケース
さて、今度はもう少し難しいケースを考えます。
$C=0$としますが、$R, W, L$が$1$とは限らない定数の場合を考えてみましょう。
また、見通しをよくするために"金額"に関するパラメータを全て$LR$で割っておきます。
つまり$w=WR/LR=W/L, n_0=N_0/LR, m=M/LR$と置きます。
こうすると

問題2:
勝つと$w>0$を得て、負けると$1$を失うゲームがある。このゲームに勝つ確率を$p$とする。
最初の所持金が$n_0$であるとして、このゲームを際限なく繰り返すとき所持金が$0$に達する確率$Q(n_0)$はいくらか。
ただし、所持金が目標額$m>n_0$に達した場合も繰り返しを終了する。

問題2は問題1と同じように考えると

$$
Q(n_0) = p \times Q(n_0+w)+(1-p) \times Q(n_0-1)\\
$$

$$
Q(0)=0,Q(m)=1
$$

が得られます。
問題1と異なり、この漸化式(?)の特性方程式は

$$
x=px^{1+w}+(1-p)
$$

となり、$x=1$以外の解を求めるのが難しいということです。

[^3]や[^4]によると、この特性方程式の実数解$S$は$0<x<1$に一つだけ存在し、

$$
Q(n_0)\leq S^{n_0}
$$

と評価できるようです。(詳しくは[^5]に書いてあるらしい)
特性方程式の解はpythonでもexcelでも簡単に求められるので、$Q(n_0)$の上限を得ることができます。

~~サンプルコード~~


### バルサラの破産確率
問題2は「$C=0$としますが、$R, W, L$が$1$とは限らない定数の場合」でしたが、実はバルサラの破産確率は定率の場合、つまり、$R$が$l$回目のゲーム開始時の所持金$N_l$に比例する場合の破産確率に相当します。
この場合は$C=0$とすると永久に破産しない(賭金が無限に小さくなっていく)ために、$C>0$と取る必要があります。
この場合も実は問題2に帰着させることができます。[^4]
そのため、問題2と同様に特性方程式を解き、破産確率の上限を得ることができます。

### 勝率が自己相関をもつ場合
勝率$p$が自己相関を持つというもう少し複雑なケースを考えます。
今までの問題は暗に各ゲームの結果が独立であると仮定していました。
しかし、現実のbotを運用してみると、勝ってる時は連続で勝ちやすい、あるいは勝ったあとは負けやすい、といった傾向あったりします。
例えば、連続で負けやすいbotであれば各トレードが無相関であると仮定したときより破産しやすいかもしれません。

この場合は漸化式を得るのも難しそうなので、割り切ってモンテカルロシミュレーションを行うことを考えます。
この際、$l+1$回目の勝率は$l$回目のゲームの勝率$p_{l}$を使って$p_{l+1}=\beta p_{l}+\epsilon_l$としてやります。
ここで、$\epsilon$は平均$0$、分散$\sigma^2$のホワイトノイズとします。
つまり、勝率がAR(1)モデルに従うと仮定して、サンプリングを行い、得られたサンプルパスに対して、破産した割合を計算してやれば破産確率を見積もる事ができます。

## 最後に

後半はざっくりした内容になってしまいましたが、破産確率が何を仮定して、どのように導出されているかざっくりと理解してもらえたら幸いです。
あと、Qiitaは数式と注釈が書きづらかったので、二度と使いません。
よいbotterライフを！

## 参考記事

\[1]: [想像の100倍は破産します【破産問題】](https://www.youtube.com/watch?v=AfJnUUGQDE0) めちゃくちゃわかりやすい
\[2]: [三項間漸化式の3通りの解き方](https://manabitimes.jp/math/697)
\[3]: [破産確率の計算](https://va2577.github.io/post/46/)
\[4]: [バルサラの破産確率の導出](http://autodaytrade.blog.fc2.com/blog-entry-70.html?sp) でもこれはバルサラの破産確率の導出ではない気がする。
\[5]: [確率論とその応用 I 下](https://www.amazon.co.jp/dp/4314000163/ref=cm_sw_r_tw_dp_0RP4W7QJCYJAKGMJSVFE )