Here's an interesting puzzle.

A game is played by repeatedly tossing a coin until it lands heads.  If it 
lands heads on the first try, you win $1 and the game is over.  If it lands 
heads on the 2nd try, you win $2 and the game is over.  On the 3rd try $4, 
and in general if you get the head on the nth try, you win $2^(n-1).

I simulated this game in C++ and after 1e6 goes the average win-per-go 
settles down quite nicely to $8.09 and stays there up to 1e8 goes.  Is that 
correct?  How much should you be willing to pay for each go?  Does it depend 
on how many goes you are going to have?

Post a reply to this message

scott wrote:
> Here's an interesting puzzle.
> 
> A game is played by repeatedly tossing a coin until it lands heads.  If 
> it lands heads on the first try, you win $1 and the game is over.  If it 
> lands heads on the 2nd try, you win $2 and the game is over.  On the 3rd 
> try $4, and in general if you get the head on the nth try, you win 
> $2^(n-1).
> 
> I simulated this game in C++ and after 1e6 goes the average win-per-go 
> settles down quite nicely to $8.09 and stays there up to 1e8 goes.  Is 
> that correct?  How much should you be willing to pay for each go?  Does 
> it depend on how many goes you are going to have?

By "average" you mean "arithmetic mean"?

The probability of N tosses is 2^(-N). So the probability of winning 
2^(N-1) dollas is 2^(-N).

[This simple analysis ignores the fact that if, say, you tossed a coin 
100 times without getting any heads at all, almost any *real* human 
would question whether the coin is loaded...]

Just as the probability of individual scores have a probability 
distribution, so the average scores should have one. And, by the central 
limit theorum, I would suggest that these converge on being normally 
distributed for larger and larger numbers of turns.

But what would the mean and standard deviation be? I have no idea.

Post a reply to this message

> By "average" you mean "arithmetic mean"?

Yup, total amount won over all games divided by the number of games played.

Post a reply to this message

Hmm. Tricky.

The number of heads given N tosses of the coin follows a Poisson 
distribution, and the number of tails before hitting a head follows a 
geometric distribution, but what the **** is the average score? A curios 
puzzle indeed...

Post a reply to this message

scott wrote:
> Here's an interesting puzzle.
> 
> A game is played by repeatedly tossing a coin until it lands heads.  If 
> it lands heads on the first try, you win $1 and the game is over.  If it 
> lands heads on the 2nd try, you win $2 and the game is over.  On the 3rd 
> try $4, and in general if you get the head on the nth try, you win 
> $2^(n-1).
> 
> I simulated this game in C++ and after 1e6 goes the average win-per-go 
> settles down quite nicely to $8.09 and stays there up to 1e8 goes.  Is 
> that correct?  How much should you be willing to pay for each go?  Does 
> it depend on how many goes you are going to have?
> 
> 

what kind of coin?
what kind of surface does it land on?
any pay out for it landing on its edge?

Post a reply to this message

> what kind of coin?
> what kind of surface does it land on?
> any pay out for it landing on its edge?

Just assume there is a 50% chance of heads or tails.

Post a reply to this message

> Hmm. Tricky.
>
> The number of heads given N tosses of the coin follows a Poisson 
> distribution, and the number of tails before hitting a head follows a 
> geometric distribution, but what the **** is the average score? A curios 
> puzzle indeed...

How about if you assume initially the game is limited to a certain number of 
tosses, and if a head fails to show up within that limit you win nothing...

Post a reply to this message

scott wrote:
> Here's an interesting puzzle.
> 
> A game is played by repeatedly tossing a coin until it lands heads.  If
> it lands heads on the first try, you win $1 and the game is over.  If it
> lands heads on the 2nd try, you win $2 and the game is over.  On the 3rd
> try $4, and in general if you get the head on the nth try, you win
> $2^(n-1).
> 
> I simulated this game in C++ and after 1e6 goes the average win-per-go
> settles down quite nicely to $8.09 and stays there up to 1e8 goes.  Is
> that correct?  How much should you be willing to pay for each go?  Does
> it depend on how many goes you are going to have?
> 
> 

