BrainDen.com - Brain Teasers
• 0

# Million Dollar Urns

Go to solution Solved by superprismatic,

## Question

One million dollar coins are thrown into two urns in the following manner: At the beginning of the process, each urn contains one coin. The remaining 999,998 coins are thrown in one by one. Each coin lands into one of the two urns with different probabilities. If at any stage of the process the first urn contains x coins and the second urn contains y coins, then the probabilities that the thrown coin will fall into the first or second urn are:

x/(x+y) and y/(x+y)

The question is: how much should you pay (in advance) for the contents of the urn that contains the smaller amount of coins?

## Recommended Posts

• 0
• Solution

Since the expected value of the number of coins in the urn having

the fewest coins is 5000002/999999, a fair value to
play the game would be that number of dollars. That would be
\$250,000.250000250000250000... But, I would be a cheapskate and
offer a measly \$250,000 to play.
##### Share on other sites
• 0

assuming you mean 1 million coins each valued at 1 dollar,

and that x/(x+y) is probability for urn 1, and y/(x+y) is for urn 2,

based on computer sim, i get roughly 75000.

##### Share on other sites
• 0

so let's verify it for a small case. let's say we have 7 coins.

both urns start with 1 coin, so, the probability the coin will fall in urn 1 or urn 2 = 50% for both.

after the first coin, one of the urns will have 2 coins, the other 1.

so the probability that the coin will fall in the smaller urn is 1/3.

if it falls in the smaller urn, your back at 50/50 else your at 1/4.

smaller urn can then either be 1/5, or 2/5.

then either 1/6, 1/3, or 1/2.

and finally 1/7 2/7 or 3/7.

therefore the expected value for 7 coins is...

1+1/2 +1/3 +2/3*1/4 +1/3*1/2 +2/3*3/4*1/5 +1/3*1/2*2/5

+2/3*3/4*4/5*1/6 +1/3*1/2*2/5*1/2 +2/3*1/4*2/5*1/3

+2/3*3/4*4/5*5/6*1/7 +1/3*1/2*2/5*1/3*2/7 +1/3*1/2*2/5*2/3*3/7 = 2.528.

calculating for 1,000,000 would take a while.

still we have an approximate answer. roughly 36% the amount.

##### Share on other sites
• 0

Let L

n be the number of coins in the urn with the largest
number of coins after n coins have been urned. Similarly,
Let Sn be the number of coins in the urn with the smallest
number of coins after n coins have been urned. So, we have
L2=1, S2=1 which forces L3=2, S3=1. Our task is to estimate
S1,000,000.

Now, a simple probability calculation gives the expected values of
Ln and Sn in terms of Ln-1 and Sn-1 to be:
Ln=Ln-1+(Ln-1/(Ln-1+Sn-1))
Sn=Sn-1+(Sn-1/(Ln-1+Sn-1))

Using these recursions we get the following list of values for
n, Ln, and Sn:

2, 1, 1
3, 2, 1
4, 8/3, 4/3
5, 10/3, 5/3
6, 12/3, 6/3
7, 14/3, 7/3
.
.
.
n, 2n/3, n/3

So, the expected value of S1,000,000 is 1,000,000/3.
##### Share on other sites
• 0

In general, applying the recursive formulas proposed for any given starting ratio of L:S would keep the same L:S ratio after every step. Something seemed fishy about the fact that if you apply this at the L:S = 1:1 step you would get a vastly different answer than if you say WOLOG that you can start after the third coin is added to have L:S = 2:1.

Suppose instead of starting to do recursions after the third coin is added, you instead considered cases explicitly a little longer first. After adding the fourth coin, there is a 2/3 chance of having L=3 and S=1, and a 1/3 chance of having L=S=2, which would necessarily become L=3 and S=2 after the next coin is added. If you apply recursion at that point, you would have:

2/3 probability of starting from L:S = 3:1 = 0.75:0.25

1/3 probability of starting from L:S = 2:2 followed by 3:2 = 0.6:0.4

Overall ratio of L:S = 0.7:0.3 = 7:3

##### Share on other sites
• 0

In general, applying the recursive formulas proposed for any given starting ratio of L:S would keep the same L:S ratio after every step. Something seemed fishy about the fact that if you apply this at the L:S = 1:1 step you would get a vastly different answer than if you say WOLOG that you can start after the third coin is added to have L:S = 2:1.

Suppose instead of starting to do recursions after the third coin is added, you instead considered cases explicitly a little longer first. After adding the fourth coin, there is a 2/3 chance of having L=3 and S=1, and a 1/3 chance of having L=S=2, which would necessarily become L=3 and S=2 after the next coin is added. If you apply recursion at that point, you would have:

2/3 probability of starting from L:S = 3:1 = 0.75:0.25

1/3 probability of starting from L:S = 2:2 followed by 3:2 = 0.6:0.4

Overall ratio of L:S = 0.7:0.3 = 7:3

I mistakenly put the "2, 1, 1" in the list. You're correct that the recursion starts with "3, 2, 1". That's why I said " L2=1, S2=1 which forces L3=2, S3=1" earlier in the post.

##### Share on other sites
• 0

Let there be 2n coins in the urn at any stage.

Then the bag with smaller number of coins can have 1,2,3,....n coins.

