情報スペクトル理論に基づく乱数生成問題の研究

点击翻译按钮获取中文摘要

研究計画に従い、「可変長非一様乱数の最大生成レートに関する研究」を行った。ある与えられた分布(コイン分布)に従う確率変数列を変換して、決められた分布(ターゲット分布)にある尺度(例えば、変動距離)で見たときに十分近い乱数をを作り出す問題のことを、乱数近似問題という。この問題は、HanとVerduによって提起された。彼らは情報源Yが与えられたとき,可能な限り小さいサイズの一様乱数を用いてYを近似する問題(resolvability問題)を考えた。VembuとVerduは、resolvability問題と双対な問題、すなわち情報源Xが与えられたときそれを変換してサイズの出来るだけ大きい一様乱数を近似する問題(intrinsic randomness問題)を考え、生成列が固定長の場合と可変長の場合の両方が考察された。また、可変長intrinsic randomnessの結果はHanによってより強い形で述べられている。昨年度、研究代表者によって、可変長非一様i.i.d.乱数の最適な生成レートが決定されたが、これはHanの結果の一般化になっていた。本年度は、この結果の更なる一般化を目指し研究を行った。その結果、可変長非一様マルコフ乱数の最適な生成レートを求めることができた。この結果は、これまで得られている乱数、生成最適レートの中でも、最も一般的なものの一つである。研究成果は、国際会議での発表を行った後、英文の学術論文誌に掲載された。また、その後の研究により、さらに一般的な可変長非一様乱数の最適な生成レートを求めることが可能であることがほぼわかった。今後さらに検討を行い、上記レートの導出を試みたい。