Abrazolica

How To Simulate a Coin Toss With Three People

You can create the equivalent of a coin toss with no coins, no dice, or any other kind of randomizing device. All you need is three people. Have each person pick a positive integer of any size and write them down. To simulate the coin toss, you check to see if the sum of any two of the numbers is greater than the third. If it is, the toss is a head and if not, the toss is a tail. More precisely, if $x$, $y$, and $z$ are the three numbers and $x+y > z$, $x+z > y$, $y+z > x$, then the toss is heads otherwise the toss is tails. Amazingly this test will simulate a fair coin toss.

As an alternative to having a person pick a number you could just use the day of the month they were born. Since the numbers cannot be larger than 31 this method will not give you a perfectly fair coin toss but it will be extremely close to fair. When the numbers are limited to being no larger than $n$ then the probability that the sum of any two numbers is greater than the third (coin comes up heads) is given by:

$p(n)=\frac{1}{2}+\frac{1}{2n^2}$

For $n=31$ this differs from $1/2$ by only $.0005203$. If you use the birth month then $n=12$ and the probability differs from $1/2$ by $.01020408$ which is still pretty close to being fair. The birth year will not work because the possible numbers must range from $1$ to $n$ and there's no one alive that was born in the year $1$, I think. From the equation you can see that if there is no limit to how large the numbers can be, i.e. let $n$ go to infinity, then the probability becomes exactly $1/2$.

Now for a short sketch of why this works. Let $f(n)$ be the number of ways to pick three integers between 1 and $n$ so that the sum of any two is greater than the third, then $f(n)-f(n-1)$ will be the number of ways where at least one of the integers is equal to $n$. All three integers can equal $n$ in only one way. Two of the integers can equal $n$ either as $nnx$, $nxn$, or $xnn$ where $x$ ranges from 1 to $n-1$ so the number of ways this can happen is $3(n-1)$. One of the integers can equal $n$ in 3 ways with the other two chosen from 1 to $n-1$ in $\binom{n-1}{2}$ ways, so the number of ways this can happen is $3\binom{n-1}{2}$. The total number of ways where at least one of the integers equals $n$ is then

$f(n)-f(n-1)=1+3(n-1)+3\binom{n-1}{2}=1+3\binom{n}{2}$

When $n=1$ all three numbers must equal 1 and $f(1)=1$. The above equation then gives $f(2)=f(1)+4=5$. The five sets of integers in this case are (1,1,1), (1,2,2), (2,1,2), (2,2,1), and (2,2,2). Continuing on gives $f(3)=f(2)+10=15$, $f(4)=f(3)+19=34$, and so on. In general by iterating the equation you can see that $f(n)$ for $n\ge 2$ must be given by

$f(n)=n+3\sum_{k=2}^n\binom{k}{2}$

The sum in this equation reduces to $\binom{n+1}{3}$ so that after simplification you are left with

$f(n)=n(n^2+1)/2$

To get the probability you divide this by $n^3$ which is the total number of ways to pick three numbers from $1$ to $n$. This is where the formula for $p(n)$ comes from.

This problem comes from a book of probability problems that we will be publishing soon.

© 2010-2013 Stefan Hollos and Richard Hollos