可変順序マルコフ連鎖の効率的表現

Question

a（固定次数）マルコフ連鎖は、遷移確率でラベル付けされたエッジを持つ有限状態オートマトンと考えることができることを思い出してください。

したがって、二次マルコフ連鎖の遷移は、フロート値が目標状態に関連付けられた遷移確率を表すマップ

trans2: (State,State) -> List[(State,Float)] 

とみなすことができます。可変次数ケースに明白なやり方でこれを拡張

が与える：

transN: List[State] -> List[(State,Float)] 

しかし、いくつかの入力リスト（STATE1、...、stateM）のためにこのマッピングの実装は、すべてのLHSエントリを見つけることが必要です（必ずしも適切ではない）プレフィックスである遷移テーブル内のリスト（state1、...、stateM）に含まれる。

Q.州の数が大きいとすれば、どのような表現が良いでしょうか？

Answer 1

可変長マルコフ連鎖（VLMC）の効率的な表現は、確率的接尾辞ツリー（PST）である。たとえば Rパッケージについての記事[1]をご覧ください。

[1]：Gabadinho、A. and Ritschard、G.（2016）。確率的接尾辞ツリーによる状態シーケンスの分析：PST Rパッケージ。 統計ソフトウェア、72（3）、1-39のジャーナル。 https://www.jstatsoft.org/article/view/v072i03