There were quite some places in mathematical problems in which a condition imposed to make the problem supposedly difficult actually turns out to be irrelevant. The first instance where I saw something like this in the 'Compass and Straight edge constructions' in which the concept of collapsible compass actually turns out to be irrelevant. This fact is called the Compass Equivalence Theroem.
In this post, we see one such 'irrelevance' in probability theory. I've often wondered whether actual coin tosses are really fair and, if not, how to make them fair. I did some searches and quite surprised to see that this turns out be an easy problem with a simple solution (atleast in theory).
Consider you've a coin with a probability $p$ of turning up heads. Say you want to create a game out of this coin such that each player has a $50\%$ probability of winning. This can be done by the following procedure:
Toss the coin twice. If the results of both the tosses are same, ignore the two tosses and toss again. Repeat until you've different results in both the tosses. Now if the result is $HT$, the first player wins. Else, the second player does.
This works because $\mathbb{P}(HT)=p(1-p)$ whereas $\mathbb{P}(TH)=(1-p)p$.
As both has the same probability of happening and these are the only two outcomes. (Note that, we have toss the coin in 'twos' and we can't combine the intermediate parts of two tosses).
The beauty of this procedure is two-fold. First, the entire argument boils down to the commutative property of multiplication and the second is that we don't even have to know what the unfair probability is. Incredible!!
Now that we have dealt with making an unfair coin to come up with a fair result, let's look at the other way. Now we have a fair coin; how can we make game in which the winning probability of someone is $\alpha$.
This again has a simple solution. Cast the real number $\alpha$ in binary terms. Flip the fair coin until it gives the first Head. Now the player wins, if the $n$th digit in the binary expansion is $1$ and loses otherwise.
Say for example, $\alpha=\frac{3}{4}=(0.11)_2$. Now the player wins if the first Heads appears in first or the second toss and loses otherwise.
$\mathbb{P}(Win)=\mathbb{P}(\text{First Head in }1^{st}\text{ toss})+\mathbb{P}(\text{First Head in }2^{nd}\text{ toss})=\frac{1}{2}+\frac{1}{4}=\frac{3}{4}$.
All this means is that we can take any (un)fair coin with arbitrary probability $p$ and use it to create an arbitrary probability $\alpha$ of winning for some player. In other words, the bias doesn't matter.
The only difference would be that would be needing more and more tosses for the game to conclude depending the unfairness of the coin and winning probability. With that in mind, we will do something more.
Say we want to create a equal probability of winning between three players with an unfair coin. We can directly generalize the first argument and achieve this with the following procedure.
Toss the coin thrice. If all the results are the same, repeat. Else, either exactly one Heads has appeared or exactly one Tails. Assume WLOG, exactly one Heads. Then the the First player wins if the Heads happened in the first toss, the Second player wins if it did in the second toss else the third player wins.
This procedure can be applied to $4$ players, $5$ players, .. Oh wait, for $6$ players, we can do better. Instead of making six tosses every time and waiting for exactly one Heads (or one Tails), we can do it with four tosses.
Toss the coin $4$ times until exactly two Heads appear. Discard other batches of four tosses. Now the First player wins when the Heads occur in positions $(1,2)$, Second wins in positions $(1,3)$, Third wins in $(1,4)$, Fourth in $(2,3)$, Fifth in $(2,4)$ and the Sixth in $(3,4)$.
Similarly, among $10$ players, instead of tossing the coin in batches of ten, we can toss it in batches of five and wait for exactly two Heads (or two Tails) to appear.
By now one can see that we can use the unfair coin and create a game with equal probability of winning among $\binom{n}{k}$ players. Though I'vnt done much analysis further, a judicious choice depending on $n$, $k$ and $p$ will lead to shorter games than the other choices available. Quite neat, don't you think?
Yours Aye
Me
No comments:
Post a Comment