Infinite Flips

[BMAD]

Given a coin with probability p of landing on heads after a flip, what is the probability that the number of heads will ever equal the number of tails assuming an infinite number of flips?

[bonanova]

The results of a biased coin can be separated into fair-coin flips and two-headed coin flips.

Suppose p(H) = 0.6, so that p_min = 0.4.

Representative flips are T T T T H H H H H H.

Partition them as: T T T T H H H H || H H.

2p_min (80%) of the flips are "fair" flips (equal chance of T and H.) The others are "two-headed" flips.

The fair flips reach H=T with p=1; the others reach H=T with p=0.

Thus, with probability 2p_min, H=T will eventually be reached.

Putting it differently: a biased coin acts with probability 2p_min like a fair coin.

[bonanova]

I wonder whether (and at first glance I think) the answer is the same as the probability that a fraction p of fair-coin flips will be heads.
I'm going to think in those terms first.

Edit:
After thinking for two minutes, it can't be the same answer.
The OP describes a process that has a solution for irrational values of p; my description does not.
That is, the heads-fraction of any number of flips by definition is rational.

Second Edit:
Ignoring the fact that 0 = 0,
After 2 flips it's f = p(1-p).
After 4 flips it's f².
After 6 flips it's f³.
Their sum is a convergent (f<1) geometric series with maximum value of 1/3 when p=1/2, (f=1/4) and 1/(1-f) -1 in general.

Edited December 7, 2013 by bonanova
Replacing first guess with solution

[plainglazed]

...because very big numbers and especially infinity confuse me - oh well. Gonna say if 0<p<1 then the probability that the number of heads equals the number of tails somewhere along the way to infinity trials is 1. But seems the expectation that this would occur is zero so... my head hurts.

[bonanova]

On further thought, I think my answer gives only a lower bound.

[bonanova]

When the probability of the less likely outcome (heads or tails) is p,

then a sufficiently long series of flips will encounter a H=T state with probability of 2p.

What a sweet result!

And it says that a fair coin will encounter H=T with probability 1,

which I think is a well-known result.

[plainglazed]

so if the coin is biased by as little as having a probability of say .49 for flipping heads, there will not always be a point, when flipping it an infinite amount of times, that the number of heads equals the number of tails?

[bonanova]

so if the coin is biased by as little as having a probability of say .49 for flipping heads, there will not always be a point, when flipping it an infinite amount of times, that the number of heads equals the number of tails?

If 100,000 people flipped such a coin forever, only 98,000 of them would eventually get H=T.

But that's a high percentage.

I simulated 100,000 cases for p(H) = 0-.5 in steps of .05.

The result H=T happened for large numbers of flips only when p(H) was about .4 or higher.

When it was .2 or lower, equality happened in the first 10 flips or so, or it never happened.

So it's possible to deviate from equality early on and never get back.

Only for the perfect fair coin will equality have unit probability.

There must be an equation for it somewhere.

[BMAD]

plainglazed, as long as the probability of being heads isn't 100%. Which means even if the probability of getting heads is 99.9% there is still an occurrence where someone will get H=T

Edited December 7, 2013 by BMAD

[plainglazed]

@ bonanova - but infinity flips is a fair many more than "a large number of flips"

@ BMAD - someone but not everyone?

hopefully my responses here are taken as meant to be - lack of full comprehension of very large numbers - and not as deviating from the spirit of the riddle.

[BMAD]

It depends on how you splice the question. essentially we could have one person play 1,000,000 and they will have a low but existing probability of being even. We could also have 500,000 people play twice and have again a low but existing probability of being even.

[bonanova]

Once bias exists, infinity won't guarantee a return to equality.

The probability of equality decreases with bias, but it's never zero unless one of the outcomes never occurs at all.

Note that saying p(H=T) < 1 doesn't prohibit H=T, it only says H=T is not a certain eventual outcome.

[Rainman]

Just a side note: it is often falsely assumed that 100% probability is equivalent with absolute certainty. This is one of those cases; even if the coin is perfectly fair, it's possible that you will never reach H=T even if you keep flipping forever. The probability is 0, but it's possible. Any given infinite sequence is possible, for example flipping heads every time.

If we look at it backwards, suppose you did flip the coin infinitely many times and recorded your results. Whatever sequence you got, the probability of that particular sequence was 0, but it did happen.

Suppose you generate a random real number between 0 and 10. The probability of generating pi is 0, but it is within the realm of possibilities. It's totally impossible to generate -pi.

In general, suppose we have an event A. If A is absolutely certain to happen, then P(A)=1. But the converse is not true. If P(A)=1, we can't conclude that A is absolutely certain to happen. There is a definition in probability theory, that if P(A)=1, then A happens almost surely.

[plainglazed]

well, i almost surely better understand now. it's actually a little easier for my wee brain to comprehend. the learning experience here is always worth a little humility imho. thanks you guys. oh, one last (not serious) question - what if infinity is odd?

[bonanova]

well, i almost surely better understand now. it's actually a little easier for my wee brain to comprehend. the learning experience here is always worth a little humility imho. thanks you guys. oh, one last (not serious) question - what if infinity is odd?

Nice segue to a cute poem from the late Martin Gardner:

Pi goes on and on and on ...

And e is just as cursed.

I wonder: Which is larger

When their digits are reversed?

[bonanova]

Treat the path of flips as a checkerboard beginning in the lower left corner.

Flipping a H moves up one space; T moves a space to the right. The diagonal squares represent H=T.

Moving from one diagonal square to the next is TH or HT with probability f = p(H)(1-p(H)).

