請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/8077
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 姚怡慶(Yi-Ching Yao) | |
dc.contributor.author | Zhao Ging Randy Lim | en |
dc.contributor.author | 林昭京 | zh_TW |
dc.date.accessioned | 2021-05-20T00:48:45Z | - |
dc.date.available | 2021-01-07 | |
dc.date.available | 2021-05-20T00:48:45Z | - |
dc.date.copyright | 2021-01-07 | |
dc.date.issued | 2020 | |
dc.date.submitted | 2020-12-26 | |
dc.identifier.citation | Bernard, J. Letac, G. (1973). Construction d'evenements equiprobables et coefficients 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. Han, T. S. Hoshi, M. (1997). Interval algorithm for random number generation. IEEE Transactions on Information Theory 43(2): 599–611. Hoeffding, W. Simons, G. (1970). Unbiased coin tossing with a biased coin. Annals of Mathematical Statistics 41(2): 341–352. Jacquet, P. Szpankowski, W. (1999). Entropy computations via analytic depoissonization. IEEE Transactions on Information Theory 45(4): 1072–1081. Kallenberg, O. (2002). Foundations of Modern Probability. New York: Springer. Keane, M. S. O'Brien, G. L. (1994). A Bernoulli factory. ACM Transactions on Modeling and Computer Simulation 4(2): 213–219. Knuth, D. Yao, A. (1976). The complexity of nonuniform random number generation. Algorithms and Complexity: New Directions and Recent Results. Ed. by J. Traub. Academic Press. Lim, Z. G., Liao, C.-T., Yao, Y.-C. (2020). Asymptotic analysis of Peres' algorithm for random number generation. Probability in the Engineering and Informational Sciences, to appear. Lim, Z. G. Yao, Y.-C. (2020). Some streaming versions of Peres' algorithm for random number generation. Unpublished manuscript. Nacu, Ş. Peres, Y. (2005). Fast simulation of new coins from old. Annals of Applied Probability 15 (1A): 93–115. Oohama, Y. (2011). Performance analysis of the interval algorithm for random number generation based on number systems. IEEE Transactions on Information Theory 57(3): 1177–1185. Pae, S.-i. (2013). Exact output rate of Peres's algorithm for random number generation. Information Processing Letters 113(5): 160–164. Pae, S.-i. (2015). A generalization of Peres's algorithm for generating random bits from loaded dice. IEEE Transactions on Information Theory 61(2): 751–757. Pae, S.-i. (2020). Binarization trees and random number generation. IEEE Transactions on Information Theory 66(4): 2581–2587. Pae, S.-i. Loui, M. C. (2006). Randomizing functions: simulation of a discrete probability distribution using a source of unknown distribution. IEEE Transactions on Information Theory 52(11): 4965–4976. Peres, Y. (1992). Iterating von Neumann's procedure for extracting random bits. The Annals of Statistics 20(1): 590–597. Prasitsupparote, A., Konno, N., Shikata, J. (2018). Numerical and nonasymptotic analysis of Elias's and Peres's extractors with finite input sequences. Entropy 20(10): article #729, 19 pages. Ryabko, B. Matchikina, E. (2000). Fast and efficient construction of an unbiased random sequence. IEEE Transactions on Information Theory 46(3): 1090–1093. Samuelson, P. A. (1968). Constructing an unbiased random sequence. Journal of the American Statistical Association 63(324): 1526–1527. Seroussi, G. Weinberger, M. J. (2015). Optimal algorithms for universal random number generation from finite memory sources. IEEE Transactions on Information Theory 61(3): 1277–1297. Stout, Q. F. Warren, B. (1984). Tree algorithms for unbiased coin tossing with a biased coin. Annals of Probability 12(1): 212–222. von Neumann, J. (1951). Various techniques used in connection with random digits. National Bureau of Standards Applied Math Series 12: 36–38. Watanabe, S. Han, T. S. (2020). Interval algorithm for random number generation: information spectrum approach. IEEE Transactions on Information Theory 66(3): 1691–1701. Wei, W. Guo, H. (2009). Bias-free true random-number generator. Optics Letters 34(12): 1876–1878. Zhou, H. Bruck, J. (2012a). Efficient generation of random bits from finite state Markov chains. IEEE Transactions on Information Theory 58(4): 2490–2506. Zhou, H. Bruck, J. (2012b). Streaming algorithms for optimal generation of random bits. arXiv: 1209.0730 [cs, math]. URL: http://arxiv.org/abs/1209.0730. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/8077 | - |
dc.description.abstract | 對於利用投擲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演算法的串流版本並不會產生無偏的位元亂數列,然而在特定的排序下,我們證明了這樣的串流版本所產生的位元亂數列是無偏的。 | zh_TW |
dc.description.abstract | 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 output 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. | en |
dc.description.provenance | Made available in DSpace on 2021-05-20T00:48:45Z (GMT). No. of bitstreams: 1 U0001-2212202018315700.pdf: 23717540 bytes, checksum: 27e4df7801d48ad3ee37efc0ffcc7cd9 (MD5) Previous issue date: 2020 | en |
dc.description.tableofcontents | 口試委員審定書 i 致謝 iii 摘要 v Abstract vii Contents ix List of Figures xi Chapter 1 Introduction 1 1.1 von Neumann's algorithm . . . . . . . . . . . . . . . . . . . . . 1 1.2 Elias' algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Peres' algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Binary tree representation of Peres' algorithm . . . . . . . . . . . 6 1.5 Brief literature review . . . . . . . . . . . . . . . . . . . . . . . 8 Chapter 2 Asymptotic Analysis of Peres' algorithm 13 2.1 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Proofs of Propositions 2.1 and 2.2 and (2.1) . . . . . . . . . . . . 15 2.3 Numerical results and discussion . . . . . . . . . . . . . . . . . . 26 Chapter 3 Streaming versions of Peres' algorithm 33 3.1 Introduction and streaming algorithms . . . . . . . . . . . . . . . 33 3.2 Status tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3 Unbiasedness of AS . . . . . . . . . . . . . . . . . . . . . . . . 46 3.4 Zhou-Bruck's streaming version of Peres' algorithm . . . . . . . 55 3.5 Counting status trees . . . . . . . . . . . . . . . . . . . . . . . . 65 Chapter 4 Concluding remarks 71 References 73 | |
dc.language.iso | en | |
dc.title | Peres位元亂數產生演算法及其串流版本之分析 | zh_TW |
dc.title | Analysis of Peres' algorithm and its streaming versions for random number generation | en |
dc.type | Thesis | |
dc.date.schoolyear | 109-1 | |
dc.description.degree | 博士 | |
dc.contributor.author-orcid | 0000-0002-1589-6167 | |
dc.contributor.coadvisor | 廖振鐸(Chen-Tuo Liao) | |
dc.contributor.coadvisor-orcid | 廖振鐸(0000-0001-9777-3701) | |
dc.contributor.oralexamcommittee | 黃啟瑞(Chii-Ruey Hwang),陳宏(Hung Chen),蕭守仁(Shoou-Ren Hsiau),王家禮(Chia-Li Wang),陳定立(Ting-Li Chen) | |
dc.contributor.oralexamcommittee-orcid | ,陳定立(0000-0002-1375-0164) | |
dc.subject.keyword | 資訊熵,演算法分析,Elias提取器,Peres提取器,馮·諾伊曼提取器,超可加性,串流演算法,狀態樹, | zh_TW |
dc.subject.keyword | entropy,analysis of algorithms,Elias' extractor,Peres' extractor,von Neumann's extractor,superadditivity,streaming algorithm,status tree, | en |
dc.relation.page | 75 | |
dc.identifier.doi | 10.6342/NTU202004447 | |
dc.rights.note | 同意授權(全球公開) | |
dc.date.accepted | 2020-12-28 | |
dc.contributor.author-college | 生物資源暨農學院 | zh_TW |
dc.contributor.author-dept | 農藝學研究所 | zh_TW |
顯示於系所單位: | 農藝學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-2212202018315700.pdf | 23.16 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。