Grenache's blog

競技プログラミング初心者です。

カテゴリ: 期待値

問題概要

問題文はこちらを参照してください。

試行回数の期待値を求める問題で、漸化式の右辺に先の項が現れて、単純にボトムアップのループで解けない問題です。

解法

基本的な考え方はyukicoder No.65と同じです。ただ、合計がちょうど$K$にならないといけないので、$K$を超えたときの期待値が、$\mathrm{E}[X_0]$になります。つまり、下記のような漸化式になります。

漸化式の定義: $$dp[i]=1+dp[i+1]\cdot \frac{1}{6}+dp[i+2]\cdot \frac{1}{6}+...+dp[i+6]\cdot \frac{1}{6}$$

$dp[i]$:これまでの目の合計が$i$のとき、合計が$K$になるまでに振ることになる回数の期待値$(0\le i \le K)$

初期値:$dp[K]=0,\ \underline{dp[i]=dp[0](i\gt K)}$

求める解:$dp[0]$

この漸化式だと$i=K-1$の時に、$dp[K-1]=1+dp[K]\cdot \frac{1}{6}+dp[0]\cdot \frac{5}{6}$となって、この時点で$dp[0]$が出てくるので、単純にDPで$dp[K-1]$を求めることができません。つまりこれは、$K$個の未知数($dp[0],\ dp[1],...,dp[K-1]$)を$K$個の式から求める連立一次方程式になります。

しかし、この問題の場合は連立一次方程式を解かなくても解く方法があります。

1.漸化式で解く方法

単純なDPでは解けないといいましたが、$dp[K-1]$は$dp[0]$で表され、$dp[K-2]$は$dp[K-1],\ dp[0]$で表されて、結局$dp[i]=a_i\cdot dp[0]+b_i$と表されます。つまり、次の漸化式を解いて、最後に$dp[0]=a_0\cdot dp[0]+b_0$という$dp[0]$に関する一次方程式を解けば、解が得られます。

漸化式の定義: $$\begin{eqnarray} a_i & = & a_{i+1}\cdot \frac{1}{6}+...+a_{i+6}\cdot \frac{1}{6}\\ b_i & = & 1+b_{i+1}\cdot \frac{1}{6}+...+b_{i+6}\cdot \frac{1}{6} \end{eqnarray}$$

$a_i,\ b_i$:$dp[i]=a_i\cdot dp[0]+b_i$と表されると考えたときの係数

初期値:$a_K=0,\ b_K=0,\ a_i=1(i\gt K),\ b_i=0(i\gt K)$

求める解:$a_0,\ b_0$

2.二分探索で解く方法

$dp[0]=x$と仮の値を使って、$dp[K-1],\ dp[K-2],…,dp[0]$をDPのように求めていって、得られた$dp[0]$を$f(x)$とします。すると、$x=f(x)$となる$x$を求める問題と考えることができます。$x-f(x)$は単調増加な関数なので、これは$x$を二分探索で求めることもできます。$f(x)$を求めるのに$O(K)$なので、問題ありません。

ところで、二分探索の探索範囲はどのくらいに見積もるべきなんでしょうか?下限は0ですが、上限をどの程度にすればよいのかの根拠がわかりません。また、$x-f(x)$と$f(x)-x$のどちらが単調増加なのかってすぐわかるもんなんでしょうか?1.の方法の式まで考えると、$x-f(x)$が単調増加だと分かるのですが、すぐにはわかりませんでした。今回はいずれも適当にやってみて決めることができますが、本番ではそこまでなかなか考えられません。。。

考察

いろいろな解説を読んでじっくり考えて、やっとなぜ二分探索で求めることができるのかがわかりました。ほかにもガウス・ザイデル法やガウス・ジョルダン、モンテカルロ法を使ってもできるという解説もありました。コンテスト時間内にこれだけのことを考えるのはとても無理な気がしています。。。

問題概要

問題文はこちらを参照してください。

試行回数の期待値を求める基本問題です。いわゆるコンプガチャの期待値の問題で、回数の期待値を求める問題があることを知りました。

解法

試行回数の期待値を求める問題では、ある状態から1回の試行によって遷移する状態の期待値との漸化式を立ててそれを動的計画法で解くことになります。基本的には、下記の式の形になるようです。

$$\mathrm{E}[Z]=1+\mathrm{E}[Z_1]\cdot p_1+\mathrm{E}[Z_2]\cdot p_2+...+\mathrm{E}[Z_n]\cdot p_n$$

$Z$の状態から、1回の試行によってそれぞれ$p_i$の確率で$Z_i$の状態に遷移する場合。

ここではなぜ上記の式になるのかを考えるため、確率変数の定義とその確率分布を意識していきたいと思います。

$X_i$:これまでの目の合計が$i$のとき、合計が$K$になるまでに振ることになる回数

このように考えると、求める期待値は$X_0$の期待値、$i\ge K$のときすでに$K$を超えているので、$\mathrm{E}[X_i]=0$となります。

ここで、これまでの目の合計が$i$の時に次に振るさいころの目が$1$であると仮定した場合の$X_i$の期待値を考えると、目の合計が$i+1$の時の期待値に$1$が出た試行1回を足したものになります。これは$X_i$の条件付き期待値と呼ばれるもので、式で表すと次のようになります。

$$\mathrm{E}[X_i|Y=1]=1+\mathrm{E}[X_{i+1}]$$

$Y$:これまでの目の合計が$i$のとき、次に振るさいころの目の値

同様にその他の目が出た時を考えると、次の確率分布を満たすような確率変数$\mathrm{E}[X_i|Y]$を定義することができます。

