Fair coin

Last updated April 15, 2024

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.^[1] 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.^[2] Exploring the problem of checking whether a coin is fair is a well-established pedagogical tool in teaching statistics.

Probability space definition

In probability theory, a fair coin is defined as a probability space $(\Omega ,{\mathcal {F}},P)$ , which is in turn defined by the sample space, event space, and probability measure. Using $H$ for heads and $T$ for tails, the sample space of a coin is defined as:

\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:

$x$	$\{\}$	$\{H\}$	$\{T\}$	$\{H,T\}$
$P(x)$	0	0.5	0.5	1

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)$ .

Role in statistical teaching and theory

The probabilistic and statistical properties of coin-tossing games are often used as examples in both introductory and advanced text books and these are mainly based in assuming that a coin is fair or "ideal". For example, Feller uses this basis to introduce both the idea of random walks and to develop tests for homogeneity within a sequence of observations by looking at the properties of the runs of identical values within a sequence.^[3] The latter leads on to a runs test. A time-series consisting of the result from tossing a fair coin is called a Bernoulli process.

Fair results from a biased coin

If a cheat has altered a coin to prefer one side over another (a biased coin), the coin can still be used for fair results by changing the game slightly. John von Neumann gave the following procedure:^[4]

Toss the coin twice.
If the results match, start over, forgetting both results.
If the results differ, use the first result, forgetting the second.

The reason this process produces a fair result is that the probability of getting heads and then tails must be the same as the probability of getting tails and then heads, as the coin is not changing its bias between flips and the two flips are independent. This works only if getting one result on a trial does not change the bias on subsequent trials, which is the case for most non-malleable coins (but not for processes such as the Pólya urn). By excluding the events of two heads and two tails by repeating the procedure, the coin flipper is left with the only two remaining outcomes having equivalent probability. This procedure only works if the tosses are paired properly; if part of a pair is reused in another pair, the fairness may be ruined. Also, the coin must not be so biased that one side has a probability of zero.

This method may be extended by also considering sequences of four tosses. That is, if the coin is flipped twice but the results match, and the coin is flipped twice again but the results match now for the opposite side, then the first result can be used. This is because HHTT and TTHH are equally likely. This can be extended to any multiple of 2.

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:

Graph of
1
P
(
H
)
(
1
-
P
(
H
)
)
{\displaystyle {\frac {1}{P(H)(1-P(H))}}}
the further away
P
(
H
)
{\displaystyle P(H)}
is from
0.5
{\displaystyle 0.5}
the further expected number of flips before a successful result ExpectationVonNeumannCoin.gif — Graph of ${\frac {1}{P(H)(1-P(H))}}$ the further away $P(H)$ is from $0.5$ the further expected number of flips before a successful result

${\begin{aligned}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{aligned}}$

$\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.

A better algorithm when P(H) is known

Suppose that the bias $b:=P({\mathtt {H}})$ is known. In this section, we provide a simple algorithm^[5] that improves the expected number of coin tosses. The algorithm utilizes an ideal probability $p$ , which We first consider an algorithm to generate an arbitrary coin with bias $b$ . To get a fair coin, the algorithm first sets $p=0.5$ and then executes the following algorithm.

Toss the biased coin, let $X\in \{{\mathtt {H}},{\mathtt {T}}\}$ be the result.
If $p\geq b$ , use ${\mathtt {H}}$ if the flip result is $X={\mathtt {H}}$ . Otherwise, replace $p$ to be $p\gets {\frac {p-b}{1-b}}$ and go back to step 1.
Otherwise, $p<b$ , use ${\mathtt {T}}$ if the flip result is $X={\mathtt {T}}$ . Otherwise, Set $p$ to be $p\gets {\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 reaches this optimal value in expectation. However, those algorithms are more sophisticated than the one showed above.

The above algorithm has an expected number of biased coinflips being ${\frac {1}{2b(1-b)}}$ , which is exactly half comparing with von Neumann's trick.

Analysis

The correctness of the above algorithm is a perfect exercise of conditional expectation. We now analyze the expected number of coinflips.

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<b\\1+(1-b)\cdot f_{b}\left({\frac {p-b}{1-b}}\right)&{\text{if }}p\geq b\end{cases}}

This magically 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.

Remark

The idea of this algorithm can be extended to generating any biased coin with a specified probability.

