MIS.W 公式ブログ

早稲田大学公認、情報系創作サークル「早稲田大学経営情報学会」(MIS.W)の公式ブログです!

期待値問題の形式的冪級数によるアプローチ【カウントダウンカレンダー2019冬7日目】

こんにちは! 競技プログラミング中毒者のhotmanです
競技プログラミングの事しかわからなくなってしまったので、競技プログラミングの事を書きます
数学に強くなりたいのと、ゴリゴリ競プロだとmis.wの誰も読んでくれなくなる気がしたので数学要素強めでいきます
この知識を使う競プロの問題はあまり見ないので、思考パズルのつもりで読んで頂けるとありがたいです
後、解説記事しか書けないので解説記事を書きます

関連記事(おすすめの記事)

maspyさんによる記事(これがきっかけで競プロ界に形式的冪級数が流行りました)
maspypy.com

これはmis.wの幽霊サークル員である所のSenが書いた記事で、僕も関わっている記事です
sen-comp.hatenablog.com
sen-comp.hatenablog.com

これ、難しいのも乗ってます
http://www.aoni.waseda.jp/sadayosi/course/past/comb15/chapter1.pdf

一通り読み終わったらこれを解いて見てもいいかもしれません
基礎の確認によい問題です
atcoder.jp

解説

コインをN回投げます。表がK回でる場合の数を求めなさい

中学受験ですね。 N個の物からK個選ぶ場合の数と同じなので {} _ N \mathrm{C} _ K通り
これを形式的べき級数を用いて考えると
 (1+x) ^ N の x ^ K の項
となります。
ここで、1は裏、xは表に対応しています
でもってxをK回選ぶとx ^ Kの項になる、二項定理の基本的な考え方です

サイコロをN回投げます。出た目の和がKである時の場合の数を求めなさい

受験を思い出す問題ですが、これ受験に出したらまずそう()、そんな問題です
これは形式的べき級数を使わないと表すのが面倒くさいです
結論から言うと(x+x ^ 2+ x ^ 3+x ^ 4+x ^ 5+ x ^ 6) ^ N のx ^ Kの項が答えです
これはaの目とbの目とcの目が出た時、和がa+b+cになる事を、
 x ^{a+b+c} = x ^ a \times x^ b \times x ^ cであることを用いて表しています

サイコロをN回投げます。出た目の和がKである確率を求めなさい

前問の式に\frac{1}{6 ^ N}を掛けてあげるだけです、
 \frac{(x+x ^ 2+ x ^ 3+x ^ 4+x ^ 5+ x ^ 6) ^ N}{6 ^ N}=(\frac{x}{6}+\frac{x ^ 2}{6}+ \frac{x ^ 3}{6}+\frac{x ^ 4}{6}+\frac{x ^ 5}{6}+ \frac{x ^ 6}{6}) ^ N
と出来るので、今後各項に \frac{1}{6}を掛けた式を使っていきます

サイコロをN回投げます。出た目の和の和の期待値を求めなさい

いよいよ期待値に入って行きます!
出た目の和の確率分布はf(x)=(\frac{x}{6}+\frac{x ^ 2}{6}+ \frac{x ^ 3}{6}+\frac{x ^ 4}{6}+\frac{x ^ 5}{6}+ \frac{x ^ 6}{6}) ^ Nで表せる事を前問で確認しました
 f(x)=\sum _ {i=0} ^ {\infty}A _ i x ^ iと置くと、
求めたいものは  \sum _ {i=0} ^ {\infty} i \times A _ iになります
これをは普通に掛けていってもいいのですが  f'(x)=\sum _ {i=0} ^ {\infty}i \times A _ i x ^ {i-1}であることに注目すると、
f'(1)即ち ( (\frac{x}{6}+\frac{x ^ 2}{6}+ \frac{x ^ 3}{6}+\frac{x ^ 4}{6}+\frac{x ^ 5}{6}+ \frac{x ^ 6}{6}) ^ N)'(1)が求めたい期待値であることがわかりました!!!

期待値の和は和の期待値であることを形式的冪級数を用いて確認しなさい

