確率・期待値に関する疑問です。

質問

問：「1～ｍ（ｍは整数の定数）までの数字がかかれたカードが、それぞれ一枚ずつある。
これらのカードを箱の中に入れておく。一回の試行で箱の中からカードを一枚取り出し、数字を確認した後、再び箱へ戻すものとする。

このとき、有限回（ある程度大きい数）試行を行い、最後の試行で取り出したカードの数字を得点とするとき、より高い得点を得るにはどうしたらよいか。

ただし、試行は最後の試行の回数以内であればいつでもやめてよいものとする。」

この問に関して、ある先生は、サイコロに置き換えて考えて期待値を求め、試行の回数を多くしていき、これを一般化して期待値の漸化式、

Ｅ(n+1)＝{m(m+1)/2－[Ｅ(n)](Ｅ(n)＋1)/2＋[Ｅ(n)]×Ｅ(n)}/m

（Ｅ(n)・Ｅ(n+1)は期待値、[Ｅ(n)]は期待値のガウス記号です。）

を導きだしたそうですが、この先に進めず、迷っているそうです。

この問いを一般化することについて、何か解法や解くためのヒントを思いついた方は、何でもいいので是非回答よろしくお願いします。

合わせて漸化式の解法についても、よろしくお願いします。

回答No.2

Quattro99

知りたいのは、より高い得点を得るにはどうしたらよいかを考え、それを実行したときの期待値ということですか？

補足

要はそういったことなのですが、補足に示した通り、それを考えていった結果がその漸化式なのだそうです。

よろしくお願いします。

回答No.1

Quattro99

残り回数でいくつ期待できるかを計算し、それよりも大きいカードを引いたらやめるということになるのではないでしょうか。
例えば、残り1回になったら、最後の回で引くカードの期待値は(m+1)/2ですから、それよりも大きいカードを引いていればやめます。
従って、n回引いた場合の最大値の期待値を計算できればよいことになると思います。

期待値はたぶん、m-{(Σ_[k=1,m-1]k^n)/m^n}なので、これより大きいカードを引いたらやめればいいのではないかと思います。

補足

ご回答ありがとうございます。

今日その先生に再び話を伺ったところ、

「正n面体のサイコロで考える。
k回目の目をＸkとおくと、

Ｘ1≦ｍ1なら続行、Ｘ1≧ｍ1＋１ならやめる。

続行した時、
Ｘ2≦ｍ2なら続行、Ｘ2≧ｍ2＋１ならやめる。

続行した時、………」

というふうに、続行するかやめるかの基準となる数値をｍと置いて考えていくのだそうです。

また、

「６面の普通のサイコロで考えると、試行の回数が最大２回の時、

ｍ1＝３なので（１回目の試行で６が出た時は、当然そこで試行を終了。１、２、３が出た時は、より高い得点を得るためにはもう一度試行した方がよい）、

Ｅ＝1/6×(4＋5＋6)＋3/6×1/6×(1＋2＋3＋4＋5＋6)

最大３回の時、

ｍ1＝４、ｍ2＝３なので（２回の時と同じ考え方で、地道に計算して出したそうです）、

Ｅ＝1/6×(5＋6)＋4/6×1/6×(4＋5＋6)＋3/6×1/6×(1＋2＋3＋4＋5＋6)

……

最大７回の時、

ｍ1＝５、ｍ2＝４、ｍ3＝４、ｍ4＝４、ｍ5＝４、ｍ6＝３、となるそうです。（一回目で６以外の目が出たとき、残りまだ６回あるので、６の目が出る可能性は十分あるから、などを考えているそうです）

こうやって考えていった時、Ｅを最大とするｍ1、ｍ2、ｍ3、………をさがしていくことで、先に述べた「最大期待値」の漸化式が得られるそうです。

最初の質問内容とズレるかもしれませんが、先生の話によると、どんな考え方であれ、その漸化式にたどり着くらしいので、厚かましくて申し訳ありませんが、今度は漸化式の解法についてご一考をいただけないでしょうか？

長々とすみませんが、それだけ私はこの疑問を解決したいのです。私ももっと考えてみますので、是非よろしくお願いします。