3 ms·

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 no

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 17y 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.
dadkins 17y 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!
- madcaptenor 17y ago
  Somehow I wasn't seeing the exact formulas, even though I simulated it and got a similar answer.
- aidenn0 17y 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)) #'> )))

jongraehl 17y 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.

dadkins 17y 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!

madcaptenor 17y ago
Somehow I wasn't seeing the exact formulas, even though I simulated it and got a similar answer.
aidenn0 17y 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)) #'> )))