実は前問、こんな複雑なことをせずとも、
1回あたりの期待値が \frac {7}{2} = \frac{(1+2+3+4+5+6)}{6}なので \frac {7}{2} \times Nで十分です...
なぜなら期待値の和は和の期待値だからです...
期待値の和は和の期待値であることの説明はここにあります
mathtrain.jp
これが成り立つ事を形式的冪級数を用いて確認したいです
期待値の和は和の期待値であることの証明はしません
形式的冪級数で表せない事象においても期待値の和は和の期待値であるので、不可能です
では、行きます
確率母関数がf(x)である事象と確率母関数がg(x)である事象、それぞれの期待値は先程と同様にf'(1)g'(1)なので その和、即ち期待値の和はf'(1)+g'(1)です
一方、形式的冪級数の性質から、f(x)g(x)は両者の和の母関数になります
なので、和の期待値は(f \times g)'(1)=f(1)g'(1)+f'(1)g(1)です
ここでf'(1)+g'(1) \neq f(1)g'(1)+f'(1)g(1)に見えますが、
期待値の和は1なのでf(1)=g(1)=1であり、
そのためf'(1)+g'(1) = f(1)g'(1)+f'(1)g(1)が成り立ちます
よって少なくとも確率母関数がf(x)である事象と確率母関数がg(x)である事象の間に期待値の和=和の期待値の関係を確認できました

N回振った時サイコロを出た目の和がK以上になる確率を求めなさい

上に上げたmaspyさんの記事を読んでるとわかりやすいです まず、N回振った時サイコロを出た目の和がKである確率が(\frac{x}{6}+\frac{x ^ 2}{6}+ \frac{x ^ 3}{6}+\frac{x ^ 4}{6}+\frac{x ^ 5}{6}+ \frac{x ^ 6}{6}) ^ Nx ^ Kの項であることを上で確認しました これを使うと、 \sum _ {n=0} ^ {\infty} A _ n x ^ n=(\frac{x}{6}+\frac{x ^ 2}{6}+ \frac{x ^ 3}{6}+\frac{x ^ 4}{6}+\frac{x ^ 5}{6}+ \frac{x ^ 6}{6}) ^ Nとおいた時、
1 - \sum _ {i=0} ^ {K} A _ iが N回振った時サイコロを出た目の和がK以上になる確率になることがわかりますが、
なんと、\sumを取り除く事ができます
ここで唐突に、f(x)=sum _ {n=0} ^ {\infty} A _ n x ^ nとした時の、f(x) \times (1+x+x ^ 2+x ^ 3 +...)x ^ Kの項を考えます
すると丁度\sum _ {i=0} ^ {K} A _ iになる事が分かるので、  \frac{1}{1-x}=1+x +x ^ 2+x ^ 3+...に注意すると 1-( \frac { (\frac{x}{6}+\frac{x ^ 2}{6}+ \frac{x ^ 3}{6}+\frac{x ^ 4}{6}+\frac{x ^ 5}{6}+ \frac{x ^ 6}{6}) ^ N}{1-x}のx ^ Kの項)が答えになる事がわかります

サイコロを出た目の和がK以上になるまで振った時の振った回数の期待値を求めなさい

最終問題です
これも形式的冪級数でかけます
N回振った時サイコロを出た目の和がK以上になる確率を使って、
 \sum _ {N = 0} ^ {\infty} N \times ( (N回振った時サイコロを出た目の和がK以上になる確率)\\ -(N-1回振った時サイコロを出た目の和がK以上になる確率) ) \\
= \sum _ {N = 0} ^ {\infty} (N回振った時サイコロを出た目の和がK未満になる確率)\\
=  \sum _ {N = 0} ^ {\infty} \frac{( \frac{x}{6}+\frac{x ^ 2}{6}+ \frac{x ^ 3}{6}+\frac{x ^ 4}{6}+\frac{x ^ 5}{6}+ \frac{x ^ 6}{6}) ^ N}{(1-x)}\\
=( \frac {1}{(1-x)(1-( \frac{x}{6}+\frac{x ^ 2}{6}+ \frac{x ^ 3}{6}+\frac{x ^ 4}{6}+\frac{x ^ 5}{6}+ \frac{x ^ 6}{6}) )} )のx ^ Kの項\\
=\frac {6}{6 - 7 x + x ^ 7}のx ^ Kの項
これが答えになります
求まった!!!!

終わりに

いかがでしたでしょうか、最初は競プロやってない人向けにもわかりやすく書くつもりでしたが、最後のだけなんだかんだで難しくなってしまいました
形式的冪級数、こねこねしてるだけで楽しいので、皆もこねこねしてみてね
明日は53代はしどいさんの「君はイージングを知っているか!?」です
イージングとは何でしょうか!?
今から楽しみですね!