How many gold coins can you extract from the billionaire?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.)

Answer 4

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).

Answer 5

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.

Answer 6

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.

Answer 7

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$.

Answer 8

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

Answer 9

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.