A Universal Scheme for Transforming Binary Algorithms to Generate Random Bits from Loaded Dice

2012/09/04 by Hongchao Zhou, Zhou, Hongchao, Jehoshua Bruck +1 · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Cellular Automata and Applications #Chaos-based Image/Signal Encryption #cs.IT #math.IT #math.PR

paper · pdf · doi:10.48550/arxiv.1209.0726

2 columns, 10 pages

arxiv created 2012/09/04 · arxiv updated 2012/09/05

Abstract

In this paper, we present a universal scheme for transforming an arbitrary algorithm for biased 2-face coins to generate random bits from the general source of an m-sided die, hence enabling the application of existing algorithms to general sources. In addition, we study approaches of efficiently generating a prescribed number of random bits from an arbitrary biased coin. This contrasts with most existing works, which typically assume that the number of coin tosses is fixed, and they generate a variable number of random bits.

Cited by

• Streaming Algorithms for Optimal Generation of Random Bits

Related

• Optimal Discrete Uniform Generation from Coin Flips, and Applications
• Streaming Algorithms for Optimal Generation of Random Bits
• Random variate generation using only finitely many unbiased, independently and identically distributed random bits
• Effective Generation of Subjectively Random Binary Sequences
• Optimal rolling of fair dice using fair coins