Infinite Coin-Toss?

[Orgasmic Troll]

Okay .. is it |2p-1| + 1?

[tom11784]

it cant be since that gives a probability greater than 1

[dweick]

I've just looked at it for the case where the probability of heads and tails is equal (ie 1/2). I'm not a math dude so don't expect this to be rigorous.

Obviously you can only complete if you have an even number of tosses.

Toss the coin once, assign the value +1 to the side that shows (if heads comes up heads=+1 and tails=-1). Now toss the coin a second time.

The total will either be +2 or 0 with a probability of 1/2 that it is +2 and a probability of 1/2 that it is 0.

I use P(+x) to represent the probability that we will eventually get to a count of 0 starting with a count of +x.

So, after two tosses

(1) P = 1/2 + P(+2)

To solve for P(+2) we must toss the coin two more times and we will end up with +4 with a probability of (1/4), +2 with a probability of (1/2) and 0 with a probability of (1/4).

(2) P(+2) = (1/4)P(+4) + (1/2)P(+2) + (1/4)
(3) P(+2) = 1/2 + (1/2)P(+4)

Substitution back into the equation (1)

(4) P = 3/4 + (1/4)P(+4)

Toss the coin two more times and get +6 or +4 or +2 with probabilities 1/4, 1/2, 1/4.

(5) P(+4) = 1/4)P(+6) + (1/2)P(+4) + (1/4)P(+2)

Solve for P(+4) and we get

(6) P(+4) = (1/3) + (2/3)P(+6)

Substitute (6) back into (4) and you get

(7) P = 5/6 + (1/6)P(+6)

Now for a leap, I assert that:

(8) P(+n) = 1/((n/2) + 1) + (n/2)/((n/2) + 1)P(+(n+2))
and

(9) P = (n-1)/n + (1/n)P(+n)
for any even n

This obviously converges to 1 for the case of a normal coin toss where the probability of heads and tails is equal

[wblipp]

Other people are providing hints on a combinatorial approach. I'm describing a probabilistic approach using "skip-free" analysis.

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, then you need to "get down one level" twice - once to return to +1 and then again to get to zero. ...

So if "z" is the probability of ever getting down one level, z must satisfy the equation

z = (1-p) + pz^2.

[Orgasmic Troll]

Originally posted by tom11784
it cant be since that gives a probability greater than 1

That would be a typo .. forgot a negative sign

-|2p-1| + 1

[wblipp]

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, then you need to "get down one level" twice - once to return to +1 and then again to get to zero. So if "z" is the probability of ever getting down one level, z must satisfy the equation

z = (1-p) + pz^2.

This equation has roots z=1 and z=(1-p)/p. When p (the probability of going up) is less than 0.5, the probability of ever coming down again is 1. When p is greater than 0.5, the probability of ever coming down again is (1-p)/p. So the answer to the original question is ...

[apocalypse]

Let P : [0,1] -> [0,1] be a function such that P(p) is the probability that series of coin flips where the probability of heads is p ever achieves parity.

To summarize:

dweick has shown that P(0.5) = 1, and P(0) = P(1) = 0 is obvious from the statement of the problem.

We also know that P is symmetric about p = 0.5 because p and (1-p) are interchangeable.

We can equate a series of coin flips with a random walk on a line with unit steps, say, with H corresponding to +1 and T corresponding to -1.

Now:

Let us consider p in the interval (0.5,1).

We know that random walk with parameter p will eventually diverge to +inf because the expedted distance travelled, (2p - 1) > 0.

Hence, if our first flip is a tail the game will terminate with probability 1.

let F |N x (0.5,1) -> [0,1] be a function such that F(n,p) is the probability that given #H - #T = n and probability(H) = p, we will ever reach parity.

P(p) = (1 - p) + p*F(1,p)

wblipp asserts that F(1,p) = (1-p)/p which implies that P(p) = 2-2p in the interval (0.5,1) or 1 - |2p -1| on the interval [0,1] as asserted by TravisT.

However, using dweick's formulation where
F(1,p) = (1-p) + p*F(2,p)
F(2n,p) = (1-p)^2 *F(2n-2,p) + 2p(1-p)*F(2,p) + p^2*F(2n+2,p)

I built a system of equations in Mathematica and solved them to near convergence and P did not appear to be linear over the interval (0.5,1). For example, F(1, 3/4) seemed to converge strongly toward 3/11, implying P(3/4) = 5/11, and not 1/2 as expected by TravisT and wblipp.

I performed all of the calculations using extended precision quotients to mitigate rounding errors, and solved through F(120,p).

Did I set the problem up incorrectly, or does anyone have thoughts on the discrepancy?

[wblipp]

Originally posted by apocalypse

F(1,p) = (1-p) + p*F(2,p)
F(2n,p) = (1-p)^2 *F(2n-2,p) + 2p(1-p)*F(2,p) + p^2*F(2n+2,p)

I built a system of equations in Mathematica and solved them to near convergence and P did not appear to be linear over the interval (0.5,1).

When n=1, the right side contains F(0,p). How did you handle that?

One method you might have used is to include the equation for n=0. If you did that, the right hand side includes F(-2, p). How did you handle that?

[apocalypse]

When n > 0, F(0,p) = 1, because the game always terminates as soon as parity is achieved after the first coin toss (as I understand the initial problem).

I forgot to include that in my write-up because I can't currently access the computer on which I wrote the Mathematica program. Or rather, I fixed it in the write up of the equation for F(1,p), but not for the inductive case for F(2,p)

[apocalypse]

I was able to access the mathematica server again, and I found a small typo in my script . When I fixed it, it converged to the aforementioned piecewise linear function. Perhaps one day I will go back and figure out what problem I was actually solving...