9
$\begingroup$

An eccentric billionaire plays a game with you. She has an urn with 100 gold coins.

  • Each time, you can take any number of coins from the urn.
  • If you take n coins, she will flip a fair coin.
    • If head, she adds one more gold coin to the urn.
    • If tail, nothing happens.
  • She stops flipping at the nth tail. After her flipping stops, you can take the coins from the urn again. If the urn is empty after her flipping stops, the game ends.

What is the maximum and minimum expected number of coins you can extract from the game?

$\endgroup$
6
  • 1
    $\begingroup$ The rules are easy to misinterpret. So it seems that she's going to flip the coin until she gets n tails, and then her turn ends. Not the game ends. $\endgroup$
    – Tony Ennis
    May 21 at 16:55
  • 1
    $\begingroup$ I think all answers below that say "infinite" were based upon a different version of the rules. $\endgroup$
    – Tony Ennis
    May 21 at 17:37
  • $\begingroup$ As far as I can tell no one misinterpreted the rules - as you said, she flips until she gets $n$ tails and then her "turn" ends, after which you get to go again. How else would everyone arrive at an infinite expectation if they thought the game ended when she was done flipping? $\endgroup$
    – SQLnoob
    May 21 at 18:06
  • 1
    $\begingroup$ @SQLnoob Consider if n = 5. We pocket 5 coins. The only way she puts 5 back (making our profit infinite) in is if she flips 5 heads before she flips 5 tails, on average. That's what I'll check when I get home. $\endgroup$
    – Tony Ennis
    May 21 at 19:12
  • $\begingroup$ @TonyEnnis on average that's exactly what she'll do, given by the negative binomial distribution. $\endgroup$
    – SQLnoob
    May 21 at 19:28
14
$\begingroup$

I agree with the answer some others have given but I don't think their analysis is correct.

First of all,

the maximum and minimum expectation are the same. Taking n coins produces the same distribution of coins afterwards as taking one coin n times; the only way there could be a difference would be if you emptied the urn part-way through the sequence, but that can't happen.

So, let the expected number of coins you get, when the urn starts off with N coins in it, be f(N). We want f(100).

On each turn, the billionaire chooses a number m from a geometric distribution with parameter 1/2 (note: there are two different things "geometric distribution" can mean; we want the one that counts failures rather than trials) and the number of coins in the urn increases by m-1.

Note that

the expected number of coins after your turn is still N, but if the actual number ever hits zero the game ends, so it's possible for the expected number of coins you take to be finite (this is why I don't think the answers that say "when you play a turn, the expected number of coins doesn't change, so obviously your expectation is infinite" are being careful enough). Here's an example where perhaps the situation is clearer. We start with an urn containing 100 coins. At each turn, you take a coin from the urn; the billionaire flips a fair coin, and depending on the result either empties the urn or fills it up to double the number of coins it originally contained. Here it's still true that each turn leaves the number of coins in the urn unchanged in expectation, but the expected number of coins you get is very finite; in fact it's 2. Now, there is one important respect in which this isn't analogous to the situation here: I'm only letting you take one coin at a time. If you're allowed to take as many coins as are in the urn, then with probability 1/2 you get 100 coins, with probability 1/4 you get 200, with probability 1/8 you get 400, etc., and in fact your expected number is infinite. Similarly, if what happens is that at each turn you take just one coin and the billionaire (with equal probability) either does nothing or replaces it with two, then again your expected number of coins gained is infinite. So it's possible that there's some nice general theorem saying that provided you're allowed to take as many coins as are in the urn at each step, and provided the expected overall change in urn-count is zero, your expectation must be infinite. But the existing answers don't appeal to anything so carefully stated as this (still less prove it).

Starting with N coins in the urn,

the number of coins after your turn is $N-1+m$ with probability $2^{-m+1}$. So we have $f(0) = 0$ and $f(N) = 1 + f(N-1)/2 + f(N)/4 + f(N+1)/8 + f(N+2)/16 + \ldots$ when $N > 0$. Note that this means that if any f(N) is infinite then all are. Let's suppose they're finite, and seek either a solution or a contradiction.

Now

