Recursive Algorithms for Unbiased Coin Tossing with Two Biased Coins
Date Issued
2004
Date
2004
Author(s)
Huang, Chia-Hui
DOI
en-US
Abstract
Suppose that we have two biased coins with probability of getting head p1 and p2, respectively, where (p1-1/2)(p2-1/2)<0.
We are interested in devising an algorithm to generate a
Bernoulli random variable with probability of getting head is 1/2. This question is motivated by the challenge question on getting a perfect lottery machine through non-perfect lottery machines.
We propose a sequential adaptive algorithm on flipping the just-described two coins to generate a Bernoulli random variable with probability of getting head is 1/2. The asymptotic properties of this algorithm will be presented.
The performance of this approximation is much better than that of the algorithm based on classical stochastic approximation in which the structure of this particular problem is not fully utilized. In addition, we use a simulation study to demonstrate that the asymptotic approximation is reasonable well with moderate sample size.
Subjects
隨機逼近
鞅論
stochastic approximation
martingale
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-93-R90221019-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):d9268bcb4d208b24a33038d11fe24dc1