https://scholars.lib.ntu.edu.tw/handle/123456789/630053
標題: | Asymptotic analysis of peres' algorithm for random number generation | 作者: | Lim, Zhao Ging CHEN-TUO LIAO Yao, Yi Ching |
關鍵字: | analysis of algorithms; Elias' extractor; entropy; Peres' extractor; regularly varying sequence; superadditivity; von Neumann's extractor | 公開日期: | 1-四月-2022 | 出版社: | CAMBRIDGE UNIV PRESS | 卷: | 36 | 期: | 2 | 起(迄)頁: | 341 | 來源出版物: | Probability in the Engineering and Informational Sciences | 摘要: | von Neumann [(1951). Various techniques used in connection with random digits. National Bureau of Standards Applied Math Series 12: 36-38] introduced a simple algorithm for generating independent unbiased random bits by tossing a (possibly) biased coin with unknown bias. While his algorithm fails to attain the entropy bound, Peres [(1992). Iterating von Neumann's procedure for extracting random bits. The Annals of Statistics 20(1): 590-597] showed that the entropy bound can be attained asymptotically by iterating von Neumann's algorithm. Let denote the expected number of unbiased bits generated when Peres' algorithm is applied to an input sequence consisting of the outcomes of tosses of the coin with bias. With, the coin is unbiased and the input sequence consists of unbiased bits, so that may be referred to as the cost incurred by Peres' algorithm when not knowing. We show that (where is the logarithm to base), which together with limited numerical results suggests that may be a regularly varying sequence of index. (A positive sequence is said to be regularly varying of index if for all 0]]>, where denotes the largest integer not exceeding.) Some open problems on the asymptotic behavior of are briefly discussed where denotes the Shannon entropy of a random bit with bias. |
URI: | https://scholars.lib.ntu.edu.tw/handle/123456789/630053 | ISSN: | 02699648 | DOI: | 10.1017/S0269964820000510 |
顯示於: | 農藝學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。