The probability to win at n:th round is (1/2)^n. If you win, you get
2^(n-1). So, the theoretical predicted win-per-go is
(1/2)^1*2^(0)+(1/2)^2*2^1+(1/2)^3*2^2.... witch is the same as 1/2 + 1/2
+ 1/2 + 1/2... => infinite.
So, if you are able to have an unlimited number of goes and the other
part of the game is able to pay you what ever it has to, it doesn't
matter how much you pay for the each round: you will eventually make profit.

At least that's how our maths book explained it to me like two months ago :)

-- Arttu Voutilainen

Post a reply to this message

scott <sco### [at] scottcom> wrote:
> A game is played by repeatedly tossing a coin until it lands heads.  If it 
> lands heads on the first try, you win $1 and the game is over.  If it lands 
> heads on the 2nd try, you win $2 and the game is over.  On the 3rd try $4, 
> and in general if you get the head on the nth try, you win $2^(n-1).

> I simulated this game in C++ and after 1e6 goes the average win-per-go 
> settles down quite nicely to $8.09 and stays there up to 1e8 goes.

  How did you implement it? What type of integers did you use to count the
amount of money? (Note that a 32-bit integer will overflow after only 32
tosses of the coin, which is perfectly within the realm of possibility.)

-- 
                                                          - Warp

Post a reply to this message

"scott" <sco### [at] scottcom> wrote in message news:4965e43e@news.povray.org...

> Here's an interesting puzzle.
>
> A game is played by repeatedly tossing a coin until it lands heads.  If it
> lands heads on the first try, you win $1 and the game is over.  If it
lands
> heads on the 2nd try, you win $2 and the game is over.  On the 3rd try $4,
> and in general if you get the head on the nth try, you win $2^(n-1).
>
> I simulated this game in C++ and after 1e6 goes the average win-per-go
> settles down quite nicely to $8.09 and stays there up to 1e8 goes.  Is
that
> correct?

No. More properly, it's useless. You won't be able to solve this empirically
as such. Most influential outcomes on payoff are least likely, which you
will not ever come across in finite time.

> How much should you be willing to pay for each go?

Infinite. Sum(n,0,inf)( (1/2)^n * 2^(n-1) ) = sum(n,0,inf)(1/2) = inf.

Of course it only makes sense to play if both you and the casino have
infinite time and infinite money.

> Does it depend on how many goes you are going to have?

No, each round of game is independent, is it not?

Post a reply to this message

>> I simulated this game in C++ and after 1e6 goes the average win-per-go 
>> settles down quite nicely to $8.09 and stays there up to 1e8 goes.
> 
>  How did you implement it? What type of integers did you use to count the
> amount of money? (Note that a 32-bit integer will overflow after only 32
> tosses of the coin, which is perfectly within the realm of possibility.)

I used 32bit and then 64bit integers, but the result was the same.

Post a reply to this message

>> How much should you be willing to pay for each go?
>
> Infinite. Sum(n,0,inf)( (1/2)^n * 2^(n-1) ) = sum(n,0,inf)(1/2) = inf.
>
> Of course it only makes sense to play if both you and the casino have
> infinite time and infinite money.

What if you don't have infinite time?

>> Does it depend on how many goes you are going to have?
>
> No, each round of game is independent, is it not?

Yes, but somehow you have to calculate the "realistic" amount that you will 
win in finite time, so you can decide how much you are willing to pay for 
this game.

If I offered you a go for $2 would you take it? How about $5, $10, $100 ? 
There is a stark contrast to these values and the theoretical infinite 
average expected winnings.

Post a reply to this message

