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?