ユニバーサル符号の符号語長を用いた定常マルコフ情報源の次数推定法

摘要

Merhavらは，定常マルコフ情報源の次数を推定する問題を考察し，Lempel-Ziv（LZ）符号の符号語長を用いた次数の推定法を提案した．本論文では，LZ符号を含む一般のユニバーサル符号の符号語長を用いた次数の推定法を提案する．ここでいうユニバーサル符号とは，情報源の統計的性質によらず符号化が行え，1記号あたりの符号語長が任意の次数の正規化経験エントロピーを漸近的に達成する符号のことである．提案した次数の推定法は，系列長件と次数を過大評価する確率P_oについて-（1／m）log P_oの下極限が定められた値以上という条件のもとで，次数を過小評価する確率孔について(1)logP_uの上極限を最小にするという意味で最適である．