Hacker News Reader

Comment by madcaptenor | Hacker News Reader

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

View on HN

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!

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

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

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.

Reply on news.ycombinator.com