マルコフ連鎖：端末状態計算を見つける

Question

私はこの問題を解明しようとしています。うまくいけば、誰かがこれを完了する方法を教えてくれるでしょう。私は次のページを参考にしましたが、正しい出力を生成し、すべてのテストケースを渡すコードをjava/pythonで書くことができませんでした。私は何かすべての助けに感謝します。その状態が次の状態に行って、それぞれのためにintの配列を返した回数を表す非負intの配列の配列を受け取り

Markov chain probability calculation - Python

Calculating Markov chain probabilities with values too large to exponentiate

機能応答（m）を書きますそれぞれの状態の分子として表される各端末状態の正確な確率を与え、最後にそれらのすべての分母を最も簡単な形で与える。マトリックスは10以下である。鉱石がどの状態にあるかに関わらず、その状態から末端状態への経路が存在することが保証される。すなわち、処理は常に最終的に安定した状態で終了する。鉱石は状態0から始まります。分母が規則的に単純化されている限り、分母は計算中に符号付き32ビット整数に収まります。例えば は、行列m考える：

[ 
[0,1,0,0,0,1], # s0, the initial state, goes to s1 and s5 with equal probability 
[4,0,0,3,2,0], # s1 can become s0, s3, or s4, but with different probabilities 
[0,0,0,0,0,0], # s2 is terminal, and unreachable (never observed in practice) 
[0,0,0,0,0,0], # s3 is terminal 
[0,0,0,0,0,0], # s4 is terminal 
[0,0,0,0,0,0], # s5 is terminal 
] 

    So, we can consider different paths to terminal states, such as: 

    s0 -> s1 -> s3 

    s0 -> s1 -> s0 -> s1 -> s0 -> s1 -> s4 

    s0 -> s1 -> s0 -> s5 

    Tracing the probabilities of each, we find that 

    s2 has probability 0 

    s3 has probability 3/14 

    s4 has probability 1/7 

    s5 has probability 9/14 

Answer 1

私はエッジケースの結果がどうあるべきかわからないが、私はこの問題のためにやったことです：第2のマトリックスを作成し

1. これは、各列のすべての分子を合計することによって、各確率に対してすべての分母を保持する。
2. 行列内の最初の終端状態を非終端状態の境界として使用します。
3. 同じサイズの単位行列から第1の端子によって境界付けられた行列を減算する。
4. 差の逆数を求めます。これを行うにはいくつかの方法があります。違いを使って一致する単位行列を増やすことにしました。
5. 逆行列に、最初の端子から行列の終わりまでの行列を掛けます。
6. 次に、結果として得られた分母を見つけて、最初の端末から境界にある行列の分子の最初の行を行列の終わりに戻します。

サイドノートは：

• あなたは（あなたも、あなたが簡素化し、GCFおよびLCM関数を記述する必要があるかもしれません）画分を簡素化簡素化関数を記述する必要があります。
• ターミナルが行列の最後にあるように、適切な形式で並べ替える必要があります。
• エッジケース：1x1マトリックス、1つの非終端状態のみを有するマトリックス、10x10マトリックス、1末端状態のみを有するマトリックス