5 ms·
Coin Flip Brain Teaser
This is a brain teaser we've been batting around the office this morning. Figured I'd see if HN could come up with a more definitive answer.
I have a coin with a 51% probability of landing on heads, and 49% probability of landing on tails.
I call heads 100% of the time.
My opponent calls tails 100% of the time.
If the coin lands on heads, I get $1, and my opponent loses $1.
If the coin lands on tails, my opponent gets $1, and I lose $1.
How many coin flips do I need to do in order to earn $10 with a 99% certainty?
- deleted 17y ago[deleted]
- noodle 17y agothere is no guarantee that every 100 flips will shake out exactly 51/49.
- deleted 17y ago[deleted]
- zackattack 17y agoPlease don't post in a math thread if you don't know what you're talking about. Misinformation is really anti-social.
- khafra 17y agoIn this context, "99% certainty" refers to a specific prediction interval, not "a guess I'm pretty confident in," like it would in colloquial speech. http://en.wikipedia.org/wiki/Prediction_interval http://en.wikipedia.org/wiki/Prediction_interval may help.
- tome 17y agoPlease don't upvote this, it's simply wrong.
- deleted 17y ago[deleted]
- deleted 17y ago[deleted]
- tome 17y agoThat calculation shows that after 500 flips your expected profit is $10, which is not the same as the question that was asked.
- bsaunder 17y agoYou didn't include the work required for the 99% confidence interval that the original post asked for. It requires statistics, not simple math.
- madcaptenor 17y agoStatistics is math.
- Nwallins 17y agoIt ain't simple.
- bradlane 17y agobecause your calculation assumes that out of 100 flips, heads always gets 51 out of 100, which is not how probability works - it's not linear (for lack of a better word). It's possible to be up $10 in just 10 flips, just as it's possible to be even at 1,000,000 flips (though neither very likely, but possible!). Also, the question asked "with a 99% certainty", which your answer doesn't take into account. If you had a coin that when flipped had these odds, and you wanted to try this out, your answer of 500 would be a good rough estimate, but not the answer.
- deleted 17y ago[deleted]
- asorbus 17y agoIs it that you earn ten dollars before your opponent, or just that you earn ten dollars?
- uptown 17y agoThat you earn $10 with 99% certainty.
- asorbus 17y agoDoing the 99% certainty part I'm pretty sure requires that you calculate a confidence interval http://en.wikipedia.org/wiki/Confidence_interval http://en.wikipedia.org/wiki/Confidence_interval although that article hasn't helped me remember how to do that
- aidenn0 17y agoIt's impossible to earn 10 dollars before your opponent with 99% certainty.
- tome 17y agoThe number of dollars you win out of N flips is 2W - N, where W ~ B(N,0.51). So, your question is: What is the minimum value of N such that P(2W - N >= 10) >= 0.99, i.e. P(W >= 5 + N/2) >= 0.99. So calculate Sum from {n = 5 + N/2} to {n = N} of P(W = n) for some different values of N, and see what you get! [P(W = n) = (N choose n) 0.51^n 0.49^(N-n)]
- zackattack 17y agoWhat is W?
- tome 17y agoW ~ B(N, p) means W is a binomial random variable: the number of heads you get from N independent coin flips each with probability p of coming up heads.
- zackattack 17y agoThere's got to be a better way to express summations and combinations on the internet. Did you see that link posted earlier?
- tome 17y agoNo I didn't. Could you please repost? I'd be interested.
- zackattack 17y agohttp://detexify.kirelabs.org/classify.html http://detexify.kirelabs.org/classify.html
- madcaptenor 17y agoYeah, but that just tells you how to write the symbol in LaTeX. HN doesn't support LaTeX so that's no good. What tome wrote is basically LaTeX stripped of some of the syntax that makes it unambiguous for computers but hard to read for humans. This is basically the standard way of writing mathematics in a plain-text setting.
- zackattack 17y agoNo idea how to solve this. You want to solve for p = .01.
- deleted 17y ago[deleted]
- deleted 17y ago[deleted]
- Jopius 17y ago70 exp: after 7 flips 99% probability of earning $1 (1-(0,49^7)) times 10
- deleted 17y ago[deleted]
- bcater 17y agoThis is all scribbled in a notebook, so there's a good chance that it's wrong, but bear with me on the arithmetic. As a first guess, let's agree that in expectation you earn $0.51 each time you flip the coin, so it should take you about 20 tries to reach $10. Let's do something better, though. EDIT: The previous paragraph is totally wrong. Thanks, tome :) Let's build a confidence interval with alpha = 0.01 so that (1 - alpha) = 0.99. First, we'll need some trials. For that, I wrote a program that flipped a weighted coin and played the game until it reached $10 using the rules that you described. I recorded the number of coin flips required in each of 15 trials: 298, 84, 268, 2712, 110, 66, 42, 128, 84, 48, 280, 80, 64, 42, 234 We'll need the sample mean, X_bar = 302. Now, we'll compute the Z-score so that we can build an interval in which the true mean (mu) lies with 99% probability: P(-z <= Z <= z) = 0.99 We know that Z = (302 - mu) / (sigma / sqrt(n)), where sigma (the standard deviation) = 650 and sqrt(n) = 4. I'm rounding. Therefore, Z = (302 - mu) / 168. Now, let's look at the cumulative distribution function Phi(z) and note that if Phi(z) = 1 - (alpha / 2) = 0.995, then Phi(z) ~= 0.997, the approximate cutoff for the 3rd standard deviation. Thus, z ~= 3. Thus, we have that P(-3 <= (X_bar - mu) / (sigma / sqrt(n)) <= 3) = 0.99, so P(X_bar - 504 <= mu <= X_bar + 504) = 0.99. Therefore, I am 99% confident that the true mean, mu, lies on [X_bar - 504, X_bar + 504] = [302 - 504, 302 + 504]. That's a really wide range, and seemingly completely unhelpful for the purposes of betting. More sample trials would teach us more and lead us to a smaller interval since we expect that within some large number of trials we will converge on mu.
- tome 17y agoYour expected earning on each flip is $0.02 not $0.51!
- bcater 17y agoYou're exactly right. Whoops!
- madcaptenor 17y agoI like the idea of simulating. But not all distributions are normal! In particular there's no reason to expect the distribution of hitting times to be normal, and intuitively it seems like the distribution would be very far from normal. I wrote a program and did ten thousand trials; the 100th largest hitting time was 5578, which is my estimate of the 99th percentile of the distribution, and thus the answer to the version of the original problem where we don't have to fix the number of coin flips ahead of time. The median hitting time from my simulation is 152; the mean, 506, the standard deviation, 1155. Yes, the standard deviation is larger than the mean! The distribution has a very long right tail. I'm fairly confident (in an informal sense) that the median of the true distribution is somewhere near 152, but I'm not confident about the mean or standard deviation. A lot of distributions in problems like this have tails which decay only like power laws, which makes estimating the mean and standard deviation from a sample very difficult. (I'm not saying that the distribution is a power law, though; it's hard to identify those just by looking at the data.)
- deleted 17y ago[deleted]
- czar235 17y agoCan we set up the problem this way: sum_{i=0}^k [(10+k) choose (10+i)] (.51)^(10+i) >= .99 find the minimum value of k that satisfies the inequality.
- madcaptenor 17y agoEverybody's assuming that you have to fix the number of coin flips in advance. (This includes my calculation below, which is basically tome's result using a normal approximation to the binomial.) But that was never explicitly stated. You could imagine that you wait until you've got $10 and then walk away; the time until this happens would be shorter. I'd approximate the amount of money you have as a Brownian motion with drift and use that to compute. But I can't do the actual computation right now (I don't have that stuff memorized and don't have the right books where I am).
- jongraehl 17y agoInteresting angle (it certainly makes a slight difference if you walk away at exactly $10 up), but the question asked gets the majority interpretation from me.
- dadkins 17y agoI decided to try to figure it out from this angle. What we have is a random walk where, with probability 0.51 we go forward, and with probability 0.49 we go backward. If we ever reach 10, we quit. I wrote a program to compute the cumulative probability that we stop at 10 over time. #include <stdio.h> #include <math.h> #define GOAL 10 #define MAXN 20000 double p = 0.51; double pr[2][MAXN + 1 + GOAL]; #define PR_(t, x) (pr[(t) % 2][MAXN + (x)]) int main() { int n, i; double totalp = 0; PR_(0, 0) = 1; for (n = 1; n <= MAXN; n++) { PR_(n, -n) = PR_(n-1, -n+1) * (1 - p); for (i = -n+1; i < GOAL; i++) PR_(n, i) = PR_(n-1, i-1) * p + PR_(n-1, i+1) * (1 - p); totalp += PR_(n-1, GOAL-1) * p; printf("n=%d p=%g\n", n, totalp); if (totalp >= 0.99) break; } return 0; } The results: n=5488 p=0.989997 n=5489 p=0.989997 n=5490 p=0.990005 You get to quit much sooner if you can walk away as soon as you have $10!
- madcaptenor 17y agoSomehow I wasn't seeing the exact formulas, even though I simulated it and got a similar answer.
- aidenn0 17y ago
- dadkins 17y agoLet X be a random variable indicating the number of heads that have come up. After n flips, E[x] = pn, where p = 0.51 in our case. When X >= n/2 + 5, we're up 10 dollars. In other words, we want to find n such that Pr[X < n/2 + 5] < .01 If we express that in terms of the mean, we can apply a Chernoff bound: Pr[X <= E[X] - a] <= Exp[-2a^2/n], for 0 < a < E[X] If E[x] = pn, then a = pn - (n/2 + 5), which for p = 0.51 is a = .01n - 5. So, solving Exp[-2a^2/n] = .01 (with help from Wolfram alpha) gives a quadratic equation with two solutions: n = 348.257 and n = 651.743 The first is too small, a would be negative (n needs to be at least 500). The second is good enough. 652 does the trick.
- madcaptenor 17y agoI like the idea of using a Chernoff bound, but 652 is way too low to be the answer! But I get, as solutions for exp(-2(.01n-5)^2 / n) = .01, n = 10.4 and n = 24015.
- dadkins 17y agoOh you're right, that's the solution. Silly me, the moment I go to a computer to solve the final equation I get it wrong!
- aidenn0 17y agoWith GNU R: require(graphics) netgain <- function(x) { 2*qbinom(.01,x,.51)-x } plot(1:25000,netgain(1:25000)) plot(10000:15000,netgain(10000:15000)) The first plot is interesting because it shows you are not expected to win anything with 99% certainty until around 13000 tosses.
- joecool 17y agostatistically, after 100 flips, you'd be up 2 dollars. so it would take 500 flips.
- joecool 17y agostatistically, after 100 flips, you'd be up $2. so it would take 500 flips.