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

摘要

任意に与えられた有限離散確率分布P_Y（y）を持つ確率変数yを，2値定常無記憶な一様乱数列｛X_i｝から生成するアルゴリズムであるKnuth-Yaoアルゴリズムと区間アルゴリズムに対して，、それぞれP_Y（y）とその累積確率分布の2進数展開考用いた新しい実装アルゴリズムを提案する．提案アルゴリズムは，それらの2進数展開が与えられれば，高い演算性能を必要とせず，P_Y（y）を誤差ゼロで実現できる．また，区間アルゴリズムに対して，Yのアルアァベットサイズ月井が2および3の場合に，Yを1シンボル生成するのに必要な｛X_i｝の平均ビット長ELの厳密な理論式を導出すると共に，y≧4の場合に対して，ELの新しい上界を与える．