可变阶马尔可夫链的有效表示
Efficient representation for variable-order Markov Chain
回想一下，（固定顺序）马尔可夫链可以被视为有限状态自动机，其边缘由转移概率标记。
因此，二阶马尔可夫链中的转换可以视为映射
trans2: (State,State) -> List[(State,Float)]
其中浮点值表示与目标状态关联的转移概率。
以明显的方式将其扩展到可变顺序的情况给出：
transN: List[State] -> List[(State,Float)]
但是，为某些输入 List(state1, ..., stateM ) 实现此映射需要在转换 table 中找到所有 LHS 条目，它们是 List 的（不一定正确的）前缀(state1, ..., stateM).
Q. 鉴于状态的数量可能很大，什么可能是一个好的表示？
可变长度马尔可夫链 (VLMC) 的有效表示是概率后缀树 (PST)。例如，请查看有关 PST R-package.
的文章 [1]
[1]：Gabadinho, A. 和 Ritschard, G. (2016)。使用概率后缀树分析状态序列：PST R 包。 统计软件杂志, 72(3), 1-39。 https://www.jstatsoft.org/article/view/v072i03
回想一下，（固定顺序）马尔可夫链可以被视为有限状态自动机，其边缘由转移概率标记。
因此，二阶马尔可夫链中的转换可以视为映射
trans2: (State,State) -> List[(State,Float)]
其中浮点值表示与目标状态关联的转移概率。
以明显的方式将其扩展到可变顺序的情况给出：
transN: List[State] -> List[(State,Float)]
但是，为某些输入 List(state1, ..., stateM ) 实现此映射需要在转换 table 中找到所有 LHS 条目，它们是 List 的（不一定正确的）前缀(state1, ..., stateM).
Q. 鉴于状态的数量可能很大，什么可能是一个好的表示？
可变长度马尔可夫链 (VLMC) 的有效表示是概率后缀树 (PST)。例如，请查看有关 PST R-package.
[1]：Gabadinho, A. 和 Ritschard, G. (2016)。使用概率后缀树分析状态序列：PST R 包。 统计软件杂志, 72(3), 1-39。 https://www.jstatsoft.org/article/view/v072i03