Best-of-(2n-1)(M-SOLUTIONプロコンオープン)

Pocket

こんにちは、ふるやん(@furuya1223)です。

先日の M-SOLUTION プロコンオープンC 問題(期待値の問題)が、なぜあの解法で正しくなるのかを解説してみたいと思います。

問題概要

高橋君と青木君が、どちらかが N 勝するまでゲームを繰り返します。

1回のゲームでは、A % の確率で高橋君が勝ち、B % の確率で青木君が勝ち、C % の確率で引き分けになります。

どちらかが N 回勝つまでにゲームが行われる回数の期待値を出力します。

準備

とりあえず N=3 で考えてみます。

各ゲームの結果の列を、「CAACCBCCCCA」のように文字列で表してみます。

この場合は、高橋君が 3 勝し、青木君 1 勝して、高橋君の勝ちです。

ゲームが行われた回数は 11 回です。

C=0 の場合

まず、引き分けが無い場合を考えてみます。

この場合は、結果列は「AABA」のように、A と B のみになります。

「M 回で終わる確率」が分かれば、期待値の計算ができます。

とりあえず、高橋君が勝つ場合だけを考えてみましょう。

M 回目で高橋君が N 勝して終わるには、「M-1 回の間に高橋君が N-1 勝し、青木君が M-N 勝する」かつ「M 回目で高橋君が勝つ」という条件が両方成立する必要があります。

M-1 回目までの結果と M 回目の結果は独立(M-1 回目までの結果によって M 回目の結果の確率が変化しない)なので、前者の確率と後者の確率を掛ければよいです。

前者の確率は、

$${}_{M-1}\mathrm{C}_{N-1}a^{N-1}b^{M-N}$$

と表現できます。ただし、a=A/100, b=B/100 はそれぞれ、高橋君と青木君の勝つ確率です(C=0 のため A+B=100 である点に注意)。

コンビネーションの部分は、例えば「A2回, B1回」の場合に「AAB, ABA, BAA」の並べ替えパターンを考慮しているということです。

後者の確率はもちろん a なので、全体の確率は

$${}_{M-1}\mathrm{C}_{N-1}a^{N}b^{M-N}$$

となります。

ここまでが分からない方は、高校数学(数学A?)の「場合の数と確率」について勉強すると良いでしょう。

M 回目で青木君が N 勝して終わる確率も同様に、

$${}_{M-1}\mathrm{C}_{N-1}a^{M-N}b^{N}$$

となります。したがって、M 回で終わる確率は

$${}_{M-1}\mathrm{C}_{N-1}\left (a^{N}b^{M-N} + a^{M-N}b^{N}\right )$$

となるので、ゲーム回数の期待値は

$$\sum_{M=N}^{2N-1}M{}_{M-1}\mathrm{C}_{N-1}\left (a^{N}b^{M-N} + a^{M-N}b^{N}\right )$$

となります。M の取りうる値の範囲が N から 2N-1 であることに注意です。

ここまでは解説どおりですね。

C が 0 でない場合

結果列から C(引き分け)を除いた文字列について考えます。

例えば、結果列が「CAACCBCCCCA」となっている場合には「AABA」になります。

これを「引き分け除去後の結果列」と呼んでみましょう。

引き分け除去後の結果列の最初の文字が「A」になる確率はいくらでしょうか。

最初の文字ということは「最初に C 以外が出たとき」ということです。そのときに A が出る確率は、条件付き確率ですね。A か B が出たということが確定しているので、

$$P(Aが出る|AかBが出た)=\frac{(Aが出る)かつ(AかBが出た)}{AかBが出た}$$

$$=\frac{Aが出る}{AかBが出た}=\frac{\frac{A}{100}}{\frac{A}{100}+\frac{B}{100}}=\frac{A}{A+B}$$

となります。

これは最初に限りません。2 回目の ” C 以外” でも、A が出る確率は A/(A+B) です。

そのため、a=A/(A+B), b=B/(A+B) と置くと、C=0 の場合と同じように、引き分け除去後の結果列が「AABA」になる確率は「a^3*b^1」になりますし、引き分け除去後の結果列が M 文字になる確率は、高橋君勝ちと青木君勝ちを合わせて

$${}_{M-1}\mathrm{C}_{N-1}\left (a^{N}b^{M-N} + a^{M-N}b^{N}\right )$$

となります。

次に、「引き分け除去後の結果列が M 文字になったときの、引き分け除去前の結果列の長さの期待値」を考えましょう。

