Knuth-Yaoアルゴリズムおよび区間アルゴリズムの新しい実装法とその性能評価

摘要

In this paper, new implementation algorithms are proposed for Knuth-Yao algorithm and the Interval algorithm, which can generate a sequence with an arbitrarily given discrete probability Py (y) from a binary random sequences {X_i}. The proposed algorithms don't require high precision in operation and can achieve Py(y) without error. For the Interval algorithm, we derive the exact theoretical value of the average bit length E[L] of X_i necessary to generate one symbol of Y for |y| = 2 and 3, where |y| is the cardinality of alphabet of Y. Furthermore, a new tight upper bound of E[L] is derived for |y|≧ 4.%任意に与えられた有限離散確率分布P_Y（y）を持つ確率変数Yを，2値定常無記憶な一様乱数列｛X_i｝から生成するアルゴリズムであるKnuth-Yaoアルゴリズムと区間アルゴリズムに対して，それぞれP_Y（y）とその累積確率分布の2進数展開を用いた新しい実装アルゴリズムを提案する．提案アルゴリズムは，それらの2進数展開が与えられれば，高い演算性能を必要とせず，P_Y（y）を誤差ゼロで実現できる．また，区間アルゴリズムに対して，Yのアルファベットサイズ|y|が2および3の場合に，Yを1シンボル生成するのに必要な{X_i}の平均ビット長E[L］の厳密な理論式を導出すると共に，|y|≧4の場合に対して，E|L|の新しい上界を与える．