• 0

Million Dollar Urns

Question

Posted · Report post

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?

0

Share this post


Link to post
Share on other sites

16 answers to this question

  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

lol, yes. I mean 1 million, $1 coins. verify the solution

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

post-1048-0-67744600-1381401257_thumb.gi

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

Max: 497404

Min: 002756

Avg: 263134

post-1048-0-10399300-1381401880_thumb.gi

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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. :~}

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

My bad.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.