Coin Flip Paradox: Is it Finite or Infinite?

[pig]

The thread about Zeno reminded me of a paradox that I was never able to understand.

Let's say you play a game, where you repeatedly flip a coin, and the first time the coin lands tails, you stop flipping. Then you get 2^n coins, where n is the number of heads flips. How much money is the game worth?

The probability of n being 0 is 1/2 (first flip tails).
The probability of n being 1 is 1/2*1/2 (first flip heads, second flip tails).
The probability of n being 2 is 1/2*1/2*1/2 (first and second flip heads, third tails).

And so on.

So, the expected payoff is:

(1/2)^1 * 2^0 + (1/2)^2 * 2^1 + (1/2)^3 * 2^2 + ...

= 1/2 + 1/2 + 1/2 + ...

The expected payoff is infinite, and therefore I should offer any finite amount of money to play this game. Can anyone explain?

Either intuition and a finite number of experiments don't work well with an infinite number of possibilities, or math doesn't.

 

[moshek]

This is a nice paradox about expectation.

:tongue:

Thank you
Moshek

 

[Hurkyl]

A common "trap" when dealing with expected payoffs is that gambling games don't work as "I pay up front and get my expected payoff back". Try working out the expected number of times you have to play before you win a million coins!


Another common trap is leaving out some qualifications:

You probably don't have time to sit around and wait for a trillion flips of a coin to get your money, so there's an upper limit on the number of coin flips.

The person paying you probably doesn't have a trillion coins, so there's an upper limit on the payoff you will receive.

In either case, there is a cutoff in your infinite sum, thus reducing the expected payoff to something finite.

 

[pig]

Thank you for the replies. Hurkyl, I ran into a similar answer before, but it doesn't completely satisfy me. The reason is this.

Consider a similar problem - the rules are the same, except the payoff would be n coins, where n is the number of times you flipped the coin. The expected payoff would be:

1/2 + 2/4 + 3/8 + 4/16 + 5/32 + ...

This is the sum of the infinite series n/(2^n).

((n+1)/2^(n+1))/(n/2^n) = (n+1)/2n

For all n except 1, this is < 1, so the series converges and the sum is not infinite. I believe the sum is 2, so the expected payoff is 2. No problem here.

So here we don't need to introduce the maximum number of flips, and the maximum payoff is still not finite - but unlike the first problem, it "works".

 

[Hurkyl]

Unlike the other problem, when you truncate this sum, the expected value changes very little. (And thus, it is convenient to use the infinite case to approximate the finite case)

And yes, the sum is 2. (try differentiating $\sum_n (x/2)^n$ then plug in 1 for x)

I guess I'm not entirely sure what's bothering you about this.

 

[matt grime]

And just think. If you had an infinite amount of money, you could win another infinite amount of money off your (least) favourite casino.

 

[uart]

With this "paradox" it is instructive to consider the finite case where your maximum win is upper bounded at M = 2^k.

In this case you find that the expected Win is equal 1 + k/2 and so you can apply a sensible cost to play of : $$1 + 0.5 \log_2(M)$$, where M is the house maximum payout.

 

[moshek]

uart:

log( infinity)=infinity
and what is the different between
paradox to "paradox" ?

 

[uart]

uart:
log( infinity)=infinity

Yes I realize that, but any game you can play will be of finite length and with finite maximum payout. It is also useful to look at the manner in which the expected return increases.

and what is the different between
paradox to "paradox" ?

I used quote to indicate that I don't really see this problem as all that parodoxical. There are are plenty of cases where the Expected Value of a bonafide random process is not finite.

 

[moshek]

Uart:

I will be really sad if a contradiction will be found in mathematics since that will destroy the all what was created until today but I am a search of paradox since I believe that jumping to new dimension :tongue: of understanding can come from there.

Thank you for your nice explanation to this paradox or "paradox" you choose.

That shows me that it has not the power to make the shift in mathematics
So we have to search a more powerful """""paradox""""".

Best
Moshek

 

[uart]

