Merhavらは，定常マルコフ情報源の次数を推定する問題を考察し，Lempel-Ziv(LZ)符号の符号語長を用いた次数の推定法を提案した.本論文では，LZ符号を含む一般のユニバーサル符号の符号語長を用いた次数の推定法を提案する.ここでいうユニバーサル符号とは，情報源の統計的性質によらず符号化が行え，1記号あたりの符号語長が任意の次数の正規化経験ェントロピーを漸近的に達成する符号のことである.提案した次数の推定法は，系列長nと次数を過大評価する確率P_oについて-(１)logP_oの下極限が定められた値以上という条件のもとで，次数を過小評価する確率P_uについて(１)logP_uの上極限を最小にするという意味で最適である.%Merhav et al.studied the problem of estimating the order of stationary Markov sources. They proposed an order estimator using codeword length of the Lempel-Ziv(LZ) code. In this paper, We propose an alternative order estimator using codeword length of a general universal code. The universal code means the code whose compression ratio asymptotically achieves the normalized empirical entropy rate of any order. The proposed order estimator is shown to be asymptotically optimal in the following performance criterion. For the sequence length n, the probability P_u of underestimating the order and the probability P_o of overestimating it, the order estimator minimizes the limit superior of (1) logP_u while keeping the limit inferior of -(1) logP_o more than a given prescribed level.
展开▼
