On the Algorithm Complexity of Generating Discrete Uniform Distribution from a Biased Coin

Area of Science:

• Information Theory
• Computer Science Theory
• Probability Theory

Background:

• Generating uniformly distributed random numbers is crucial for many computational tasks.
• Biased Bernoulli sources present a challenge for achieving true uniformity.
• Lei's Algorithm A3 (2023) was proposed to address this challenge.

Purpose of the Study:

• To provide a rigorous analytical proof for the uniformity mechanism of Algorithm A3.
• To derive explicit bounds on the algorithm's performance, including acceptance probability and runtime.
• To analyze the conversion of discrete uniform digits to a continuous Uniform(0,1) distribution.

Main Methods:

• Fourier analysis utilizing roots of unity for coefficient extraction.
• Derivation of acceptance-probability and expected-runtime bounds.
• Rigorous treatment of composite moduli.
• Base-n expansion for continuous uniform distribution simulation.

Main Results:

• A Fourier-analytic proof confirms the uniformity of Algorithm A3.
• Explicit bounds for acceptance probability and expected runtime are derived.
• The method for generating a continuous Uniform(0,1) distribution is demonstrated.
• The computational cost of finite-digit simulation is quantified.

Conclusions:

• Algorithm A3 provides an exact discrete uniform distribution from a biased Bernoulli source.
• The analytical bounds offer insights into the algorithm's efficiency and practical feasibility.
• The proposed method enables the simulation of continuous uniform distributions with quantifiable costs.