What is probability of success?

Question

Casino offers a simple game:
You toss a coin, heads you win $1, tails you lose $1.

John enters the casino with $1000 in his poket and plans to toss a coin until he makes +$100, then grab the cash and leave.

What is the probability that his plan will be successful?

Answer 1

Let P be the probability that his strategy wins. We'll make successive approximations of P: P1, P2, P3, ...

The chance of getting to 100 first vs. getting to -100 first is 1/2 (eventually one will be reached, even if it takes a while). Therefore, his success rate is at least 50%.

We are up to P1 = 1/2
Let's consider what happens if he gets to -100 first. Then there is a 50% chance that he gets to +100 before he gets to -300 (a run of 200 in either direction).

We are up to P2 = 1/2 + (1/2)*(1/2)
Let's consider what happens if he gets to -300 first. Then there is a 50% chance that he gets to -700 before he gets to 100 (run of 400 in either direction).

We are up to P3 = 1/2 + (1/2)* (1/2 + (1/2)*1/2)
Let's consider what happens if he gets to -700 first. Then there is a 50% chance that he gets to -1000 before he gets to -400 (run of 300 in either direction).

We are up to P4 = 1/2 + (1/2)^2 + (1/2)^3 - (1/2)^4
Let's consider what happens if he gets to -400 first. Then there is a 50% chance that he gets to 100 before -1000 (run of 500).

Note that minus sign. Getting to -1000 first means a subtraction. Getting to 100 first means an addition. This process will eventually cycle so I'm going to list the rest table like:

Entries:
previous position
where a + run goes to (50% chance)
where a - run goes to (50% chance)
Next two possibilities:
Resulting formula: Which we will write as a base 2 fraction.

0 100 -100 P1 = 1/2 = .1
-100 100 -300 P2 = ½ + ½^2 = .11
-300 100 -700 P3 = ½ + ½^2 + ½^3 = .111
-700 -400 -1000 P4 = ½ + ½^2 + ½^3 - ½^4 = .1110 - .0001
-400 100 -900 P5 = ½ + ½^2 + ½^3 - ½^4 + ½^5 = .11101 - .00010
-900 -800 -1000 P6 = ½ + ½^2 + ½^3 - ½^4 + ½^5 - ½^6 = .111010 - .000101
-800 -600 -1000 P7 = .1110100 - .0001011
-600 -200 -1000 P8 = .11101000 - .00010111
-200 100 -500 P9 = .111010001 - .000101110
-500 0 -1000 P10 = .1110100010 - .0001011101

0 100 -100 P11 = .11101000101 - .00010111010
That is
P11 = ½ + ½^2 + ½^3 - ½^4 + ½^5 - ½^6 - ½^7 - ½^8 + ½^9 - ½^10 + ½^11

Note that this cycle will repeat so that we get
P∞ = ½ + ½^2 + ½^3 - ½^4 + ½^5 - ½^6 - ½^7 - ½^8 + ½^9 - ½^10 + P∞/2^10

In other words:
P = P∞ = .1110100010 - .0001011101 + P/2^10
or
P = .1101000101 + P/2^10
P = ½ + ½^2 + ½^4 + ½^8 + ½^10 + P/2^10
Multiplying through by 2^10 yields

1025P = 512 + 256 + 64 + 4 +1 = 837

So P = probability he walks away a winner = 837 / 1025,
which is about 81.6585%. Seems pretty good, right?


But it isn't. It's a losing strategy since his expected value is:
100P * 1000(1-P) = 100(11P - 10)
= 100 (9207 -10250) / 1025
= -4 * 7 * 149 / 41
which is negative and approximately -101.756
About four times out of 5 he's a winner, but when he loses, he loses big.

-------------------------
Showers are good. That's where you often times figure out where you messed up. In the case at hand, all those subtractions of ½^n up above should be 0.

So it should really be:
P = ½ + ½^2 + ½^3 + ½^5 + ½^9 + P/2^10
Multiplying through by 2^10, and SUBTRACTING instead of adding =>
(3*341)P = 512 + 256 + 128 + 32 + 2 = 930
So his probability of winning is
P = 310/(3*11²),
which is about .90909