substituting N+1 for N in the recurrence and dividing by 2 we get $f(N+1)/2 = 1/2 + f(N)/4 + f(N+1)/8 + f(N+2)/16 + \cdots$ whose RHS has the same "tail" as that of the original recurrence. So, subtracting, $f(N) - f(N+1)/2 = 1/2 + f(N-1)/2$ when $N>0$.

And now

if we write $g(N)=f(N+1)-f(N)$ this becomes $g(N-1)-g(N)=1$ when $N>0$. This in turn means that $g(N)=a-N$ for some constant $a$, whence $f(N)=b+aN-N^2/2$ for constants $a,b$; and since $f(0)=0$ we must have $b=0$ so $f(N)=aN-N^2/2$. It's easy to verify that any such $f$ does in fact satisfy the recurrence relation.

Unfortunately

no such $f$ can actually be correct, because for large $N$ the values are negative! So we have a contradiction, and the only dubious assumption we made was that the values of $f$ are finite. So in fact they are not all finite; as mentioned above, this means that they are all infinite; in particular $f(100)$ is infinite, and your expected number of coins is infinite whatever values of $n$ you pick.

$\endgroup$
10
  • 1
    $\begingroup$ "has a very finite expectation, namely 2. This is why I don't think it's enough to say," Note that this argument is also not correct: If the bills triple or disappear, the expected end capital is still infinite, even if the expected number of turns is finite. $\endgroup$
    – Retudin
    May 20 at 15:30
  • 1
    $\begingroup$ @Retudin: What argument are you talking about? Isn't Gareth's answer just saying "I don't think it's obvious that OP's game has an infinite expected number of steps"? $\endgroup$
    – tehtmi
    May 20 at 16:31
  • 1
    $\begingroup$ @tehtmi The 'example used as argument'. It is incorrect in the sense that it is incomplete (since nothing is taken out at each step, and finite duration and finite expectation are different aspects of the puzzle). Not ideal if used as argument that other analysis is incomplete. $\endgroup$
    – Retudin
    May 20 at 17:30
  • 1
    $\begingroup$ It's trivial to modify it to have something closer to the form of the game here. I'll make that modification since the difference seems to be distracting. $\endgroup$
    – Gareth McCaughan
    May 20 at 17:48
  • 2
    $\begingroup$ Right, perhaps a more interesting framing of the question would be something like, "What is the probability that you win at least 1,000,000 coins?" in which case the answer would be only like 5%. You will most likely end up with less - but mathematically because your profit will sometimes effectively grow forever your expectation is infinite. $\endgroup$
    – SQLnoob
    May 21 at 12:44
4
$\begingroup$

The maximum expected number of coins you can get is

infinite

How can you get that much money?

Take all the coins from the urn. The billionaire will toss the coin until the 100th tails. This will happen (on average) after 200 throws: on average 100 heads and 100 tails. Thus the billionaire will put (on average) 100 new coins in the urn. You can now take again 100 coins -- or whatever number of coins are in the urn -- and the game never ends.

$\endgroup$
5
  • 4
    $\begingroup$ The billionaire stops her tossing at the nth tail, not at the nth toss. $\endgroup$
    – Eric
    May 20 at 10:56
  • $\begingroup$ @Eric either case, if you take 100 coins there will be 50 replacements on average. Or am I missing something? $\endgroup$
    – melfnt
    May 20 at 11:00
  • $\begingroup$ @Eric ok, that's what I was missing: the billionaire can toss the coin more than 100 times, can't she? $\endgroup$
    – melfnt
    May 20 at 11:02
  • 1
    $\begingroup$ Yes, she can. There's no limit. $\endgroup$
    – Eric
    May 20 at 11:08
  • $\begingroup$ @Eric thank you for pointing that out, I misunderstood the question. I corrected my answer accordingly, but I'm not sure about the correctness anymore $\endgroup$
    – melfnt
    May 20 at 11:14
4
$\begingroup$

Attempt at a bit more rigor in an answer.

Consider first the strategy of taking 1 coin each turn:

