4
$\begingroup$

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?

$\endgroup$
1
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This would imply that incorrect answers happen exponentially infrequently as a function of $k$. If so, that's great! $\endgroup$ – templatetypedef Feb 5 '14 at 20:54
  • 1
    $\begingroup$ I suspect the disagreement has to do with the fact that there is no fair coin in this problem. $\endgroup$ – John Habert Feb 5 '14 at 21:49
  • $\begingroup$ @JohnHabert: Whoops, you're right of course :). I've edited the numbers. $\endgroup$ – mjqxxxx Feb 5 '14 at 23:10
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I understand that this is the case, but how do I then determine the probability that the total sum is greater than 0? I can use this to easily get the expected value, but I don't see how this translates into a probability. $\endgroup$ – templatetypedef Feb 5 '14 at 19:34
  • $\begingroup$ Why would we subtract the tails? It's only the matter of heads count. $\endgroup$ – Hoda Feb 5 '14 at 19:51
1
$\begingroup$

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}}$$

$\endgroup$
1
  • $\begingroup$ Is there a simple way to get an asymptotic expression for this? $\endgroup$ – templatetypedef Feb 5 '14 at 21:08
0
$\begingroup$

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%.

$\endgroup$
2
  • $\begingroup$ Is there any way to get an asymptotic approximation of that summation? (I apologize if that's a tall order, but I have pretty much no idea how to determine just how likely or unlikely that is.) $\endgroup$ – templatetypedef Feb 5 '14 at 20:03
  • $\begingroup$ I'm not too good with asymptotics. :( Mathematica gives the result of the sum using its DifferenceRoot function, and it's pretty obscure to me. Hopefully someone else can help. If no one notices, you could ask a separate follow-up question about the asymptotics of the sum. $\endgroup$ – Steve Kass Feb 5 '14 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.