Fair coin
In probability theory and statistics, a sequence of independent Bernoulli trials with probability 1/2 of success on each trial is metaphorically called a fair coin.
≈ 8 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In probability theory and statistics, a sequence of independent Bernoulli trials with probability 1/2 of success on each trial is metaphorically called a fair coin. One for which the probability is not 1/2 is called a biased or unfair coin. In theoretical studies, the assumption that a coin is fair is often made by referring to an ideal coin.
John Edmund Kerrich performed experiments in coin flipping and found that a coin made from a wooden disk about the size of a crown and coated on one side with lead landed heads (wooden side up) 679 times out of 1000. In this experiment the coin was tossed by balancing it on the forefinger, flipping it using the thumb so that it spun through the air for about a foot before landing on a flat cloth spread over a table.
Edwin Thompson Jaynes claimed that when a coin is caught in the hand, instead of being allowed to bounce, the physical bias in the coin is insignificant compared to the method of the toss, where with sufficient practice a coin can be made to land heads 100% of the time.…
In probability theory and statistics, a sequence of independent Bernoulli trials with probability 1/2 of success on each trial is metaphorically called a fair coin. One for which the probability is not 1/2 is called a biased or unfair coin. In theoretical studies, the assumption that a coin is fair is often made by referring to an ideal coin.
John Edmund Kerrich performed experiments in coin flipping and found that a coin made from a wooden disk about the size of a crown and coated on one side with lead landed heads (wooden side up) 679 times out of 1000. In this experiment the coin was tossed by balancing it on the forefinger, flipping it using the thumb so that it spun through the air for about a foot before landing on a flat cloth spread over a table.
Edwin Thompson Jaynes claimed that when a coin is caught in the hand, instead of being allowed to bounce, the physical bias in the coin is insignificant compared to the method of the toss, where with sufficient practice a coin can be made to land heads 100% of the time. The traditional Australian game of Two-up uses a specific set of rules and physical mechanics to keep the coin toss fair and random: Coins may not be directly thrown from the hand Coins must be tossed at least 10 feet in the air Coins must not hit any obstruction Coins have to visibly spin through the air Exploring the problem of checking whether a coin is fair is a well-established pedagogical tool in teaching statistics. \Omega = \{H, T\} The event space for a coin includes all sets of outcomes from the sample space which can be assigned a probability, which is the full power set 2^{\Omega} .
Thus, the event space is defined as: \mathcal{F} = \{\{\}, \{H\}, \{T\}, \{H, T\}\} \{\} is the event where neither outcome happens (which is impossible and can therefore be assigned 0 probability), and \{H, T\} is the event where either outcome happens, (which is guaranteed and can be assigned 1 probability). Because the coin is fair, the possibility of any single outcome is 50-50.
The probability measure is then defined by the function: So the full probability space which defines a fair coin is the triplet (\Omega, \mathcal{F}, P) as defined above. Note that this is not a random variable because heads and tails do not have inherent numerical values like you might find on a fair two-valued die.
A random variable adds the additional structure of assigning a numerical value to each outcome. Common choices are (H,T)\to(1,0) or (H,T)\to(1,-1) .
The expected value of flips at the n game E(F_n) is not hard to calculate, first notice that in step 3 whatever the event HT or TH we have flipped the coin twice so E(F_n|HT,TH)=2 but in step 2 ( TT or HH ) we also have to redo things so we will have 2 flips plus the expected value of flips of the next game that is E(F_n|TT,HH)=2+E(F_{n+1}) but as we start over the expected value of the next game is the same as the value of the previous game or any other game so it does not really depend on n thus E(F)=E(F_n)=E(F_{n+1}) (this can be understood the process being a martingale E(F_{n+1}|F_n,...,F_1)=F_n where taking the expectation again get us that E(E(F_{n+1}|F_n,...,X_1))=E(F_n) but because of the law of total expectation we get that E(F_{n+1})=E(E(F_{n+1}|F_n,...,F_1))=E(F_n) ) hence we have: \begin{align} E(F) &=E(F_n)\\ &=E(F_n|TT,HH)P(TT,HH)+E(F_n|HT,TH)P(HT,TH)\\ &=(2+E(F_{n+1}))P(TT,HH)+2P(HT,TH)\\ &=(2+E(F))P(TT,HH))+2P(HT,TH)\\ &=(2+E(F))(P(TT)+P(HH))+2(P(HT)+P(TH))\\ &=(2+E(F))(P(T)^2+P(H)^2)+4P(H)P(T)\\ &=(2+E(F))(1-2P(H)P(T))+4P(H)P(T)\\ &=2+E(F)-2P(H)P(T)E(F)\\ \end{align} \therefore E(F)=2+E(F)-2P(H)P(T)E(F)\Rightarrow E(F)=\frac{1}{P(H)P(T)}=\frac{1}{P(H)(1-P(H))} The more biased our coin is, the more likely it is that we will have to perform a greater number of trials before a fair result. Suppose that the bias b:=P(\mathtt{H}) is known.
In this section, we provide a simple algorithm that improves the expected number of coin tosses. The algorithm allows simulating a coin with any probability p , and the value of p changes internally across iterations. To get a fair coin, the algorithm first sets p = 0.5 and then executes the following steps.
Toss the biased coin. Let X \in \{\mathtt{H}, \mathtt{T}\} be the result. If p \ge b , use \mathtt{H} if the flip result is X=\mathtt{H} .
Otherwise, set p to \frac{p-b}{1-b} and go back to step 1. Otherwise, p , use \mathtt{T} if the flip result is X=\mathtt{T} . Otherwise, set p to \frac{p}{b} and go back to step 1.
Note that the above algorithm does not reach the optimal expected number of coin tosses, which is 1/H(b) (here H(b) is the binary entropy function). There are algorithms that reach this optimal value in expectation. However, those algorithms are more sophisticated than the one above.
The above algorithm has an expected number of biased coinflips being \frac{1}{2 b(1-b)} , which is exactly half of the expected flips for von Neumann's approach. Given the bias b=P(H) and the current value of p , one can define a function f_b(p) that represents the expected number of coin tosses before a result is returned.
The recurrence relation of f_b(p) can be described as follows. f_b(p) = \begin{cases} 1 + b\cdot f_b\left( \frac{p}{b} \right) & \text{if } p This solves to the following function: f_b(p) = \frac{b + (1-2b)p}{b(1-b)} When p=0.5 , the expected number of coinflips is f_b(0.5) = \frac{1}{2b(1-b)} as desired.
Further reading
Available from Andrew Gelman's website John von Neumann, "Various techniques used in connection with random digits," in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, 12 (Washington, D.C.: U.S. Government Printing Office, 1951): 36-38.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1375052414 under CC BY-SA 4.0; modifications have been made.