ITERATING VONNEUMANN PROCEDURE FOR EXTRACTING RANDOM BITS

被引：127

作者：

PERES, Y ^{[1
]}

机构：

[1] HEBREW UNIV JERUSALEM,JERUSALEM,ISRAEL

来源：

ANNALS OF STATISTICS | 1992年 / 20卷 / 01期

关键词：

RANDOM BITS; ENTROPY; FUNCTIONAL EQUATION; EXCHANGEABILITY;

D O I：

10.1214/aos/1176348543

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

Given a sequence of independent, identically distributed random biased bits, von Neumann's simple procedure extracts independent unbiased bits. In this note we show that the number of unbiased bits produced by iterating this procedure is arbitrarily close to the entropy bound.

引用

页码：590 / 597

页数：8

共 8 条

[1]

Blum M., 1984, 25th Annual Symposium on Foundations of Computer Science (Cat. No. 84CH2085-9), P425, DOI 10.1109/SFCS.1984.715944

[2] EFFICIENT CONSTRUCTION OF AN UNBIASED RANDOM SEQUENCE [J].

ELIAS, P .

ANNALS OF MATHEMATICAL STATISTICS, 1972, 43 (03) :865-&

[3]

Feller W., 1966, INTRO PROBABILITY TH, VII

[4] CLASS OF FINITARY CODES [J].

KEANE, M ;

SMORODINSKY, M .

ISRAEL JOURNAL OF MATHEMATICS, 1977, 26 (3-4) :352-371

[5]

MCELIECE RJ, 1977, ENCY MATH ITS APPLIC, V3

[6] TREE ALGORITHMS FOR UNBIASED COIN TOSSING WITH A BIASED COIN [J].

STOUT, QF ;

WARREN, B .

ANNALS OF PROBABILITY, 1984, 12 (01) :212-222

[7]

von Neumann J., 1951, NBS APPL MATH SER, P36

[8]

[No title captured]

← 1 →