ブロック積み上げの問題1

　コインを投げ表が出たらブロックを一段積み上げ、裏が出たら既に積んであるブロックを全て取り去る。0段の時（ブロックがない時）は、もう一度コインを投げる。N回目に初めてブロックの高さがM段に到達する確率は？(表の出る確率＝ｐ,裏の出る確率＝ｑとする。）
解.確率母関数を使って求める。
まずM＝1の場合.

　　この母関数をM1（ｓ）とする。

M=2の場合.
N回目に初めて2段目に到達するためには、K回目（N＞K）に初めてブロックの高さが1に到達する必要がある。その次のステップでは、確率ｐで高さ2に到達する場合と確率ｑで振り出しに戻る場合がある。前者の場合の母関数は、ｐｓ・M1（ｓ）であり、後者の場合の母関数は、ｑｓ・M1（ｓ）である。さらに、後者の
場合では、L回目（N＞L＞K+1）にもう一度1段目に到達し、その次のステップで確率ｐで高さ2に到達する場合と確率ｑで振り出しに戻る場合がある。以下このような過程が無限につづく。結局、M=2の場合の母関数は、

となる。この母関数をM2とする。
M=Kの場合.
上述のように母関数Mｋは、Mｋ-1を使った漸化式から得られ

問題のN回目に初めてM段目に到達する確率は、この初項公比の無限等比数列のの係数を求めれば分かります。

では、この数列の第ｒ項のの係数を求めてみましょう。
それには左の式を展開した時の（ｔ＝N-ｋ）の係数を知る必要があります。
の係数は、×（ｒ個のｋ面体のサイコロを振り、それらの目の和がｔとなる場合の数）となります。
ｒ個のｋ面体のサイコロを振り、それらの目の和がｔとなる場合の数は、次の式で表現されます。[（ｔ-ｒ）/ｋ]は（ｔ-ｒ）をｋで割ったとき、小数点以下を切り捨てた整数値です。
したがって問題の解は、となります。
この問題を解くにあたって用いた母関数は他の方法によっても導くことができます。
（N-（M-1））～N回目まではコインの表がでて、1～（N-M）回目までは（裏）、（表裏）、（表表裏）、（表表表裏）、、、、（表×（M-1）裏）の組み合わせです。
例えば、これら要素の2個の組み合わせで4ステップを作れば（裏）（表表裏）と（表表裏）（裏）と（表裏）（表裏）があり3個の組み合わせで4ステップを作れば
（裏）（裏）（表裏）と（裏）（表裏）（裏）と（表裏）（裏）（裏）があります。結局ｒ個の要素でのｔステップの作り方が何通りあってその確率がどれほどかを求めるには、この式の展開式のの係数を調べればよいということになります。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　トップページへ