scott <sco### [at] scottcom> wrote:
> >> I simulated this game in C++ and after 1e6 goes the average win-per-go 
> >> settles down quite nicely to $8.09 and stays there up to 1e8 goes.
> > 
> >  How did you implement it? What type of integers did you use to count the
> > amount of money? (Note that a 32-bit integer will overflow after only 32
> > tosses of the coin, which is perfectly within the realm of possibility.)

> I used 32bit and then 64bit integers, but the result was the same.

  Did you at least put an assert() to check that no more than 31 (or 63)
tosses were ever made?

-- 
                                                          - Warp

Post a reply to this message

"scott" <sco### [at] scottcom> wrote in message
news:49662979$1@news.povray.org...

> > Of course it only makes sense to play if both you and the casino have
> > infinite time and infinite money.

> What if you don't have infinite time?

Then we decide on a cutoff.

> >> Does it depend on how many goes you are going to have?

> > No, each round of game is independent, is it not?

> Yes, but somehow you have to calculate the "realistic" amount that you
will
> win in finite time, so you can decide how much you are willing to pay for
> this game.

Sure, if you tell me exactly what the finite time is.

> If I offered you a go for $2 would you take it?

It's an even game for 4 throws, favours me for higher. You must show me that
you have $8.

> How about $5,

It's an even game for 10 throws, favours me for higher. You must show me
that you have $512.

> $10,

It's an even game for 20 throws, favours me for higher. You must show me
that you have $524,288.

This is on par with typical lotteries. Odds of winning the biggest jackpot
is almost one in a million, with more probable smaller prizes.

> $100 ?


It's an even game for 200 throws, favours me for higher. You must show me
that you have over $8e59.

Even then, I don't think I'd play, as I don't know where I'd put that money
if I win.

> There is a stark contrast to these values and the theoretical infinite
> average expected winnings.

The progression on maximum winnings possible might be a clue why.

Post a reply to this message

scott wrote:
> Here's an interesting puzzle.
> 
> A game is played by repeatedly tossing a coin until it lands heads.  If 
> it lands heads on the first try, you win $1 and the game is over.  If it 
> lands heads on the 2nd try, you win $2 and the game is over.  On the 3rd 
> try $4, and in general if you get the head on the nth try, you win 
> $2^(n-1).
> 
> I simulated this game in C++ and after 1e6 goes the average win-per-go 
> settles down quite nicely to $8.09 and stays there up to 1e8 goes.  Is 
> that correct?  How much should you be willing to pay for each go?  Does 
> it depend on how many goes you are going to have?

