Large Deviations Performance of Interval Algorithm for Random Number Generation
Large Deviations Performance of Interval Algorithm for Random Number Generation
复制标题
随机数生成区间算法的大偏差性能
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
T. Uyematsu
中科院分区：
文献类型：
--
作者：
Akisato Kimura;T. Uyematsu
我们研究了随机数生成的区间算法的大偏差性能。首先，我们证明输入序列的长度与输出序列的长度几乎肯定接近输入和输出分布的熵之比。接下来，我们研究大偏差性能，特别是内在随机性。我们表明，每个输入样本的输出公平随机位的长度几乎肯定接近输入源的熵，并且我们可以确定这种情况下的指数。进一步地，我们考虑从固定长度的输入序列中获取固定数量的公平随机比特。我们表明，如果每个输入样本的输出随机位数低于源的熵，则随着输入序列的长度趋于无穷大，由变分距离和散度测量的近似误差呈指数消失。相反，如果每个输入样本的随机位数高于源的熵，则由变分距离测量的近似误差以指数方式接近二，由散度测量的近似误差以线性方式接近无穷大。 ＊部门东京工业大学电气电子工程系，地址：2-12-1 Ookayama, Meguro-ku, Tokyo 152-8552, Japan
We investigate large deviations performance of interval algorithm for random number generation. First, we show that the length of input sequence per the length of output sequence approaches to the ratio of entropies of input and output distributions almost surely. Next, we investigate large deviations performance especially for intrinsic randomness. We show that the length of output fair random bits per input sample approaches to the entropy of the input source almost surely, and we can determine the exponent in this case. Further, we consider to obtain the fixed number of fair random bits from the input sequence with fixed length. We show that the approximation error measured by the variational distance and divergence vanishes exponentially as the length of input sequence tends to infinity, if the number of output random bits per input sample is below the entropy of the source. Contrarily, the approximation error measured by the variational distance approaches to two exponentially and the approximation error measured by the divergence approaches to infinity linearly, if the number of random bits per input sample is above the entropy of the source. ∗Dept. of Electrical and Electronic Eng., Tokyo Institute of Technology, 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8552, Japan