例えば M=4 のとき、結果列の長さは

結果列の長さ = (1 回目に C 以外が出るまでの回数)+(2 回目に C 以外が出るまでの回数)+(3 回目に C 以外が出るまでの回数)+(4 回目に C 以外が出るまでの回数)

となります。

この期待値を考えます。このとき、期待値の線形性(特に「和の期待値は期待値の和」)より、

$$E[結果列の長さ]=\sum_{i=1}^4E[i回目に\mathrm{C}以外が出るまでの回数]$$

となります。E[〜] は「〜の期待値」という意味です。

A, B, C の出やすさは常に一定なので、総和の中身は i によって変化しません。したがって結局

$$E[結果列の長さ]=4\times E[\mathrm{C}以外が出るまでの回数]$$

M を一般化すると、

$$E[結果列の長さ]=M\times E[\mathrm{C}以外が出るまでの回数]$$

となります。Mは「引き分け除去後の結果列の長さ」です。

では、E[C以外が出るまでの回数] を考えましょう。

これは「幾何分布の期待値」などで検索すると出てきますが、1/(C以外が出る確率) になります。

成功率 p のチャレンジを成功するまで行う場合のチャレンジ回数の期待値は 1/p です。

簡単な証明が 解説PDF に掲載されています。別の証明を記事の末尾に載せておきます。

今回、C 以外が出る確率は 1-C/100=(100-C)/100 なので、

$$E[\mathrm{C}以外が出るまでの回数]=\frac{100}{100-C}$$

となります。

したがって、「引き分け除去後の結果列が M 文字になったときの、引き分け除去前の結果列の長さの期待値」は

$$\frac{100M}{100-C}$$

となります。

さて、ここで、上記の期待値について別の解釈をしてみます。

「引き分け除去前の結果列の長さ」を X 、「引き分け除去後の結果列の長さ」を M とします。

この定義を用いて、「引き分け除去後の結果列が m 文字になったときの、引き分け除去前の結果列の長さの期待値」を E[X|M=m] と書きます。これは条件付き期待値の表記法ですが、今は難しいことは考えなくて大丈夫です。「M が m になったときの X の期待値」と解釈するだけで大丈夫です。

期待値の定義から、E[X|M=m] は、引き分け除去前の長さを X として

$$E[X|M=m]=\sum_{x=m}^\infty x\times P(X=x|M=m)$$

となります。ただし、P(X=x|M=m) は、「M が m になったときに X が x になる確率」です。

この値が

$$\frac{100m}{100-C}$$

になるので、

$$\sum_{x=m}^\infty x\times P(X=x|M=m)=\frac{100m}{100-C}$$

です。これは後で使います。

今回欲しい値は「引き分け除去前の結果列の長さの期待値」です。つまり E[X] です。

これは、期待値の定義を用いて

$$E[X]=\sum_{x=N}^\infty x\times P(X=x)$$

と表現できます。

ここで、P(X=x) が以下のように表現できることを利用します。

$$P(X=x)=\sum_{m=N}^{2N-1}P(M=m)P(X=x|M=m)$$

これは、「X が x になる」という事象が「M が m になって X が x になる」という事象に分割できて、それぞれが排反(同時に起こらない)ということに基づいています(確率の和の法則)。ただし、x<m のときは P(X=x|M=m)=0 であることに注意してください(引き分けを除去して長くなることは無い)。

X が 11 になる確率は、M が 3 になって X が 11 になる場合と、M が 4 になって X が 11 になる場合と、……の確率の和になるということです。

これを用いると、

$$E[X]=\sum_{x=N}^\infty x\times \sum_{m=N}^{2N-1}P(M=m)P(X=x|M=m)$$

となります。

x を中の総和に入れて、掛け算の並べ替えをすると以下のようになります。

$$E[X]=\sum_{x=N}^\infty \sum_{m=N}^{2N-1}P(M=m)\times x \times P(X=x|M=m)$$

さらに、大胆にも総和の入れ替えを行います。無限和なので絶対収束する必要がありますが、すると信じましょう。総和の中身が全て 0 以上なので、この総和が収束すれば絶対収束することになりますね。(このへんが雑)

$$E[X]=\sum_{m=N}^{2N-1}\sum_{x=N}^\infty P(M=m)\times x \times P(X=x|M=m)$$

さらに、x に関する総和に無関係な P(M=m) を x に関する総和の外に出すと