Related Research Articles

In probability theory and statistics, the binomial distribution with parameters n and p is the discrete probability distribution of the number of successes in a sequence of n independent experiments, each asking a yes–no question, and each with its own Boolean-valued outcome: success or failure. A single success/failure experiment is also called a Bernoulli trial or Bernoulli experiment, and a sequence of outcomes is called a Bernoulli process; for a single trial, i.e., n = 1, the binomial distribution is a Bernoulli distribution. The binomial distribution is the basis for the popular binomial test of statistical significance.

In information theory, the entropy of a random variable is the average level of "information", "surprise", or "uncertainty" inherent to the variable's possible outcomes. Given a discrete random variable $, which takes values in the alphabet and is distributed according to, the entropy is$

In probability theory, the sample space of an experiment or random trial is the set of all possible outcomes or results of that experiment. A sample space is usually denoted using set notation, and the possible ordered outcomes, or sample points, are listed as elements in the set. It is common to refer to a sample space by the labels S, Ω, or U. The elements of a sample space may be numbers, words, letters, or symbols. They can also be finite, countably infinite, or uncountably infinite.

In probability theory, an elementary event, also called an atomic event or sample point, is an event which contains only a single outcome in the sample space. Using set theory terminology, an elementary event is a singleton. Elementary events and their corresponding outcomes are often written interchangeably for simplicity, as such an event corresponding to precisely one outcome.

The likelihood function is the joint probability mass of observed data viewed as a function of the parameters of a statistical model. Intuitively, the likelihood function $is the probability of observing data assuming is the actual parameter.$

In probability and statistics, a Bernoulli process is a finite or infinite sequence of binary random variables, so it is a discrete-time stochastic process that takes only two values, canonically 0 and 1. The component Bernoulli variablesX_i are identically distributed and independent. Prosaically, a Bernoulli process is a repeated coin flipping, possibly with an unfair coin. Every variable X_i in the sequence is associated with a Bernoulli trial or experiment. They all have the same Bernoulli distribution. Much of what can be said about the Bernoulli process can also be generalized to more than two outcomes ; this generalization is known as the Bernoulli scheme.

In statistics, maximum likelihood estimation (MLE) is a method of estimating the parameters of an assumed probability distribution, given some observed data. This is achieved by maximizing a likelihood function so that, under the assumed statistical model, the observed data is most probable. The point in the parameter space that maximizes the likelihood function is called the maximum likelihood estimate. The logic of maximum likelihood is both intuitive and flexible, and as such the method has become a dominant means of statistical inference.

In probability theory, the law of large numbers (LLN) is a mathematical theorem that states that the average of the results obtained from a large number of independent and identical random samples converges to the true value, if it exists. More formally, the LLN states that given a sample of independent and identically distributed values, the sample mean converges to the true mean.

In probability theory and statistics, the Bernoulli distribution, named after Swiss mathematician Jacob Bernoulli, is the discrete probability distribution of a random variable which takes the value 1 with probability $and the value 0 with probability . Less formally, it can be thought of as a model for the set of possible outcomes of any single experiment that asks a yes-no question. Such questions lead to outcomes that are Boolean-valued: a single bit whose value is success/yes/true/one with probability p and failure/no/false/zero with probability q . It can be used to represent a coin toss where 1 and 0 would represent "heads" and "tails", respectively, and p would be the probability of the coin landing on heads. In particular, unfair coins would have$

In probability theory, an event is said to happen almost surely if it happens with probability 1. In other words, the set of outcomes on which the event does not occur has probability 0, even though the set might not be empty. The concept is analogous to the concept of "almost everywhere" in measure theory. In probability experiments on a finite sample space with a non-zero probability for each outcome, there is no difference between almost surely and surely ; however, this distinction becomes important when the sample space is an infinite set, because an infinite set can have non-empty subsets of probability 0.

In probability theory, coupling is a proof technique that allows one to compare two unrelated random variables (distributions) $X$ and $Y$ by creating a random vector $W$ whose marginal distributions correspond to $X$ and $Y$ respectively. The choice of $W$ is generally not unique, and the whole idea of "coupling" is about making such a choice so that $X$ and $Y$ can be related in a particularly desirable way.

