破産確率の正確な計算

破産確率の問題です

１円払ってサイコロを振って
１の目が出たら０円
２の目が出たら０円
３の目が出たら０円
４の目が出たら０円
５の目が出たら５円
６の目が出たら６円 をそれぞれ貰えるとします。

この時、手持ち金額ｘ 目標金額をＡ円とした時の破産確率を求めよ。
離散版（SDI以外）の回答で宜しくお願いします。

補足 この類は確率微分方程式（ウイーナー過程に近似）で容易に解けますが、
マルコフ連鎖での解とは結構なズレを生じます。
特にｘ＝１付近・ｘ＝Ａ－１付近です。
マルコフ連鎖で正確な解析解が出ますが、サイコロの次元数が増えると
（出目の数が１万次元）メモリー不足に陥ります。

マルコフ以外の＜近似しない解法＞をご存知の方が居るなら教えてください。

離散マルチンゲールが、その高速解法となると思いますが、
見本関数の算出・処理方法がわかりません。
伊藤差分方程式から算出してもｔを消せません。

やりたい事は、次元数を増やした場合の高速正確な計算です。
宜しくお願いします。

No.1 回答者： gef00675 回答日時： 2009/03/09 23:36

離散マルチンゲールによる解ではないので、お望みの回答になってないかもしれませんが。

。。
破産確率の差分方程式を、単純に次のようなガウス・ザイデル的な方法で計算してみました。
Pを添字範囲0から(A+6)の配列（破産確率）とし、
A=目標金額
P(0)=1
P(A)=P(A+1)=P(A+2)=P(A+3)=P(A+4)=0として、
すべてのP(x)が収束するまで次を繰り返す
　k=1からA-1に渡って次を繰り返す
　　P(k)←P(k-1)*4/6+P(k+4)/6+P(k+5)/6
このような方法でも割と早く収束するし、１次元配列しか使っていないのでサイコロの出目の数を１万に増やした程度ではメモリー不足にはなりません。むしろ、P(x)の計算途中にアンダーフローして0になってしまう可能性があることの方が問題です。その場合、P(x)のスケールをうまく調整してやる必要があるでしょう。
　yahooのほうに差分方程式の特性根を利用した厳密解を書き足しておきましたが、出目の数が１万になると特性根の絶対値が１０のマイナス何百乗とかになってくるので、よほど数値計算に通じてないと、普通にプログラムしたのでは無理ですね。「近似しない」「高速解法」には違いないのですが。
参考にならなければごめんなさい。

この回答への補足

色々ありがとうございます_(..)_
ご指摘の件、解法の一つとして候補に入れさせていただきます。
この問題は解決が簡単ではない事がわかっただけでも大収穫でした。

離散数学は実に面倒ですね　^^;　数学の穴と言えるかもしれません。
知っている人は知っている？　余り要求度は高くないのかもしれません。

統計数理研究所の公開論文も一応全部チェックしましたが、
それらしき件を取り扱っている論文がありません。

この種を扱っていそうな物でspringer本を調べた所
Discrete Gambling and stochastic Games なる物と
一橋の藤田岳彦氏の書いたランダムウオークと確率解析を見つけ読んでみると次元数は１のみ。
どちらもアイデアに富む稀に見る良書なので隅々読むとヒントはあるかもしれませんが

差分方程式も似た問題が発生する様ですし、あと思い付くのは他拘束条件を盛り込み
パラメーター変換（ラプラスetc）で測度変換してパラメーター１個に持ち込んで、
そこでマルチンゲールを考えています。

結局マルコフ連鎖の巨大行列を解くネットワーク連携計算システム
でも構築しないと問題は正確には解決しませんがMatlabでもう少し
境界周辺の漸近特性改善を研究する必要があると言うのが分かっただけでも収穫でした。

とにかくどの方法を使ってもコンピュータの計算過程上で問題が起こりやすく、
しかも都合よく正確な値を出すマルチンゲールの式は無いのかもしれません　^^;

補足日時：2009/03/27 10:44