Expected value: biased coin flips

Got it! This site "robinsnyder.com" uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website. Note: This appears on each machine/browser from which this site is accessed.

A coin is flipped.

What are the possible outcomes?
What is the probability of each outcome?

We will ignore the possibility of the coin landing on edge. The "bottom" value "⊥" is the state where the result is not yet known.

A fair coin is a coin for which the probability of heads and tails is each 0.5.
A biased coin is a coin for which the probability of heads and tails are not each 0.5.

There is no issue with deciding an issue using a coin flip if the coin is fair.

But what if the coin is not fair

Suppose that two individuals want to use a coin flip to settle a dispute, but neither person trusts the other.

How would you use a (possibly biased) coin to perform the coin flip so that neither individual has an advantage?

John Von Neumann provided in interesting solution to this problem.

A clever solution to the problem of how to decide coin flips in the presence of possibly biased coins is due to John von Neumann (mathematician, computer scientist, etc.) , famous mathematician, statistician, operations researcher, computer scientist (traditional microprocessors are called Von Neumann machines), etc.

More: John von Neumann

Suppose you have a biased coin that has

Prob(heads) = 0.4, and
Prob(tails) = 0.6.

Here is the method. How can you insure fair coin flips in the presence of a potentially biased coin (Von Neumann)? For example, what if Prob(heads) is 0.6 and Prob(tails) = 0.4?

Two flips will be done.

How many possibilities are there?

There are 2*2 = 4 possibilities.

HH = Heads Heads (TP = True Positive) HT = Heads Tails (FP = False Positive) TH = Tails Heads (FN = False Negative) TT = Tails Tails (TN = True Negative)

What is the EV (Expected Value) of each of the four cases?

Here is the EV of each possibility.

EV(HH) = 0.4*0.4 = 0.16 EV(HT) = 0.4*0.6 = 0.24 EV(TH) = 0.6*0.4 = 0.24 EV(TT ) = 0.6*0.6 = 0.36

The two people decide who will have Heads-Tails and who will have Tails-Heads.

Flip twice until the flips come up either Heads-Tails or Tails-Heads. If the two flips come up Heads-Heads or Tails-Tails, the flips are done again until a winner is decided.

Is this a fair way to do it?

Here are the expected values of the choices.

EV(HT) = 0.4*0.6 = 0.24 EV(TH) = 0.6*0.4 = 0.24 EV(neither) = 0.6*0.6 = 0.52

Since the probability of HT and the probability of TH are the same, this is a fair way to do it.

How many flip pairs are needed, on average, until a winner is determined?

What is the chance that in 10 coin flips, you will get every coin flip as specified? For example:

H H H H H H H H H H (all heads)
T T T T T T T T T T (all tails)
H T H T H T H T H T (some other pattern)
... and so on ...

The chance of getting 10 coin flips exactly as specified is 1/1024. This is about 1/1000, or 1/10³.

1 / 210 = 1 / 2*2*2*2*2*2*2*2*2*2 = 1 / 1024 1 / 103 = 1 / 1000

In general, a probability of 1/10^3*m is about the same as a probability of 1/2^10*m. That is, 10*m coin flips. When m is 1 then 10 coin flips.

So the following hold as quick approximations.

To convert 10^m to binary, multiply m by 10 and divide by 3 to get 2^10*m/3.
To convert 2ⁿ to decimal, multiply n by 3 and divide by 10 to get 2^3*n/10.

So the following are quick approximations.

10¹⁵ ≈ 2⁵⁰
10¹⁸ ≈ 2⁶⁰
10²¹ ≈ 2⁷⁰
10²⁴ ≈ 2⁸⁰
10²⁷ ≈ 2⁹⁰

What is your probability of winning the super state lottery?

Your probability of winning the super state lottery is, say, about 1/1,000,000,000, one in a billion (i.e., one chance in thousand million).

What does this mean? Your probability of winning the super state lottery is about 1/1,000,000,000 = 1/10⁹ = 1/10^3*3 which is about 1/2^3*10 = 1/2³⁰.

Your probability of winning the super state lottery is about the same as flipping a coin 30 times and getting the desired result on each flip.

To put powers of ten into perspective, the concept of flipping a coin can be used to determine one unit of the measured quantity.

Powers Coin Measured of ten flips quantity --------- ----- -------- 1.00*109 30 Winning the super state lottery (1,000,000,000) 3.16*107 25 Seconds in a year (60*60*24*365.25) 3.65*1012 42 Days in 10 billion years (365.25*10,000,000,000) 3.15*1017 58 Seconds in 10 billion years 1*10*1080 266 Small particles in the known universe 3.15*1097 324 Second for every particle for 10 billion years

For a quick approximate conversion of a base 10 power to a base 2 power, take the power of ten, divide by 3 (i.e., 3 powers of ten, or a thousand), and multiply by 10 (i.e., 10 powers of 2, or just over a thousand).

1,000,000,000 (billion) ≈ 109 ≈ 2(9/3)*10 = 230

So, 2³² is about 4 billion.

Many people have played the game of 20 questions.

In 20 well-chosen questions, you can pick one thing from 2²⁰ ≈ 1,000,000 things (i.e., 20 flips).

1,000,000 = 106 ≈ 220

A practical working limit is much less than 1000 bits of information.

In general, even 200 bits of information would be highly unlikely.