ブロックの積み上げ問題2
　コインをを投げて表が出たらブロックを1段積み上げ裏が出たら既に積んであるブロックから1段取り去る。0段の状態で裏が出たらもう一度コインを投げる。
コインをN回投げた時に初めてM段目に到達する確率を求めよ。（表の出る確率＝ｐ,裏の出る確率＝ｑ）

　母関数で求める。
まず、0段の状態からスタートしてNステップで初めて1段目に到達する確率についての母関数を求めます。これは、ブロックの積み上げ問題1で出てきた次式、
です。ここでは、この母関数を新たにG0（ｓ）とします。
次に、1段の状態からスタートしてNステップで初めて2段目に到達する確率についての母関数を求めます。この母関数をG1（ｓ）とします。
1ステップ後には、確率ｐで2段目に到達し確率ｑで0段目に移動します。したがってこの母関数は、
　

となり、この方程式を解くととなります。
上述議論と同じ様にK-1段の状態からスタートしてNステップで初めてK段目に到達する確率についての母関数の漸化式も求めることができ、
となります。

実際に、この式のG0（ｓ）にを代入し分母と分子に1-ｑｓを掛けると、


G2では、

G3（ｓ）では、


この計算をすると、となっていることが分かります。
ここで、関数ｆ1（ｘ）を次のように定めます。ｆ1（ｘ）＝1（ｘ＝全ての整数）、さらにｆi（ｘ）をと定めます。
すると次の関係が成り立ちます。　　ｆ1（ｘ）の場合この関数の定義によりこの式の正しいことが分かります。
さらに、ｆi-1（ｘ）に対して任意の整数ｘを代入した場合と、ｆi（ｘ）に対して1からｋ-1の整数ｘを代入した場合にこの式が成り立つと仮定します。
ｆi（ｘ）の定義と帰納法の仮定により、したがって、ｆi(x)でも成り立つことが分かります。

Gｎの分母はmが偶数の場合(m＞2）
、

となり、であるため


mが奇数の場合、

となり、であるため


そして、状態0からスタートしてNステップ後に初めてM段目に到達する確率についての母関数は、G0（ｓ）、G1（ｓ）、G2（ｓ）、、、GM-1（ｓ）の積
G0（ｓ）×G1（ｓ）×G2（ｓ）×、、、×GM-1（ｓ）によって求まります。Gi（ｓ）(i＝0～m）の積は以下のようになります。

mが偶数の場合

隣り合った項の分母と分子が相殺するためにこの式は次のようになります。

mが奇数の場合

こちらも隣り合った項の分母と分子が相殺するために次のようになります。



したがって、状態0からスタートしてNステップ後に初めてM段目に到達する確率についての母関数は
M-1が偶数の場合

M-1が奇数の場合

となり、状態0からスタートしてNステップ後に初めてM段目に到達する確率は、この母関数をN回微分しN！で割りSに0を代入した値となります。


　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　トップページへ