Coin Flip Brain Teaser

https://news.ycombinator.com/item?id=721448

by uptown • 17 years ago

21 36 17 years ago

news.ycombinator.com

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?

asorbus2• 17 years ago

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

uptown• 17 years ago

That you earn $10 with 99% certainty.

asorbus2• 17 years ago

Doing the 99% certainty part I'm pretty sure requires that you calculate a confidence interval http://en.wikipedia.org/wiki/Confidence_interval although that article hasn't helped me remember how to do that

aidenn03• 17 years ago

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

tome5• 17 years ago

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

zackattack5• 17 years ago

What is W?

tome5• 17 years ago

W ~ 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.

zackattack5• 17 years ago

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

tome5• 17 years ago

No I didn't. Could you please repost? I'd be interested.

rarestblog• 17 years ago

I think he was asking for a numeric answer.

tome5• 17 years ago

If he wants one he can calculate it using the formula I've provided. A normal approximation to the binomial distribution might help too.

splat• 17 years ago

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

madcaptenor6• 17 years ago

I'm glad to see an answer from this approach. (Maple wasn't cooperating for me.) And notice that it compares well with the 14507 from the normal approximation to the binomial.

tspiteri• 17 years ago

I did it in C, my code was a bit longer. (And it has the advantage that you do not need an initial estimate for the problem to be solved in a very short time.)

    #include <math.h>
    #include <stdio.h>
    
    double p(int throws, double pwin, int req_wins)
    {
        int win, i;
        double log_dp = log(pwin) * throws;
        double log_loss_win = log((1 - pwin) / pwin);
        double ret = 0;
        for (win = throws, i = 0; win >= req_wins; win -= 2, ++i) {
            ret += exp(log_dp);
            log_dp += log_loss_win + log((throws - i) / (i + 1.0));
        }
        return ret;
    }
    
    int main()
    {
        double pwin = 0.51;
        int req_wins = 10;
        double conf = 0.99;
        int min, max = 1;
        while (p(max, pwin, req_wins) < conf)
            max *= 2;
        min = max / 2;
        while (min < max) {
            int mid = (min + max) / 2;
            if (p(mid, pwin, req_wins) < conf)
                min = mid + 1;
            else
                max = mid;
        }
        printf("For %d throws, P(win $10 or more) = %f\n"
               "For %d throws, P(win $10 or more) = %f\n",
               min - 1, p(min - 1, pwin, req_wins),
               min, p(min, pwin, req_wins));
    }

The output from this program:

    For 14413 throws, P(win $10 or more) = 0.989777
    For 14414 throws, P(win $10 or more) = 0.990004

zackattack5• 17 years ago

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

Jopius• 17 years ago

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

times 10

bcater3• 17 years ago

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.

tome5• 17 years ago

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

bcater3• 17 years ago

You're exactly right. Whoops!

madcaptenor6• 17 years ago

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

bcater3• 17 years ago

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

czar235• 17 years ago

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.

madcaptenor6• 17 years ago

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

jongraehl• 17 years ago

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.

dadkins3• 17 years ago

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!

madcaptenor6• 17 years ago

Somehow I wasn't seeing the exact formulas, even though I simulated it and got a similar answer.

aidenn03• 17 years ago

The following lisp simulation gets numbers on about the same order of magnitude:

    (defun flip () (if (< (random 100) 49) nil t))

    (defun game (n d)
      (declare (optimize speed))
      (if (>= d 10) n
        (if (flip)
          (game (incf n) (incf d))
          (game (incf n) (decf d)))))
  
    (print (nth 1000 (sort (loop for i from 1 to 100000
                    collect (game 0 0)) #'> )))

dadkins3• 17 years ago

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.

madcaptenor6• 17 years ago

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.

dadkins3• 17 years ago

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

aidenn03• 17 years ago

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.

joecool2• 17 years ago

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

joecool2• 17 years ago

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

Coin Flip Brain Teaser

Related Stories