$$E[X]=\sum_{m=N}^{2N-1}P(M=m)\times \sum_{x=N}^\infty x \times P(X=x|M=m)$$

となります。また、x<m のときは P(X=x|M=m)=0 で、かつ m >= N なので、

$$E[X]=\sum_{m=N}^{2N-1}P(M=m)\times \sum_{x=m}^\infty x \times P(X=x|M=m)$$

と書くことができます。

最後の総和は、すでに計算した「引き分け除去後の結果列が m 文字になったときの、引き分け除去前の結果列の長さの期待値」 E[X|M=m] なので、

$$\sum_{x=m}^\infty x\times P(X=x|M=m)=\frac{100m}{100-C}$$

を用いて、

$$E[X]=\sum_{m=N}^{2N-1}P(M=m)\times \frac{100m}{100-C}$$

となります。

P(M=m) もすでに計算しています。a=A/(A+B), b=B/(A+B) と置いたときの

$${}_{m-1}\mathrm{C}_{N-1}\left (a^{N}b^{m-N} + a^{m-N}b^{N}\right )$$

ですね。

ということで、最終的に計算すべき値は、a=A/(A+B), b=B/(A+B) と置いて

$$E[X]=\sum_{m=N}^{2N-1}{}_{m-1}\mathrm{C}_{N-1}\left (a^{N}b^{m-N} + a^{m-N}b^{N}\right )\times \frac{100m}{100-C}$$

となります。

有限の値になったので、絶対収束の条件は満たしていると考えていいんじゃないでしょうか。(雑)

終わりに

期待値の問題でいちいちこんなことを考えるわけにはいきません。

自己ループを含む遷移の問題は、自己ループのたびに「(1/遷移確率)回で遷移する」とみなして良いです。この記事がその理由です。

そうすると、遷移グラフが DAG になって DP が使えるようになったりします。(参考:ARC016-C「ソーシャルゲーム」

期待値はかなり雑に考えても良いという性質を持っていますが、たまには正当性を考えてみるのも良いと思います。

おまけ:幾何分布の期待値

成功確率 p のチャレンジを成功するまで行う場合のチャレンジ回数の期待値を計算してみます。

0 < p <= 1 とします。(p=0 なら永遠に成功しない)

等差数列×等比数列

高校数学的な解き方です。

x 回で終わる確率は、x-1 回失敗した後に成功する確率なので、

$$p(1-p)^{x-1}$$

となります。期待値を E と置くと、期待値の定義から

$$E=\sum_{x=1}^\infty xp(1-p)^{x-1}$$

となります。これは「等差数列×等比数列」の形になっているので、高校数学の常套手段をつかいます。

両辺に (1-p) を掛けると、

$$(1-p)E=\sum_{x=1}^\infty xp(1-p)^x$$

となり、また、

$$E=p+\sum_{x=2}^\infty xp(1-p)^{x-1}=p+\sum_{x=1}^\infty (x+1)p(1-p)^x$$

と書けるので、これらを辺ごとに引いて、

$$-pE=-p-\sum_{x=1}^\infty p(1-p)^x$$

無限等比級数の計算式より

$$\sum_{x=1}^\infty p(1-p)^x=\frac{p(1-p)}{1-(1-p)}=1-p$$

となります。

したがって

$$-pE=-p-(1-p)=-1$$

より

$$E=\frac{1}{p}$$

となる。

モーメント母関数

確率論的な解き方です。

チャレンジ回数 X の確率関数は、

$$P(x)=p(1-p)^{x-1}$$

と書けます。したがって、X が従う分布(幾何分布)のモーメント母関数は

$$M_X(t)=E[e^{tX}]=\sum_{x=1}^\infty e^{tx}p(1-p)^{x-1}=\sum_{x=1}^\infty \frac{p}{1-p}\left\{ (1-p)e^t \right\}^x$$

$$=\frac{pe^t}{1-(1-p)e^t}$$

となります。ただし、

$$t<-\ln (1-p)$$

です。

期待値を得るために、これを t で微分します。

$$\frac{\mathrm{d}}{\mathrm{d}t}M_X(t)=\frac{pe^t}{1-(1-p)e^t}+\frac{p(1-p)e^{2t}}{\left\{1-(1-p)e^t\right\}^2}$$

これに t=0 を代入して、

$$E[X]=1+\frac{1-p}{p}=\frac{1}{p}$$

となります。

Pocket

スポンサーリンク
レクタングル大
レクタングル大

シェアする

  • このエントリーをはてなブックマークに追加

フォローする