« 乱数の生成に関する研究 | Main | トレーニング系列を用いた乱数生成に関する研究 »

2009年10月25日

無限系列が真の乱数と識別できないための条件

無限に長い0と1の系列が与えられたとき、有限長系列に関する乱数判定法では真の乱数と区別できないための 必要十分条件が下記の3条件の各々と等価であることを示すのに成功しました。
  • 有限状態機械では過去の系列から次の1ビットを予想できない
  • 有限状態機械ではこの系列を圧縮できない
  • この系列の経験分布が一様分布であること
更に、Lempel-Ziv78符号で圧縮できない無限系列は、上記の2番目の条件を満たし、真の乱数と区別 できないことを明らかにしました。この研究は、乱数の本質に対して新たな知見を与えるものです。
Posted by 植松友彦 at 10:50 午前
Categories: 研究紹介