Coin Flip Brain Teaser

[uptown]

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?

[tome]

The 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)]

[splat]

Solving this numerically, I get 14414.

I used the following line of Mathematica code:

For[n=14400, Sum[PDF[BinomialDistribution[n,.51],k],{k,n/2+5,n}] < .99, n++, Null]; Print[n]

(I played around with it a little to guess the initial value of 14400, just so it wouldn't take forever to run....)

[rarestblog]

I think he was asking for a numeric answer.

[zackattack]

There's got to be a better way to express summations and combinations on the internet. Did you see that link posted earlier?

[zackattack]

What is W?

[madcaptenor]

Everybody'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).

[dadkins]

I 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!

[jongraehl]

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

[bcater]

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

[madcaptenor]

I 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.)

[tome]

Your expected earning on each flip is $0.02 not $0.51!

[bcater]

After 1 million trials with the above method I get: avg: 499.00 sigma: 1115.04 [499.00 - 3.35,499.00 + 3.35]

[aidenn0]

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

[dadkins]

Let 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]

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

[czar235]

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

[asorbus]

Is it that you earn ten dollars before your opponent, or just that you earn ten dollars?

[uptown]

That you earn $10 with 99% certainty.

[aidenn0]

It's impossible to earn 10 dollars before your opponent with 99% certainty.

[joecool]

statistically, after 100 flips, you'd be up 2 dollars. so it would take 500 flips.

[joecool]

statistically, after 100 flips, you'd be up $2. so it would take 500 flips.

[zackattack]

No idea how to solve this. You want to solve for p = .01.

[tome]

Please don't upvote this, it's simply wrong.

[noodle]

there is no guarantee that every 100 flips will shake out exactly 51/49.

[Jopius]

70

exp: after 7 flips 99% probability of earning $1 (1-(0,49^7))

times 10