Finding the better coin: what is the probability of success?

Question

Just for fun, I'm working my way through Motwani and Raghavan's Randomized Algorithms textbook. As part of a solution to one of the problems they've posed, I've come across a probability problem I don't know how to solve:

Suppose that you have two coins, one of which flips heads $\frac{2}{3}$ of the time and one of which flips heads $\frac{1}{3}$ of the time. You flip each coin $k$ times and guess which coin flips heads $\frac{2}{3}$ of the time by choosing the coin that flipped the most heads. (If there's a tie, assume that you guess incorrectly). What is the probability, as a function of $k$, that you choose the correct coin?

To try to solve this, I tried to model the distributions of heads from the coins as two binomial distributions and then subtracting them to get a distribution on the difference between the good coin's number of heads and the bad coin's number of heads, but I couldn't make much progress because I don't know how to subtract these distributions. I also tried modeling the binomial distributions as normal distributions and subtracting those, but ran into a similar problem (I don't know how to subtract them).

Does anyone have any advice on how to approach this problem?

Answer 1

You have some exact answers here, so I'll just answer the easier question: how do you approximate the result for large $k$? Place a counter at zero, then flip the head-weighted coin and the tail-weighted coin together $k$ times; move the counter to the right for each "good" flip on either coin and to the left for each "bad" flip. Per flip, each coin moves the counter $\pm 1$ with probabilities $2/3$ and $1/3$ respectively (mean $1/3$, variance $8/9$). Mean and variance simply add, so after $k$ flips you have a distribution with mean $2k/3$ and variance $16k/9$; and by the central limit theorem, the shape will be approximately Gaussian. You will make the wrong decision if the counter lands to the left of the origin, which happens with approximate probability $$ \frac{1}{2}\left(1+\text{erf}\left(-\frac{2k/3}{\sqrt{2\cdot 16k/9}}\right) \right)=\frac{1}{2}\left(1+\text{erf}\left(-\sqrt{\frac{k}{8}}\right)\right)\sim e^{-k/8}\sqrt{\frac{2}{\pi k}}. $$ These asymptotics indicate that you need $20-25$ flips to be $99\%$ confident in your choice, reasonably consistent with the exact answer given elsewhere.

Answer 2

Every time you get heads on the 2/3 coin, write +1; every time you get tails write -1.

Every time you get heads on the 1/3 coin, write -1; every time you get tails write +1.

You will get the right answer if your total at the end is positive.

---

More info by request: You have $2k$ events, and each of them has a good outcome (2/3 of the time), and a bad outcome (1/3 of the time). You need to have more than $k$ good outcomes to have a good result.

Answer 3

A head with the left coin as well as a tail with the right coin both support the hypothesis that the left coin is the pro-heads coin. In one arrangement of the coins both these events happen with $\frac 23$, in the other arrangement both hapen with $\frac13$. Your method of counting heads and assuming the coin with more heads is the pro-heads coin is equivalent to counting how many coin tosses support "left coin is pro-heads" vs. "right coin is pro-head" and going by majority. To elaborate: If $a,b,c,d$ are the numbers of heads left, tails left, heads right, tails right, then the original methods asks to decide by $a-c$, the other method compares $(a+d)-(b+c)$. But $a+b=c+d=k$, so this is just $a+(k-c)-(k-a)b-c =2(a-c)$.

So the question is: What is the probability that a $\frac23$ event occurs more than $k$ out of $2k$ times? For $k=1$ this is $\frac49$. For $k=2$ it is $\frac {2^4}{3^4}+4\cdot\frac{2^3}{3^4} =\frac{16}{27}$ and in general it is $$ \sum_{i=0}^{k-1}{2k\choose i}\frac{2^{2k-i}}{3^{2k}}$$

Answer 4

If a coin yields heads with probability $p$, the probability of exactly $h$ heads in $k$ tosses is $\displaystyle \binom k h p^h (1-p)^{k-h}$. You have two coins, one with $p=1/3$ and one with $p=2/3$. The coin flips are independent, so the probability of getting $i$ heads from the first coin and $j$ heads from the second coin is $\binom k i \left(\frac{1}{3}\right)^i \left(\frac{2}{3}\right)^{k-i}\cdot\binom k j \left(\frac{2}{3}\right)^j \left(\frac{1}{3}\right)^{k-j}$. The probability of choosing the correct coin is then $$\sum_{i<j} \left(\binom k i \left(\frac{1}{3}\right)^i \left(\frac{2}{3}\right)^{k-i}\cdot\binom k j \left(\frac{2}{3}\right)^j \left(\frac{1}{3}\right)^{k-j}\right)\textrm.$$ For what it's worth, it takes 26 flips for the probability of at good result to exceed 99%.