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

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

解説

コインを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}) ^ N$ の $x ^ 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代はしどいさんの「君はイージングを知っているか！？」です
イージングとは何でしょうか！？
今から楽しみですね！

MIS.W 公式ブログ

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

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

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

解説

終わりに