What is the expected number of turns until the jar ends up with one fewer coin (after refilling)? Let this number be denoted $E_1$ and let $E_n$ be the expected number of turns before the jar ends of with $n$ fewer coins. Then $E_n = n E_1$ and $E_1 = 1 + \frac{1}{2}\cdot0 + \frac{1}{4}\cdot E_1 + \frac{1}{8}\cdot E_2 + \dots = 1 + \frac{E_1}{2} \sum_{k=1}^\infty{\frac{k}{2^k}}=1 + E_1$. This is a contradiction if $E_1$ is finite, so $E_1$ is infinite and we expect an infinite number of turns and thus infinite earnings.

For other strategies:

Taking $n$ coins from the jar is equivalent to committing to taking one coin $n$ times in a row. Either way, the billionaire flips coins until she has gotten $n$ tails and refills the jar accordingly. So, there can be no other result.

Comments:

We can think of this problem as a kind of one-dimensional random walk. Like a balanced random walk, the expected number of steps to reach a point is infinite. However, the probability of eventually reaching 0 coins in the jar is still 100% -- this can be thought of as a case of Gambler's ruin. (In the model, the gambler's bankroll is the jar, although in the actual game our profit is determined by the number of steps.) (This does not contradict the infinite expected number of steps.)

$\endgroup$
2
  • 3
    $\begingroup$ The question says "billionaire" but interestingly every answer seems to assume an "infinillionaire". $\endgroup$
    – WhatsUp
    May 20 at 14:44
  • 4
    $\begingroup$ @WhatsUp: Obviously if the billionaire can run out of coins, there is a finite result (which we could calculate given that number). But, given the "math" tag, I think the word "billionaire" is irrelevant: the question says she refills the jar if she flips heads, and that's that. $\endgroup$
    – tehtmi
    May 20 at 14:53
4
$\begingroup$

The value of $n$ is important as follows:

It is completely irrelevant - every coin removed from the urn results in a series of tosses of the coin until a tail occurs, where each toss has 50% probability of adding a coin to the urn, and a 50% chance of moving on to the effect of the next coin removed.
Each coin removed has an expectation of adding $\frac12 + \frac14 + \frac18 + ... + \frac1{2^i} + ...$ additional coins, regardless of the value of $n$ chosen at each step.

The value of coins in the pot at the start of each turn will always be equal to

$100 + h - t$, where $h$ is the number of heads tossed so far, and $t$ is the number of tails, which simulates a simple random walk.

The game ends

the first time that $t = h + 100$. Although it could seem that the game could continue for ever, it will terminate with probability 1, and we could expect to calculate a finite expected value...

Currently this is a partial answer, as I don't currently have time to work out, and my google-fu failed to find the formula for

a simple random walk crossing a specified threshold.

Update: I later realised I abandoned a further edit and forgot to undelete this answer after fixing the misunderstanding that made me delete it initially... Gareth McCaughan♦ has since posted a more rigorous answer that demonstrates that

the expectation is in fact infinite.

Despite this,

although it could seem that the game could continue for ever, it will terminate with probability 1 - a random walk eventually visits all points an infinite number of times.

Also, for most games,

the actual result will be well within the billionaire's means - after about 10000 coin flips (not calculated nor correct formula determined - a rough approximation by "law of large numbers" where deviation is of the order of the square root of the number of samples), the number of coins in the pot would be expected to differ from the original number by around 100, and in cases where it differs in the negative direction, the game ends. The mathematical expectation is infinite because of a small minority of games that add arbitrarily large numbers of coins to the pot before eventually removing as many as they added (which will eventually occur with probability 1!).

For a slightly different analysis of why this is the expectation, consider what happens first between two events that must have equal probability:

  1. The pot becomes empty for the first time

  2. The pot doubles in value for the first time

The probability of