$\mathrm{E}[X_i|Y]$ $\scriptsize 1+\mathrm{E}[X_{i+1}]$ $\scriptsize 1+\mathrm{E}[X_{i+2}]$ $\scriptsize 1+\mathrm{E}[X_{i+3}]$ $\scriptsize 1+\mathrm{E}[X_{i+4}]$ $\scriptsize 1+\mathrm{E}[X_{i+5}]$ $\scriptsize 1+\mathrm{E}[X_{i+6}]$ 合計
確率 $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ 1

ここで、条件付き期待値には$\mathrm{E}[\mathrm{E}[X_i|Y]]=\mathrm{E}[X_i]$という式が成り立つとのこと。したがって、$X_i$の期待値は$\mathrm{E}[X_i|Y]$の期待値を求めればよく、これは期待値の定義より下記になります。

$$\begin{eqnarray} \mathrm{E}[X_i] & = & \mathrm{E}[\mathrm{E}[X_i|Y]] \\ & = & (1+\mathrm{E}[X_{i+1}])\cdot \frac{1}{6}+(1+\mathrm{E}[X_{i+2}])\cdot \frac{1}{6}+...+(1+\mathrm{E}[X_{i+6}])\cdot \frac{1}{6} \\ & = & 1+\mathrm{E}[X_{i+1}]\cdot \frac{1}{6}+\mathrm{E}[X_{i+2}]\cdot \frac{1}{6}+...+\mathrm{E}[X_{i+6}]\cdot \frac{1}{6} \end{eqnarray}$$

例えば、$\mathrm{E}[X_{K-1}]=1+\mathrm{E}[X_{K}]\cdot \frac{1}{6}+\mathrm{E}[X_{K+1}]\cdot \frac{1}{6}+...+\mathrm{E}[X_{K+5}]\cdot \frac{1}{6}$となり、$i\ge K$のとき$\mathrm{E}[X_i]=0$より、$\mathrm{E}[X_{K-1}]=1$です。

漸化式にて$\mathrm{E}[X_{i}]$を$\mathrm{E}[X_{i+1}]~\mathrm{E}[X_{i+6}]$にて定義できているので、DPで$i$を$K-1$から$0$のループを回すことで$\mathrm{E}[X_{0}]$を求めることが可能です。

結局、動的計画法の問題としてまとめると下記のようになります。

漸化式の定義: $$dp[i]=1+dp[i+1]\cdot \frac{1}{6}+dp[i+2]\cdot \frac{1}{6}+...+dp[i+6]\cdot \frac{1}{6}$$

$dp[i]$:これまでの目の合計が$i$のとき、合計が$K$になるまでに振ることになる回数の期待値$(0\le i \le K)$

初期値:$dp[K]=0,\ dp[i]=dp[K](i\gt K)$

求める解:$dp[0]$

考察

条件付き期待値に関する情報は少なめだったので、最初の式をなかなか理解することができませんでした。結局このような形で、理解したつもりになっています。

問題概要

問題文はこちらを参照してください。

期待値の線形性を使うと簡単な問題です。

解法

1個のサイコロで考えると、問題文中にあるように期待値の定義$\displaystyle \mathrm{E}[X]=\sum_{x}x\cdot \Pr\{X=x\}$を使って計算できます。

求める期待値の確率変数を定義します。

$X$:1個のサイコロを振って出る目

$X$の確率分布を表で表します。

出る目の数$X$ 1 2 3 4 5 6 合計
確率 $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ 1

したがって、1個のサイコロを振って出る目の期待値は $$\mathrm{E}[X_i]=1\cdot \frac{1}{6}+2\cdot \frac{1}{6}+3\cdot \frac{1}{6}+4\cdot \frac{1}{6}+5\cdot \frac{1}{6}+6\cdot \frac{1}{6}=\frac{21}{6}=3.5$$ となります。

次に、この問題で求める期待値の確率変数を定義します。

$Y$:n個のサイコロを振って出る目の合計

ここで、

$X_i$:i番目のサイコロの出る目

と定義すると、確率変数$Y$は$X_i$の和で表すことができます。 $$Y=X_1+X_2+...+X_n$$

このように求めたい期待値の確率変数を、別の確率変数の和で表すということを考えると、期待値の線形性を用いることができます。求めたい$Y$の期待値$\mathrm{E}[Y]$は下記のようになります。 $$\mathrm{E}[Y]=\mathrm{E}[X_1+X_2+...+X_n]=\mathrm{E}[X_1]+\mathrm{E}[X_2]+...+\mathrm{E}[X_n]$$ $\mathrm{E}[X_i]$は上記で求めた「1個のサイコロを振って出る目の期待値」と何ら変わりはないので、$\mathrm{E}[Y]=n\cdot \mathrm{E}[X]=n\cdot 3.5$となります。

考察

期待値の線形性を知ったときは目からうろこで、とても感激しました。ただ、これは高校時代に数学で習ったはずのことで、完全に忘れてしまっていたようです。。。

ちなみにこの問題を期待値の定義を使って解こうとすると下記のような感じになるのでしょうか。

$Y$:n個のサイコロを振って出る目の合計

これの確率分布を表で表すと

出る目の合計$Y$ n n+1 n+2 ... 6n-1 6n 合計
確率 $\frac{1}{6^n}$ $\frac{n}{6^n}$ $\frac{???}{6^n}$ ... $\frac{n}{6^n}$ $\frac{1}{6^n}$ 1

のようになります。この確率を求める公式もあるようですが、理解できませんでした。nが小さければ、全探索で計算することもできるようです。でも、期待値の線形性を知っていれば簡単という典型問題です。

このページのトップヘ