From biased coin to any discrete distribution

DOI10.1007/S10998-020-00363-WMaRDI QIDQ2043731zbMATH OpenOpenAlexFDO

Authors Karol Gryszka

Publication date 3 August 2021

Published in Periodica Mathematica Hungarica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10998-020-00363-w

zbMATH Keywords

algorithmbiased coincoin flipdiscrete distributiondiscrete probability measureexpected valuesimulation of distribution

Mathematics Subject Classification ID

Computational methods for problems pertaining to probability theory (60-08) Probabilistic measure theory (60A10) Probability distributions: general theory (60E05) Random number generation in numerical analysis (65C10)

Review text

This paper shows that there is a coin-based algorithm that can generate any discrete distribution, with a size that can include any countable set. The coin need not be fair and the algorithm is not based on a limiting process. The work is elegant and interesting.

Recommendations

• Generation of discrete distributions from biased coins
• scientific article; zbMATH DE number 4117876
• Generating discrete uniform distribution from a biased coin using number-theoretic method
• Efficient generation of fair dice with few biased coins
• Tree algorithms for unbiased coin tossing with a biased coin

Cites work

• How to turn loaded dice into fair coins
• scientific article; zbMATH DE number 3614066 (Why is no real title available?)
• Optimal random number generation from a biased coin
• Simulating fair dice with biased coins
• The Efficient Construction of an Unbiased Random Sequence
• Tree algorithms for unbiased coin tossing with a biased coin

Cited in

(6)

• Independent unbiased coin flips from a correlated biased source - a finite state Markov chain
• Generation of discrete distributions from biased coins
• Coin flipping of any constant bias implies one-way functions
• Coin Flipping with Constant Bias Implies One-Way Functions
• An instance-based algorithm for deciding the bias of a coin
• Generating discrete uniform distribution from a biased coin using number-theoretic method

This page was built for publication: From biased coin to any discrete distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2043731)