The expected payoff is infinite of course.  Personally, I'd pay about 
$10 to play the game, which indicates that I'm not attempting to 
maximize my expected payoff in making this decision.  The best I can 
formalize my reasoning is that the `utility' to me of winning a sum of 
money levels off asymptotically as that sum of money decreases.  For 
example, as far as I'm concerned there's no difference between winning 
$10^20 and $10^30, despite the fact that the latter is a vastly larger sum.

Furthermore, since I have only a very limited amount of money, losing $x 
has a higher negative utility than gaining $x -- as indicated by the 
fact that I wouldn't play a game with zero expected payoff (unless the 
game itself was fun of course).

To properly estimate how much I should pay to play under this view I 
should make a guess at my payoff vs. utility curve and then calculate an 
expected utility, but that's a bit more effort than I's probably care to 
spend were I presented with such a situation, so I'll take the 
satisficing approach and just say $10.

Also, I assume that you're familiar with the name of this puzzle, but on 
the off chance that you're not: 
http://en.wikipedia.org/wiki/St._Petersburg_paradox

Post a reply to this message

I tried it myself with the program at the end of this post, and got a
bit different of a result. The program printed:

times tested: 100000000, sum: 1600092924, average: 16.0009
times tested: 200000000, sum: 2952473665, average: 14.7624
times tested: 300000000, sum: 4316535702, average: 14.3885
times tested: 400000000, sum: 6018669380, average: 15.0467
times tested: 500000000, sum: 7585216727, average: 15.1704
times tested: 600000000, sum: 8915924298, average: 14.8599
times tested: 700000000, sum: 10662688388, average: 15.2324
times tested: 800000000, sum: 12027713479, average: 15.0346
times tested: 900000000, sum: 13468996092, average: 14.9656
times tested: 1000000000, sum: 15300481793, average: 15.3005

  The program:

#include "IsaacRand.hh"
#include <iostream>
#include <cassert>

int main()
{
    typedef unsigned long long ULL;

    IsaacRand rng(0);

    ULL sum = 0;
    std::cout << "sizeof(sum) = " << sizeof(sum) << std::endl;

    ULL counter;
    for(counter = 0; counter < 1000000000ULL; ++counter)
    {
        ULL rounds = 0;
        while(rng.getNext() % 2 == 0)
        {
            ++rounds;
            assert(rounds < 64);
        }
        if(rounds) sum += 1ULL << rounds;
        else ++sum;

        if(counter % 100000000 == 100000000-1)
            std::cout << "times tested: " << counter+1
                      << ", sum: " << sum << ", average: "
                      << double(sum)/double(counter) << std::endl;
    }
}

Post a reply to this message

somebody wrote:
> Even then, I don't think I'd play, as I don't know where I'd put that money
> if I win.

I can help with that!

-- 
   Darren New, San Diego CA, USA (PST)
   Why is there a chainsaw in DOOM?
   There aren't any trees on Mars.

Post a reply to this message

"Darren New" <dne### [at] sanrrcom> wrote in message
news:49663ef0$1@news.povray.org...
> somebody wrote:

> > Even then, I don't think I'd play, as I don't know where I'd put that
money
> > if I win.
>
> I can help with that!

Thanks, but I need help from a couple more people to stash away equivalent
of 40,000 universes' weight of money in 100 dollar bills.

Post a reply to this message

Btw, this might be of interest:

http://en.wikipedia.org/wiki/St._Petersburg_paradox

-- 
                                                          - Warp

Post a reply to this message

>> >  How did you implement it? What type of integers did you use to count 
>> > the
>> > amount of money? (Note that a 32-bit integer will overflow after only 
>> > 32
>> > tosses of the coin, which is perfectly within the realm of 
>> > possibility.)
>
>> I used 32bit and then 64bit integers, but the result was the same.
>
>  Did you at least put an assert() to check that no more than 31 (or 63)
> tosses were ever made?

It seems that the number of tosses never exceeds 16, even when running it 
1e9 times (where you would expect around 30 tosses is likely to come up).

OK I just fixed it now, I changed my head/tail generator from:

(rand()%2) == 0

to

rand() <= RAND_MAX/2

and now it seems to behave better, after 1e9 goes the maximum number of 
tosses in a row is 29, and the average winnings per go are around $14.30.

I guess that the RNG doesn't have more than 16 odd or even integers in a 
row, but it does has more than 16 either side of the mid-value.  Perhaps I 
need a better RNG to investigate further.

Post a reply to this message

>> $10,
>
> It's an even game for 20 throws, favours me for higher. You must show me
> that you have $524,288.

OOC why the 20 and why the $2^19 figues?  That's what I was really 
interested in.

Post a reply to this message

> Also, I assume that you're familiar with the name of this puzzle, but on 
> the off chance that you're not: 
> http://en.wikipedia.org/wiki/St._Petersburg_paradox

No I wasn't aware of the name (so as usual it is then very hard to find any 
info about it), thanks!

Post a reply to this message

scott <sco### [at] scottcom> wrote:
> (rand()%2) == 0

> to

> rand() <= RAND_MAX/2

  The rand() function in most compilers is of extremely poor quality and
should never be used for this type of application. You should always use
a very high-quality RNG with a humongous period.

  I used (my C++ version of) the ISAAC RNG, which should be of fairly high
quality.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   The rand() function in most compilers is of extremely poor quality and
> should never be used for this type of application. You should always use
> a very high-quality RNG with a humongous period.
> 
>   I used (my C++ version of) the ISAAC RNG, which should be of fairly high
> quality.

I understand the Mersenne Twister is designed specifically for these 
kinds of simulations - but I don't know how widely available it is...

PS. One time I wrote my own PRNG just to generate some random data for 
testing purposes. I don't know why I didn't use the PRNG library, but I 
should have; on investigation, it turns out that my own PRNG almost 
always has a period of 2. (!!) Oops...

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> I understand the Mersenne Twister is designed specifically for these 
> kinds of simulations - but I don't know how widely available it is...

  The ISAAC RNG is faster than MT. I don't know about quality, but it should
be very competitive at least.

> PS. One time I wrote my own PRNG just to generate some random data for 
> testing purposes. I don't know why I didn't use the PRNG library, but I 
> should have; on investigation, it turns out that my own PRNG almost 
> always has a period of 2. (!!) Oops...

  One of the basic things taught at school is that you should never attempt
to make your own PRNG if you don't have extensive experience about the
subject, if you want any kind of quality to it.

  Another thing with the exact same rule is a hashing function.

-- 
                                                          - Warp

Post a reply to this message

>> I understand the Mersenne Twister is designed specifically for these 
>> kinds of simulations - but I don't know how widely available it is...
> 
>   The ISAAC RNG is faster than MT. I don't know about quality, but it should
> be very competitive at least.

Well I seriously doubt it can possibly be any *worse* than an LCG. 
(Otherwise... why would they have designed it?)

>> PS. One time I wrote my own PRNG just to generate some random data for 
>> testing purposes. I don't know why I didn't use the PRNG library, but I 
>> should have; on investigation, it turns out that my own PRNG almost 
>> always has a period of 2. (!!) Oops...
> 
>   One of the basic things taught at school is that you should never attempt
> to make your own PRNG if you don't have extensive experience about the
> subject, if you want any kind of quality to it.
> 
>   Another thing with the exact same rule is a hashing function.

Or, indeed, several other kinds of construct. (E.g., it's notoriously 
hard to make a good encryption algorithm.)

In my defense, in the incident in question "good quality" random numbers 
weren't necessary. I just needed lots of different numbers with no 
particular pattern to them. OTOH, what I got was something like

   3, 11, 3, 11, 3, 11, 3, 11...

which is obviously no use at all. The PRNG generates longer sequences in 
a few cases, but most of the time it does not. And I somehow failed to 
notice this.

In future, I'm going to use the PRNG library. No matter how stupid its 
API is!

Post a reply to this message

>  I tried it myself with the program at the end of this post, and got a
> bit different of a result. The program printed:

I just found out that Windows includes a better RNG anyway, you call it with 
the API function CryptGenRandom.  More details here:

http://en.wikipedia.org/wiki/CryptGenRandom

It's a fair bit slower than rand(), but by making use of every bit returned 
(rather than just testing the LSB) it is comparable.

Post a reply to this message

Warp wrote:
>   One of the basic things taught at school is that you should never attempt
> to make your own PRNG if you don't have extensive experience about the
> subject, if you want any kind of quality to it.

This method seems to work pretty well: http://xkcd.com/221/

Post a reply to this message

Warp wrote:
>   One of the basic things taught at school is that you should never attempt
> to make your own PRNG if you don't have extensive experience about the
> subject, if you want any kind of quality to it.

And even if you do. Knuth tells stories of his own attempts while writing 
his semi-numeric methods tome, having thought he came up with a great RNG 
and found it generated a couple hundred numbers before settling into a short 
cycle of something like 3 or 4 values.



-- 
   Darren New, San Diego CA, USA (PST)
   Why is there a chainsaw in DOOM?
   There aren't any trees on Mars.

Post a reply to this message