Amplitude-shift keying (ASK) is a form of amplitude modulation that represents digital data as variations in the amplitude of a carrier wave. In an ASK system, a symbol, representing one or more bits, is sent by transmitting a fixed-amplitude carrier wave at a fixed frequency for a specific time duration. For example, if each symbol represents a single bit, then the carrier signal could be transmitted at nominal amplitude when the input value is 1, but transmitted at reduced amplitude or not at all when the input value is 0.

In statistics, the question of checking whether a coin is fair is one whose importance lies, firstly, in providing a simple problem on which to illustrate basic ideas of statistical inference and, secondly, in providing a simple problem that can be used to compare various competing methods of statistical inference, including decision theory. The practical problem of checking whether a coin is fair might be considered as easily solved by performing a sufficiently large number of trials, but statistics and probability theory can provide guidance on two types of question; specifically those of how many trials to undertake and of the accuracy of an estimate of the probability of turning up heads, derived from a given sample of trials.

For supervised learning applications in machine learning and statistical learning theory, generalization error is a measure of how accurately an algorithm is able to predict outcome values for previously unseen data. Because learning algorithms are evaluated on finite samples, the evaluation of a learning algorithm may be sensitive to sampling error. As a result, measurements of prediction error on the current data may not provide much information about predictive ability on new data. Generalization error can be minimized by avoiding overfitting in the learning algorithm. The performance of a machine learning algorithm is visualized by plots that show values of estimates of the generalization error through the learning process, which are called learning curves.

In probability theory, the Kelly criterion is a formula for sizing a bet. The Kelly bet size is found by maximizing the expected value of the logarithm of wealth, which is equivalent to maximizing the expected geometric growth rate. Assuming that the expected returns are known, the Kelly criterion leads to higher wealth than any other strategy in the long run. J. L. Kelly Jr, a researcher at Bell Labs, described the criterion in 1956.

In information theory, the binary entropy function, denoted $or, is defined as the entropy of a Bernoulli process with probability of one of two values. It is a special case of, the entropy function. Mathematically, the Bernoulli trial is modelled as a random variable that can take on only two values: 0 and 1, which are mutually exclusive and exhaustive.$

The probability of the outcome of an experiment is never negative, although a quasiprobability distribution allows a negative probability, or quasiprobability for some events. These distributions may apply to unobservable events or conditional probabilities.

Algorithmic cooling is an algorithmic method for transferring heat from some qubits to others or outside the system and into the environment, which results in a cooling effect. This method uses regular quantum operations on ensembles of qubits, and it can be shown that it can succeed beyond Shannon's bound on data compression. The phenomenon is a result of the connection between thermodynamics and information theory.

Consider two remote players, connected by a channel, that don't trust each other. The problem of them agreeing on a random bit by exchanging messages over this channel, without relying on any trusted third party, is called the coin flipping problem in cryptography. Quantum coin flipping uses the principles of quantum mechanics to encrypt messages for secure communication. It is a cryptographic primitive which can be used to construct more complex and useful cryptographic protocols, e.g. Quantum Byzantine agreement.

In information theory, the Bretagnolle–Huber inequality bounds the total variation distance between two probability distributions $and by a concave and bounded function of the Kullback-Leibler divergence . The bound can be viewed as an alternative to the well-known Pinsker's inequality: when is large, Pinsker's inequality is vacuous, while Bretagnolle-Huber remains bounded and hence non-vacuous. It is used in statistics and machine learning to prove information-theoretic lower bounds relying on hypothesis testing$

References

↑ Kerrich, John Edmund (1946). An experimental introduction to the theory of probability . E. Munksgaard.
↑ Jaynes, E.T. (2003). Probability Theory: The Logic of Science. Cambridge, UK: Cambridge University Press. p. 318. ISBN 9780521592710. Archived from the original on 2002-02-05. anyone familiar with the law of conservation of angular momentum can, after some practice, cheat at the usual coin-toss game and call his shots with 100 per cent accuracy. You can obtain any frequency of heads you want; and the bias of the coin has no influence at all on the results!{{cite book}}: CS1 maint: bot: original URL status unknown (link)
↑ Feller, W (1968). An Introduction to Probability Theory and Its Applications. Wiley. ISBN 978-0-471-25708-0.
↑ von Neumann, John (1951). "Various techniques used in connection with random digits". National Bureau of Standards Applied Math Series. 12: 36.
↑ Henry Tsai, 2024 April 12.