Coin Flip Brain Teaser

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

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

    #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));
    }

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

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

70

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

times 10

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.

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.

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

  #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;
  }

  n=5488 p=0.989997
  n=5489 p=0.989997
  n=5490 p=0.990005

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

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.

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.

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.