Jump to content
BrainDen.com - Brain Teasers
  • 0

Infinite Flips


BMAD
 Share

Question

23 answers to this question

Recommended Posts

  • 0

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 pmin = 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.

2pmin (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 2pmin, H=T will eventually be reached.

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

Link to comment
Share on other sites

  • 0

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 f2.
After 6 flips it's f3.
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 by bonanova
Replacing first guess with solution
Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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?

Link to comment
Share on other sites

  • 0

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 n

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 2pmin.

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?
Link to comment
Share on other sites

  • 0

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 pmin = 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.

2pmin (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 2pmin, H=T will eventually be reached.

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

Woah.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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 ni = # paths to H=T=i that did not previously touch the diagonal.

We want to determine whether: 2pmin = Sum(inf) ni fi where f = pmin (1-pmin)

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

Let Sk = Sum(i=1,k) ni

Then ni= iC2i - Si-1 // here iC2i is the count of ALL paths to the i th diagonal square.

That's complicated, but should work.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...