Infinite Coin-Toss?
 

Hello everyone! :)

I have a probability problem which i found very amusing to solve..

You have a game that consists of tossing a coin which can land with "heads" up with probability (P) and land with "tails" up with probability (1-P).

The game stops whenever the amount of "heads" equals the amount of "tails". Except for when both are zero.

What is the probability of the game ending ever, given the probability P?

Happy solving! :banana:

I got as far as this sum:

Sum{n=1:infinity} p[sup]n[/sup](1-p)[sup]n[/sup](2n)!/(n!)[sup]2[/sup]

But I haven't spent too much time trying to evaluate it

Keep score as "net heads", so every head scores +1 and every tail scores -1. Suppose the first toss is a head. What is the probability that your score will ever get down one level from here? Well, you might get down one level immediately by throwing a tail (probability 1-p). But if you throw a head, ...

Saying any more gives it away completely.

[QUOTE][i]Originally posted by TravisT [/i]
[B]I got as far as this sum:

Sum{n=1:infinity} p[sup]n[/sup](1-p)[sup]n[/sup](2n)!/(n!)[sup]2[/sup]

But I haven't spent too much time trying to evaluate it [/B][/QUOTE]

Mathematica shows the sum is:

[CODE](1/|1-2p|)-1[/CODE] .

cool.

but what about when it's just a regular 50/50 coin?

Travis -

I don't think the combinatorics are correct. You need to exclude the permutations which would result in equal heads/tails at a lower value of n.

For n = 2, HTTH would not be valid because the game would have stopped at HT

Unless I misunderstood the problem...

Curses! you're right .. arg.

[QUOTE]
[B]Keep score as "net heads", so every head scores +1 and every tail scores -1. Suppose the first toss is a head. What is the probability that your score will ever get down one level from here? Well, you might get down one level immediately by throwing a tail (probability 1-p). But if you throw a head, ...
[/B][/QUOTE]

then you need to "get down one level" twice - once to return to +1 and then again to get to zero. ...

Let me suggest a slightly different way to count.

If the # Heads equal # Tails, the the total number of tosses is always even.

So lets count pairs of tosses.

If we count each head as +1/2 and each tail as -1/2, the outcome of a pair of tosses is either +1 (with probability p^2), 0 (with probability 2*p*(1-p)), or -1 (with probability (1-p)^2)

Now look at the cumulative count after N pairs of tosses and call it V(N).

Also define P(V) to be the probability of termination at V=0, from some initial point V.

Clearly, V(N) = 0 and we are looking for P(0).

More hints later ...

Im glad finally some people found my problem interesting :grin:

Here is a little hint


Try to look at the problem after 2, 4, 6, 8.. tosses. Can you see any interesting relations between

((2n)!)/((n!)^2) (n = number of pair of tosses)

and amount of combinations that lead to a termination of the game that do NOT include a shorter string of combinations that would end the game.

Analyze both of these combinations for each step and try to find a relation.

PS. It can be good to write down the combinations for each step (HH, HT, TH, TT), (HHHH, HHHT...). to get a good visualization of the problem. DS

okay, I've done that, maybe too hastily .. now I get the sum

Sum{n=1:infinity} p[sup]n[/sup](1-p)[sup]n[/sup](2n)!/(n![sup]2[/sup](2n-1))