论文标题
算法相互信息的界限和Unifilar订单估计器
Bounds for Algorithmic Mutual Information and a Unifilar Order Estimator
论文作者
论文摘要
受希尔伯格的假设的启发，该假设指出，自然语言的块之间的相互信息像权力法一样生长，我们寻求算法互助信息的幂律增长率与Unifilar顺序的某些估计器之间的联系，即，即在其最小的隐藏式隐藏式隐藏式构造中产生的固定固定源代码中隐藏的状态的数量。我们考虑一个订单估计器，该订单估计器返回最大可能性大于弱惩罚的通用概率的最小顺序。该顺序估计器非常棘手，并遵循Merhav，Gutman和Ziv（1989）和Ziv和Merhav（1992）的思想，但尽管有一些很好的理论属性，但以其确切形式的形式似乎被忽略了。特别是，我们可以证明该顺序估计器的强度一致性，也可以证明算法相互信息的上限。使用两种结果，我们表明有限的Unifilar Order的所有（也是不可兼容的）来源均表现出算法互信息的子功率LAW生长和Unifilar Order估算器的生长。相比之下，我们还展示了一个统一的无限顺序的统一过程，具有确定性的下降自动机和算法随机甲骨文的示例，其中提到的两个数量作为具有相同指数的幂律而生长。我们还将结果与自然语言研究联系起来。
Inspired by Hilberg's hypothesis, which states that mutual information between blocks for natural language grows like a power law, we seek for links between power-law growth rate of algorithmic mutual information and of some estimator of the unifilar order, i.e., the number of hidden states in the generating stationary ergodic source in its minimal unifilar hidden Markov representation. We consider an order estimator which returns the smallest order for which the maximum likelihood is larger than a weakly penalized universal probability. This order estimator is intractable and follows the ideas by Merhav, Gutman, and Ziv (1989) and by Ziv and Merhav (1992) but in its exact form seems overlooked despite some nice theoretical properties. In particular, we can prove both strong consistency of this order estimator and an upper bound of algorithmic mutual information in terms of it. Using both results, we show that all (also uncomputable) sources of a finite unifilar order exhibit sub-power-law growth of algorithmic mutual information and of the unifilar order estimator. In contrast, we also exhibit an example of unifilar processes of a countably infinite order, with a deterministic pushdown automaton and an algorithmically random oracle, for which the mentioned two quantities grow as a power law with the same exponent. We also relate our results to natural language research.
