4 ms·
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 ba
by 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 agoSomehow I wasn't seeing the exact formulas, even though I simulated it and got a similar answer.
- aidenn0 17y agoThe 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)) #'> )))