Peres位元亂數產生演算法及其串流版本之分析

Analysis of Peres' algorithm and its streaming versions for random number generation

林昭京(Zhao Ging Randy Lim)

指導教授 ： 姚怡慶

共同指導教授 ： 廖振鐸(Chen-Tuo Liao)

國立臺灣大學/生物資源暨農學院/農藝學研究所/博士(2020年)

https://doi.org/10.6342/NTU202004447

摘要

對於利用投擲p-­偏銅板來產生獨立無偏的位元亂數，馮·諾伊曼（1951）提出了簡單的演算法,雖然這個演算法並非有效率地用上p-­偏銅板所蘊含的資訊熵，然而Peres（1992）提出可疊代使用上述演算法，並證明了這樣的疊代演算法的亂數產生效率無限趨近於p-­偏銅板的資訊熵上界。確切來說，Peres證明了b(n,p)/n均勻（於p ∈ (0,1)）收斂到h(p)，其中b(n,p)為Peres演算法應用於n次p-­偏銅板投擲結果(X_1,...,X_n)所產生的獨立無偏位元亂數個數的期望值，而h(p) = −p log p−(1−p)log(1−p)是單次p-­偏銅板投擲的資訊熵。我們考慮了b(n,p)的二階行為，即nh(p)−b(n,p)於n趨近於無窮大時的漸近行為。在p=1/2下,我們得到了 lim_{n→∞} log[n−b(n,1/2)]/log n = log[(1+√5)/2]這樣的結果。我們也扼要地討論了當nh(p)−b(n,p)在n趨近於無窮大時關於其行為的一些待解決問題。Peres演算法在原來被提出時並非為串流演算法（streaming algorithm），亦即(X_1,...,X_n)所產生的亂數一般上並不一定會全被排在由X_{n+1}所產生的亂數之前。我們介紹了Peres演算法的二元樹表示，也進一步介紹了一類由二元樹上節點的排序所決定的Peres演算法的串流版本。在一般二元樹節點的排序下，Peres演算法的串流版本並不會產生無偏的位元亂數列，然而在特定的排序下，我們證明了這樣的串流版本所產生的位元亂數列是無偏的。

關鍵字

資訊熵 ； 演算法分析 ； Elias提取器 ； Peres提取器 ； 馮·諾伊曼提取器 ； 超可加性 ； 串流演算法 ； 狀態樹

並列摘要

von Neumann (1951) introduced a simple algorithm for generating independent and unbiased random bits by tossing a coin of unknown bias p. While his algorithm fails to attain the entropy bound, Peres (1992) showed that the entropy bound can be attained asymptotically by iterating von Neumann's algorithm. Specifically, Peres showed that lim_{n→∞} b(n,p)/n = h(p) uniformly in p ∈ (0,1), where b(n,p) denotes the expected number of unbiased output bits generated when Peres' algorithm is applied to an input sequence (X_1,...,X_n) with X_i being the outcome of the ith coin toss, and h(p) = −p log p−(1−p)log(1−p) (the Shannon entropy of each X_i). We consider the (second­ order) behavior of nh(p)−b(n,p) as n→∞. For p=1/2, it is shown that lim_{n→∞} log[n−b(n,1/2)]/log n = log[(1+√5)/2]. Some open problems on the asymptotic behavior of nh(p)−b(n,p) are briefly discussed. The original Peres' algorithm is not streaming in the sense that some of the out­put bits generated from (X_1,...,X_n) (the first n coin tosses) may be placed after the output bits induced by X_{n+1}. We introduce a binary tree representation of Peres' algorithm, based on which we further introduce a class of streaming versions of Peres' algorithm in terms of orderings of the nodes of the binary tree. We show by example that in general a streaming version of Peres' algorithm fails to generate unbiased output bits. However, based on a special node ordering, the corresponding streaming version of Peres' algorithm is shown to be unbiased.

並列關鍵字

entropy ； analysis of algorithms ； Elias' extractor ； Peres' extractor ； von Neu­mann's extractor ； superadditivity ； streaming algorithm ； status tree

參考文獻

Bernard, J. Letac, G. (1973). Construction d'evenements equiprobables et coeffi­cients multinomiaux modulo p^n. Illinois Journal of Mathematics 17(2): 317–332.

Blum, M. (1986). Independent unbiased coin flips from a correlated biased source––a finite state Markov chain. Combinatorica 6(2): 97–108.

Bojanic, R. Seneta, E. (1973). A unified theory of regularly varying sequences. Mathematische Zeitschrift 134(2): 91–106.

Dwass, M. (1972). Unbiased coin tossing with discrete random variables. Annals of Mathematical Statistics 43(3): 860–864.

Elias, P. (1972). The efficient construction of an unbiased random sequence. Annals of Mathematical Statistics 43(3): 865–870.