It so happens that the probability for the smaller bag to have 1,2,3... n-1 coins is equal (lets say x) and for it to have n coins is x/2 such that the sum of x*(n-1) + x/2 = 1

I got this hypothesis by using brute force - calculating probabilities with total 8,10,12,14,16 coins.

Therefore for 1M coins, the probability for the smaller bag to have 1,2,3,... 499 999 coins is equal and probability for it to have 500 000 coins is half of this probability.

So, 499 999x + x/2 = 1

x = 1/499 999.5 = 2/999 999

It follows then that the expected number of coins is 499 999/2 + 500 000/999 999; this is equal to 250 000.000015

So you can pay 250 K for the bag in advance

##### Share on other sites
• 0

One million dollar coins are thrown into two urns in the following manner: At the beginning of the process, each urn contains one coin. The remaining 999,998 coins are thrown in one by one. Each coin lands into one of the two urns with different probabilities. If at any stage of the process the first urn contains x coins and the second urn contains y coins, then the probabilities that the thrown coin will fall into the first or second urn are:

x/(x+y) and y/(x+y)

The question is: how much should you pay (in advance) for the contents of the urn that contains the smaller amount of coins?

Without loss of generality coin 3 goes into the X urn: x = 2; y = 1.

Coin 4 is now twice as likely to enter urn X as urn Y, maintaining the expected ratio <r> = <x>/<y> = 2.

After 999,999 coins are tossed, <x> =666,666; <y> = 333,333.

Since urn X is more likely to get the millionth coin,

I'd pay no more than 333,333 coins for the emptiest urn.

##### Share on other sites
• 0

This is a problem where it's actually advantageous NOT to apply "without loss of generality".

Call the urns R and L (for Right and Left) rather than smallest and greatest.

When 2 coins are in play:

R has 1 coin (with probability 1)

When 3 coins are in play:

R has 2 coins with probability 1/2

R has 1 coin with probability 1/2

When 4 coins are in play:

R has 3 coins if it had 2 in the previous round AND a coin was added to R -- probability 1/2 x 2/3 = 1/3

R has 2 coins if EITHER (it had 2 in the previous round AND a coin was added to L) OR (it had 1 in the previous round AND a coin was added to R) -- probability (1/2 x 1/3) + (1/2 x 1/3) = 1/3

R has 1 coin if it had 1 in the previous round AND a coin was added to L -- probability 1/2 x 2/3 = 1/3

When N+1 coins are in play, if you know that on round N each possible number of coins in urn R had equal probability (which would be 1/(N-1)):

R has C coins if EITHER (R had C in the previous round AND a coin was added to L) OR (R had C-1 in the previous round AND a coin was added to R) -- probability [1/(N-1) x (N-C)/N] + [1/(N-1) x (C-1)/N] = 1/(N-1) x [(N-C) + (C-1)] / N = 1/(N-1) x (N-1)/N = 1/N

So the probability that urn R contains C coins on round N+1 is 1/N regardless of the value of C -- all possibilities are equally likely.

Now if instead of calling the urns Right and Left, we call them Smallest and Greatest, it's clear that the probability of every possible value for S is equal except where S = N/2... there is only one case where S = R = L, but for all other values of S there is a case where R = S and a case where L = S.

Edited by plasmid
##### Share on other sites
• 0

WOLOG isn't needed in my previous explanation. Rather,

Coin 3 goes into one of the urns. Call that urn X.

Now x/y = 2 and for Coin 4, p(X)/p(Y) = 2 which on average maintains <x>/<y> = 2,

making min = 333 333. And, if you could add frational coins, that is the correct result.

But...

Confirmation of 250000

100 trials.

Max: 493767

Min: 001264

Avg: 261357 Another 100 trials with individual results ordered, showing linear (even distribution) behavior.

Max: 497404

Min: 002756

Avg: 263134 ##### Share on other sites
• 0

The expected value will be 500000/999999 + Sum(2*i/999999)

which is 500000/999999 + 499999*500000/999999

which is (5000002)/999999

which is 250000.250000250000250000...

I stand corrected

##### Share on other sites
• 0

OK someone help me out on this. If the cases are 1 ... N/2, and there are TWO cases for all of them but N/2, for which there is only ONE case, then why isn't the average slightly LESS than N/4?

And since this is my 4999th post, does that mean the next one has to be profound in some way? I'm in trouble. :~}

##### Share on other sites
• 0

OK someone help me out on this. If the cases are 1 ... N/2, and there are TWO cases for all of them but N/2, for which there is only ONE case, then why isn't the average slightly LESS than N/4?

And since this is my 4999th post, does that mean the next one has to be profound in some way? I'm in trouble. :~}

I'm not sure how to answer this, but consider that the average of the first 2n integers is (2n+1)/2, not n. It is larger by 1/2.

##### Share on other sites
• 0

OK someone help me out on this. If the cases are 1 ... N/2, and there are TWO cases for all of them but N/2, for which there is only ONE case, then why isn't the average slightly LESS than N/4?

And since this is my 4999th post, does that mean the next one has to be profound in some way? I'm in trouble. :~}

I'm not sure how to answer this, but consider that the average of the first 2n integers is (2n+1)/2, not n. It is larger by 1/2.

Yes.

You'd need to include zero to make it n.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

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