staying strictly between 0 and 200 coins forever is zero. On average we would expect to exceed those limits after something of the order of 10000 coins have been taken out of the pot (I'll call this $m$ later). Thus there is a 50:50 chance that we'll either double the pot or end the game.

After this,

It is just as though we started the game over, but with 200 coins in the pot, and the same analysis applies, but this time we expect to get 4 times as many coins out of the pot before it either doubles or becomes empty... each time we double the pot rather than ending the game, the next phase of the game will, on average, take 4 times as long, and get us 4 times the amount of money.

So our expected winnings by this analysis are:

$m + 4m(\frac12) + 16m(\frac14) + ... + 2^{2i}m\frac1{2^i} + ...$
which is the same as
$m(1 + 2 + 4 +... + 2^i + ...)$
which is infinite.

However, taking into account that we're playing against a billionaire

we should ignore all terms in that infinite series that exceed the billionaire's wealth. Even assuming a "gold coin billionaire" who has over a billion gold coins, they'll have to stop after adding something of the order of $km$, where k is of the order of 100000 or so. To get an easily calculable result, assume $m = 10000, k < 2^{17}$
so we sum only the terms up to the point we assume the billionaire will run out of money:
$m + 4m(\frac12) + 16m(\frac14) + ... + 2^{16}m\frac1{2^8}$
which is the same as
$m(1 + 2 + 4 + 8 + 16 + 32 + 64 + 128) = 255m$
As such, our expected winnings are around 2 or 3 million coins (although in practice, almost all games will end with winnings much less than 1 million coins).

$\endgroup$
3
  • $\begingroup$ So although the expectation is infinite, if you want to become a millionaire (take away a million coins) by playing this game, your chance is not that great. $\endgroup$
    – Eric
    May 21 at 7:48
  • 1
    $\begingroup$ @Eric ... and it just occurs as you mention this that if one asks "what is a fair price to play the billionaire in order to play the game", it's a direct analogue of the game typically associated with the St. Petersburg paradox. $\endgroup$
    – Steve
    May 21 at 8:00
  • 1
    $\begingroup$ @Eric I added some calculations using some gross simplifications... I'd be fascinated to see how close that is if someone has the time or inclination to do a mathematically more rigorous calculation, but not fascinated enough to do such myself! $\endgroup$
    – Steve
    May 21 at 9:25
3
$\begingroup$

What is the maximum and minimum expected number of coins you can extract from the game?

They are both infinite. The question seems to imply that different strategies would lead to different expected outcomes, but for any $n$ you take, the billionaire is expected to add $n$ coins back into the urn.

The expected number of coin flips until she reaches the $n$th tail is $n/p$, where $p$ is the probability of tails (in this case, 0.5). So for any $n$ you choose, she's expected to flip $n/0.5 = 2n$ times, which is expected to add $2n/2 = n$ coins back into the urn.

$\endgroup$
1
$\begingroup$

Between 500K and 500M gold coins, depending on the exact net worth of the billionaire

As others have explained, on average one gold coin is replaced for every coin you take. So the expectation is that the game goes on as long as the billionaire can continue replacing the coins.

A one-ounce gold coin sells for around 2000 US dollars according to this website I found with a Google search. A "billionaire" is a person whose net worth is at least one billion US dollars, so our billionaire can afford at least 500K gold coins. We can feel confident that this billionaire's net worth is less than one trillion US dollars (else she would be a "trillionaire"), so she cannot afford 500M gold coins.

(The total amount of gold in the world is 244K metric tons, which is equivalent to 8.6B one-ounce gold coins. So playing this game to completion would not exhaust the world's gold supply, though it would doubtless cause prices to rise.)

The minimum number of coins you could extract would be zero, by choosing not to take any. If you do not take any coins, the game would not end; but presumably you can go on with your life while the game is running, and eventually either you or the billionaire will die, ending the game.

$\endgroup$
1
  • $\begingroup$ I don't think this is how the game works. If you take n coins, only then will the millionairess flip coins, and even then she'll only pay off about 1/2 coin per flip. $\endgroup$
    – Tony Ennis
    May 21 at 17:35
1
$\begingroup$

This answer draws freely from other answers, in particular, @Gareth's and @Steve's.

As pointed out by others our strategy

is irrelevant, the outcome depends solely on the billionaire's coin tosses.

Let's assume that the billionaire gets cold feet once there are a total of M (M>100) coins in the pot. We can give a closed form solution for the expected time $E_{100,M}$ until either this happens or the game ends regularly. This provides a lower bound for the original question as we will walk away with at least an expected $\frac{E+100}2$ coins (if the game ended regularly, more if the billionaire chickened out), and this number can only increase if we revert to the original problem $E_{100,\infty}$ (infinite billionaire, no threshold M).

To map the game to a normal on-grid random walk we identify grid points with the number of coins in the pot plus the one we just took. (We always take a single coin.) Every heads toss is a hop to the right, every tails a hop to the left (by means of the coin we took to trigger the tosses). After the tails toss we transfer the coin we are holding to our purse and take a new one from the pot if possible.

Let $E_{k,M}$ be expected time to end from k coins in the jar. Then $E_{0,M}=E_{M,M}=0$ and $E_{k,M} = 1 + \frac 1 2 (E_{k-1,M}+E_{k+1,M})$. We can easily verify that this is solved by $E_{k,M} = k(M-k)$

Remember that for any $M$ this is a lower bound of $E_{100,\infty}$. As $E_{100,M}$ is unbounded it follows that $E_{100,\infty}$ cannot be finite.

How much intuition can we draw from the closed formula? Obviously, it is unfortunate that it lumps together regular and billionaire-gets-nervous endings.

Let us at least determine their relative frequencies. This can be done similarly to the approach used above:

Let $p_{k,M}$ be the probability for an irregular end. Then, simply, $p_{k,M} = \frac 1 2 (p_{k-1,M}+p_{k+1,M})$. This is therefore just a linear ramp $p_{k,M} = \frac k M$ with endpoints $p_{0,M} = 0$ and $p_{M,M} = 1$.

$\endgroup$
3
  • $\begingroup$ Is our strategy completely irrelevant? I mean the number of coins you take each time doesn't effect the expectation, but does it effect the variance? If our goal is to get away with say 10000 coins, does the probability depend on the strategy? $\endgroup$
    – Eric
    May 21 at 14:49
  • 1
    $\begingroup$ @Eric One can completely ignore what we are doing. Everything only depends on the billionaire's tosses. The game ends regularly the moment they have tossed 100 more tails than heads. What we earn is (total number of tosses + 100) / 2, also completely independent of what we are actually doing. $\endgroup$
    – loopy walt
    May 21 at 14:59
  • 1
    $\begingroup$ The expectation is infinite even if the billionaire starts with only 1 coin in the urn. So your probability of winning a certain amount of gold coins depends on the initial number of coins in the urn, not your strategy. $\endgroup$
    – Eric
    May 21 at 15:18
1
$\begingroup$

Well, mean is infinite (easy enough to see):

From starting 100 you have the same probability to first reach 0 or 200. From 200, you have again same probability to first reach 0 or 400. Etc. Amount of money you end up getting is area under the random walk, you have a sequence like 100s1+2000.5s2+4000.25*s3 etc; where s1... is the expected number of steps to first reach 0 from that value. No matter how many steps that is, it is obvious 0<s1<=s2 so even if we replace all steps with s1 we get infinite money.

Median is finite though.

In code I slightly simplified the problem -

instead of waiting on n tails, I performed n coin flips and put 2 coins back for each head. On average this gives the same number of coins back in the urn; the main difference is that I cannot ever get odd number of coins. Code (matlab) is below:

function [n,m,k] = so_coins(n)
% n=number of coins left in the urn. 
m=0; % number of coins taken so far
k=1; % steps performed - end condition.
while (n > 0 && k < 1000000) % stop after 1m steps of taking coins out.
   r=rand(n,1);
   m=m+n;
   k=k+1;
   n=2*sum(r > 0.5); % proclaim r>0.5 heads, r<0.5 tails       
end

I ran the following 1k times and it worked well enough. You should hope you never get a very long run with huge n, the code is very slow.

Minimum number of coins was 840. Median was 22500. Mean was 10^7. Maximum was 2.6*10^9 (it stopped in all cases). I was unlucky and didn't hit the "infinite streak" that would push mean to infinity. Maybe better luck next time :D

$\endgroup$
0
$\begingroup$

The minimum number of coins is 100: Take all 100 coins from the urn, and the billionaire hits the completely improbable (given that it’s a fair coin) string of no heads and 100 tails on flipping the coin. There is no maximum, because the billionaire can hit a completely improbable string of any number of heads before hitting that 100th tail. Regardless of how many coins are in the urn at the end of any turn, you take all of them.

$\endgroup$
1
  • 4
    $\begingroup$ OP requests min/max expected coins, based on different choices of n, not bare minimums/maximums $\endgroup$ May 20 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.