Coin Flip Brain Teaser | Hacker News Reader

Coin Flip Brain Teaser

21 pointsuptown47 comments

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?

View on HN

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

What is W?

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.

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

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

http://detexify.kirelabs.org/classify.html

Yeah, 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.

You missed my intention. My point is that there's got to be a better way. That link shows important progress towards the next step: expressing equations, translating them into LaTeX, and then rendering them into image (e.g. png) form.

I think he was asking for a numeric answer.

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

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

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.

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

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

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.

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!

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

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)) #'> )))

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.

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

You're exactly right. Whoops!

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

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

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.

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.

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.

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!

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.

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

That you earn $10 with 99% certainty.

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

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

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

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

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

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

times 10

Reply on news.ycombinator.com