An instance-based algorithm for deciding the bias of a coin

DOI10.1142/S1793830922500975MaRDI QIDQ6132245zbMATH OpenOpenAlexWikidataFDO

Authors Luís Fernando Schultz Xavier da Silveira, Michiel Smid

Publication date 14 July 2023

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.05502

zbMATH Keywords

bias coinChernoff-Hoeffding bound

Mathematics Subject Classification ID

Combinatorial probability (60C05) General topics of discrete mathematics in relation to computer science (68R01)

Abstract: Let $qin(0,1)$ and $deltain(0,1)$ be real numbers, and let $C$ be a coin that comes up heads with an unknown probability $p$, such that $peqq$. We present an algorithm that, on input $C$, $q$, and $delta$, decides, with probability at least $1-delta$, whether $p<q$ or $p>q$. The expected number of coin flips made by this algorithm is $Oleft(fracloglog(1/varepsilon)+log(1/delta)varepsilo{n}^{2}ight)$, where $varepsilon=|p-q|$.

Recommendations

• Tree algorithms for unbiased coin tossing with a biased coin
• Two sides of the coin problem
• Optimal coin flipping
• From biased coin to any discrete distribution
• The Biased Coin Problem

Cites work

• An almost optimal algorithm for unbounded searching
• Concentration of Measure for the Analysis of Randomized Algorithms
• Neural Network Learning
• The sample complexity of exploration in the multi-armed bandit problem

Cited in

(3)

• Efficient simulations by a biased coin
• Achieving Optimal Fairness from Biased Coinflips
• scientific article; zbMATH DE number 5589306 (Why is no real title available?)

This page was built for publication: An instance-based algorithm for deciding the bias of a coin

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