Just out of interest I programmed my computer to do a quick simulation of this game. I took the coin to be unity (eg one dollar) and simulated a measly 10 unit per game cost ($10.00) and played until I had a net win of 100 units ($100.00) or more. This seems pretty meager considering the unlimited theoretical potential of this game, but the results may surprise you.

Averaged over 10,000 runs the number of $10.00 games played just to get $100.00 or more ahead was almost 100,000 games. (per run that is!).

The average debt that was recorded before the "big win" eventually turned the tables was around $100,000.00 but the worst case debt over all runs was almost $5,000,000.00 (and all this for a lowly $10.00 game!).

Interestingly the average Win was around $400,000.00 despite the fact that each game was programmed to terminate when only $100.00 or more ahead. This reflects the nature of the game that you spend a long time loosing and going into considerable debt before eventually making one stunningly lucky series of throws which reverses your enormous lose into an enormous win.

 

[moshek]

Nice that you did it
Can you make 20,000 runs
and tell us the rezults.

Thank you
Moshek

 

[uart]

I get much the same (average) results at 20,000 runs moshek. Note that the poor ol' computer is simulating about 2,000,0000,0000 games to do this test! (20,000 runs times 100,000 average game length). It only takes about 60 seconds to do it though. :)

BTW. I'm not totally sure the psuedo random number generator is really good enough for such large runs. I don't know what it's repeat period is and whether it's good enough to model the very rare events. Anyway I'm pretty sure the results still give a good indication of how such a game is likely to play out.

 

[moshek]

Thank you Uart for the computer simulation
and your nice explantion to this "Paradox".

Best
Moshek

 

[robert Ihnot]

St. Petersburg Paradox not really real

A common "trap" when dealing with expected payoffs is that gambling games don't work as "I pay up front and get my expected payoff back". Try working out the expected number of times you have to play before you win a million coins!


Another common trap is leaving out some qualifications:

You probably don't have time to sit around and wait for a trillion flips of a coin to get your money, so there's an upper limit on the number of coin flips.

The person paying you probably doesn't have a trillion coins, so there's an upper limit on the payoff you will receive.

In either case, there is a cutoff in your infinite sum, thus reducing the expected payoff to something finite.

No casino will allow you to play for infinite sums, since they don't have the money. Now in what I read before, I think it was Weaver, in Lady Luck who said that Monte Carlo had a run of 28 heads once in about 70 years. (This does not mean that anyone continually doubled up.) But, obviously this is darn near impossible.

So let us say that we will pick 2^40 as the maximum payoff possible, which
is around 1.1 trillion dollars of money the casino does not have. Well even with this totally fantastic and impossible limit the amount to pay would be only $20 for a fair game. As far as this $20 goes, the casino could go on for years and years, declaring bankruptcy if necessary... Let's suppose in 70 years it played 2^28 games or 268,434,456 games and the worst that could happen would be for 28 successful passes. Then since it collected $20 a game and the cost averaged out to $14, the casino could expect to make $6 a game and this is a profit of over 1.6 billion dollars!

Thus, I feel, that the use of infinity in this problem is misleading. There is no such thing as infinity in this as a practical problem.

 

[moshek]

Pig:

Read the 6 problem of Hilbert ( paris 1900)
so you find one key to solve your language paradox.

Best
Moshek :uhh:

 

[ExecNight]

Hmm lots of n's..lots of infinities but Not enough relevance :zzz:


First of all..Lets say you have 10 coins..And gambled 10 times,you might win all games or you might lose all 10 or something between..

Tho if we say you have 100000000000 coins and played 100000000000 times you will end up with 50000000000 coins in the end..A few coins more or less for more info study Statistics..

So with infinite playing you will lose exactly half of your coins..If both sides were inserting coins you will end up exactly with the coins you began..

 

[xt]

errr... The St Petersburgs problem, curse the Bernoullis.

 

[s0l0m0nsh0rt]

not quite 50/50

Did you know that getting H or T on a coin flip is not actually 50/50? Its more like 51/49 in favor of the side facing up when u flip it. So, next time yer playin games for money, remember that!