数学では無限級数などの無限要素が存在する。計算機は無限回の計算ができないため、工夫をして有限回の計算で極限を求める必要がある。
期待値の計算
期待値の性質
P(X), P(Y)が
非独立でも独立でも、 P(X+Y) = P(X) + P(Y)
独立な場合に限り、P(XY) = P(X)P(Y)
非独立でも独立でも、 P(X+Y) = P(X) + P(Y)
独立な場合に限り、P(XY) = P(X)P(Y)
確率変数が無限大に発散する場合
状態遷移に不変遷移（引き分け）が含まれる場合、確率変数が無限大に発散してしまうため、期待値の定義式から直接期待値を求めることができない。
このような場合、不変遷移を無視して考えた遷移確率と、補正した確率変数（回数など）を用いることで、期待値を定義式から求めることができる。
このような場合、不変遷移を無視して考えた遷移確率と、補正した確率変数（回数など）を用いることで、期待値を定義式から求めることができる。
確率変数の補正について、不変遷移が発生する確率をp、不変遷移を無視して考えた時の確率変数をxと書くと、補正後の確率変数はx/(1-p)となる。
x=1の場合の例として、確率pで裏が出るコインを表が出るまで投げ続けるとき、投げる回数の期待値Eを求めることを考える。
この時、期待値の定義式と期待値の意味を考えることで
E=(1-p)*1 * p(1+E)
が成り立つことがわかる。これを変形すると
E=1/(1-p)となる。
(最初に出る面で場合分けをし、最初に裏が出た後の遷移回数をを期待値を用いて表すことで無限個の項を無くしている。)
x=1の場合の例として、確率pで裏が出るコインを表が出るまで投げ続けるとき、投げる回数の期待値Eを求めることを考える。
この時、期待値の定義式と期待値の意味を考えることで
E=(1-p)*1 * p(1+E)
が成り立つことがわかる。これを変形すると
E=1/(1-p)となる。
(最初に出る面で場合分けをし、最初に裏が出た後の遷移回数をを期待値を用いて表すことで無限個の項を無くしている。)
例１ ABC78 C(300)
不変遷移を無視すると、
正解する確率は(1/2)^M/(1/2)^M = 1
確率変数は{100(N-M)+1900M}* 1/(1/2)^M =={100(N-M)+1900M}* 2^Mとなるので、求める期待値は
1*{100(N-M)+1900M}* 2^M
正解する確率は(1/2)^M/(1/2)^M = 1
確率変数は{100(N-M)+1900M}* 1/(1/2)^M =={100(N-M)+1900M}* 2^Mとなるので、求める期待値は
1*{100(N-M)+1900M}* 2^M
例２ M-SOLUTIONS C(500)
不変遷移を無視すると、確率はそれぞれa/100→a/a+b, b/100→b/a+bとなる。また、確率変数n(回数)を補正すると n→(100*n/(a+b) )となる。
以上の値を用いた期待値の定義式から期待値を計算すればよい。
(解説PDFの式は誤植があって怪しいので注意)
以上の値を用いた期待値の定義式から期待値を計算すればよい。
(解説PDFの式は誤植があって怪しいので注意)
Writer:Sen,Hyado