Thus any path to the nth diagonal square happens with probability f ⁿ

Total probability of H=T=n is then just a matter of counting paths.

To answer the question we need a subset of p(H=T=n), using only the paths for which n is the first diagonal square reached.

A closed-form expression for these paths would permit summing a convergent infinite series in f.

Not having the closed form, I constructed a modified Pascal Triangle to count paths in the upper left part of the checkerboard to each diagonal point, excluding paths that had previously visited the diagonal:

 

1 9 ....1 8 35 110 275 572 1001 1430 1430 14301 7 27  75 165 297  429  429  4291 6 20  48  90 132  132  1321 5 14  24  42  42   421 4  9  14  14  141 3  5   5   51 2  2   21 1  11 11

Notice the last three numbers in each row are the same, because if we begin with H, the last two flips that get us to H=T without a previous H=T must be TT. Similar paths exist beginning with T, so the numbers on the diagonal must be doubled.

The first 17 values are

2 2 4 10 28 84 264 858 2860 9724 33592 117572 416024 1485800 5348880 19389690 70715340.

These are the coefficients of a power series in f.

The partial sums are the probability of (first) reaching any of the first n diagonal squares - i.e. of (first) achieving H=T for 1<=H<=n.

The infinite series should sum to 2p_min.

For values of .001 < p(H) < .25 the 17-term series gives 2p(H) to within 4 places.

This happens because f is small, and convergence is rapid.

For .25 < p(H), the increased likelihood of the first H=T condition occurring for H>17 is seen.

The deficiency is precisely the probability that H=T will be first reached for H>17.

 

p(H) Series (17 terms).05 .1000.10 .2000.15 .3000.20 .4000.25 .4999.30 .5992.35 .6953.40 .7806.45 .8417.50 .8642

From the array, is it possible to discern (a la Pascal and the binomial coefficients) an expression for the path count in closed form?

[gavinksong]

The results of a biased coin can be separated into fair-coin flips and two-headed coin flips.

Suppose p(H) = 0.6, so that p_min = 0.4.

Representative flips are T T T T H H H H H H.

Partition them as: T T T T H H H H || H H.

2p_min (80%) of the flips are "fair" flips (equal chance of T and H.) The others are "two-headed" flips.

The fair flips reach H=T with p=1; the others reach H=T with p=0.

Thus, with probability 2p_min, H=T will eventually be reached.

Putting it differently: a biased coin acts with probability 2p_min like a fair coin.

Woah.

[plasmid]

How do you partition the flips of a coin with p(tails)=0.4 and p(heads)=0.6 in the scenario where it comes up with ten consecutive tails?

[bonanova]

How do you partition the flips of a coin with p(tails)=0.4 and p(heads)=0.6 in the scenario where it comes up with ten consecutive tails?

T T T T H H H H - H H is a result that is representative of p(H) = 0.6.

That does not mean that in every ten flips it will happen.

There can be (arbitrarily long) strings of T, so long as p(T) is not zero.

So T T T T T T T T T T can happen.

But p(H) = 0.6 says that, on average, whenever there are 10-T strings there will also be 10-H strings, and they will occur in the following proportions:

T T T T T T T T T T

T T T T T T T T T T

T T T T T T T T T T

T T T T T T T T T T

H H H H H H H H H H

H H H H H H H H H H

H H H H H H H H H H

H H H H H H H H H H

-------------------

H H H H H H H H H H

H H H H H H H H H H

and the hyphens indicate how to partition them.

[Rainman]

If P(H)=0.6, the probability of a 10-H string is 0.6¹⁰ ~ 0.006, whereas the probability of a 10-T string is 0.4¹⁰ ~ 0.0001. So 10-H strings should be much more frequent than 10-T strings.

[bonanova]

Agree. Better simply to say simply that in any large ensemble of N outcomes, where 60% will be H, the outcomes can be partitioned into groups that are totally fair (H=T) and totally biased (all H.). The fair partition will be N x 2 p(T) in size.

[The_King_Of_Games]

one doubt

what if we assume there are 2n flips with n->infinity. using binomial p(no. of heads = no. of tails) = 2nCn * p^n * (1-p)^n, with n->infinity. we know by intuition that for p=0.5, this is = 1. can we somehow proceed this way and solve the question?

[The_King_Of_Games]

one doubt

what if we assume there are 2n flips with n->infinity. using binomial p(no. of heads = no. of tails) = 2nCn * p^n * (1-p)^n, with n->infinity. we know by intuition that for p=0.5, this is = 1. can we somehow proceed this way and solve the question?

somebody plz help with this doubt

[bonanova]

one doubt

what if we assume there are 2n flips with n->infinity. using binomial p(no. of heads = no. of tails) = 2nCn * p^n * (1-p)^n, with n->infinity. we know by intuition that for p=0.5, this is = 1. can we somehow proceed this way and solve the question?

somebody plz help with this doubt

Envision the series of flips as a tour of a checkerboard, where H is a move up and T moves to the right.

Start at the lower left corner. If your path comes back to the diagonal, you have a H=T condition.

Counting paths, closed form.

Let n_i = # paths to H=T=i that did not previously touch the diagonal.

We want to determine whether: 2p_min = Sum(inf) n_i fⁱ where f = p_min (1-p_min)

To proceed, we need expressions for the n_i . Here they are.

Let S_k = Sum(i=1,k) n_i

Then n_i= _iC_2i - S_i-1 // here _iC_2i is the count of ALL paths to the i th diagonal square.

That's complicated, but should work.