The expected value of his winnings is
100(11P - 10) = 100(310/33 - 10) = -2000 / 33,
which is about -$60.61

And hopefully I haven't mucked anything up this time around.

-------------------------
Well, that's what I get for three hours of sleep. At least I got further this time. So where was I? Oh, yes...
(3*341)P = 930
It turns out that 341 is actually 31 * 11, and not 33 * 11 as some people would have you think. Thanks to the wiseguy who pointed this out.
(3 * 31 * 11)P = 3 * 31 * 10
So
P = 10/11, which is about .90909

So the expected value of his winnings is
100(11P - 10) = 100(10 - 10) = 0
That may have been the whole point of the problem.

Answer 2

Pretty high, but he'll be there forever.

What we want is the probability he will get +100 before -1000, or, 1 minus the probability he gets -1000 before +100.

The probability he gets -$1000 in exactly n tosses, where n is even and greater than or equal to 1000, is:
A(n) = 0.5^n * (n choose (n-1000)/2)

The probability he FIRST gets -$1000 in exactly n tosses, where n is even and greater than or equal to 1000, is:
F(n) = A(n) – Sum (k = 500 to n/2-1) of F(2k)

However, in these n tosses, he cannot have ever gotten to +100. This means that those n-1000/2 heads couldn't have been anywhere...

And now, this is really ugly...

Umm... everyone else has flawed logic here... and I'm not even sure that I didn't make a mistake in my work...

Knowmeansknow and Quadrillerator: the problem is that although it is easy to use binomials to get the probability he gets -1000 in any given amount of flips, we need to make sure he doesn't get +100 before that. which makes this problem REALLY ugly. It looks like you guys both had good work though... I didn't check it but yeah.

Answer 3

Good question!

I think his chance of success is pretty close to 100% IF time is not an issue. All John needs to do to win is have 100 more heads than tails. To lose, he needs 1000 more tails than heads.

To calculate probability, we need the binomial standard deviation, which is given as sqrt(N*p*(1-p)), where N is number of tosses, and p is the probability (0.5). For 1000 tosses, the standard deviation is sqrt(1000*0.5*0.5) = 15.8. The rule of normal probability means there is a 68.2% chance that the number of heads will be within one standard deviation of the expected number of heads (so, 500 +/- 15.8, or between 484 and 516 heads).

If you increase the number of tosses to 40000, the standard deviation is 100, meaning there is a 68.2% chance that the number of heads will be between 19900 and 20100. There is also a 95.45% chance that the number of heads will be within 2 standard deviations of the mean (between 19800 and 20200 heads). The odds increase to 99.99999999974% for being within 7 standard deviations of the mean (between 19300 and 20700 heads).

As John keeps tossing the coin, the standard deviation continues to increase, which will, in turn, increase the chances of being +100 on heads. Regardless of the number of tosses, the odds of having +100 on heads will always be much greater than the odds of having -1000.

There's a good chance it could take 100,000 or more tosses for John to win his $100. There's probably more efficient ways to make that money.

-----------

Quadrill below is correct (that is, his second corrected answer is correct). Nice work!

Answer 4

Nearly 0. There is a 1/2 chance of a getting a head when a coin is tossed. So he might lose nearly as much as he gains. So, there is almost no way he can get +100 heads without tossing nearly 10000 times. Nobody would try that long.

Answer 5

If it is a fair coin, then you have a 50-50 chance of getting a head or a tail with each toss.

The expectation of this game = 0.5(1) + 0.5(-1) = 0
So the outcome in the long run, is that he will make $0, not $100

Answer 6

P = (1/2)^100 + (1/2)^102 + (1/2)^104 + . . .
P = (1/2)^100∑1 + (1/2)^2 + (1/2)^4 . . . for 999 terms
r = (1/2)^2
S = (1 - (1/2)^2000)/(1 - 1/4)
P ≈ 1.0518*10^-30

Answer 7

If luck is on his side he may actually make a 100$.But if it isn't on his side he may make it but would take him approximately 1and a half days.It depends on his strategy and luck.