A Note on Approximation of Uniform Distributions From Variable-to-Fixed Length Codes
作者： F. Cicalese , L. Gargano , U. Vaccaro
关键词: Discrete mathematics 、 Combinatorics 、 Partially ordered set 、 Random number generation 、 Probability distribution 、 Mathematics 、 Parse tree 、 Upper and lower bounds 、 Minimax approximation algorithm 、 Uniform distribution (continuous) 、 Majorization
摘要: In this correspondence, we prove that the probability distribution induced on leaves of a Tunstall parse tree for given source is (unique) lower bound in partially ordered set distributions by all possible trees with same number leaves, and according to majorization partial order. We apply result problem optimally approximating uniform flips biased coin
acm.org
sci-hub.se 参考文章(46)
Noam Nisan, Extracting randomness: how and why ,(1996)
Brian Parker Tunstall, Synthesis of noiseless compression codes Georgia Institute of Technology. ,(1967)
S. M. Ali, S. D. Silvey, A General Class of Coefficients of Divergence of One Distribution from Another Journal of the Royal Statistical Society: Series B (Methodological). ,vol. 28, pp. 131- 142 ,(1966) , 10.1111/J.2517-6161.1966.TB00626.X
Ömer Eğecioğlu, Marcus Peinado, Algorithms for Almost-uniform Generation with an Unbiased Binary Source computing and combinatorics conference. pp. 117- 126 ,(1998) , 10.1007/3-540-68535-9_15
Isaac L. Chuang, Michael A. Nielsen, Quantum Computation and Quantum Information ,(2000)
Y.A. Reznik, W. Szpankowski, Improved behaviour of tries by the "symmetrization" of the source data compression conference. pp. 372- 381 ,(2002) , 10.1109/DCC.2002.999975
Sung-il Pae, Michael C. Loui, Optimal random number generation from a biased coin symposium on discrete algorithms. pp. 1079- 1088 ,(2005) , 10.5555/1070432.1070587
V. M. Sidel'nikov, On the statistical properties of transformations realizabie on finite automata Cybernetics. ,vol. 1, pp. 1- 19 ,(1965) , 10.1007/BF01074690
Toshiya Itoh, Simulating Fair Dice with Biased Coins Information & Computation. ,vol. 126, pp. 78- 82 ,(1996) , 10.1006/INCO.1996.0036
Julia Abrahams, On the selection of measures of distance between probability distributions Information Sciences. ,vol. 26, pp. 109- 113 ,(1982) , 10.1016/0020-0255(82)90035-4