Million Dollar Urns

[BMAD]

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?

[superprismatic]

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

the fewest coins is 500000²/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.

[phil1882]

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.

[BMAD]

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

[phil1882]

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.

[superprismatic]

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 S_n be the number of coins in the urn with the smallest
number of coins after n coins have been urned. So, we have
L₂=1, S₂=1 which forces L₃=2, S₃=1. Our task is to estimate
S_1,000,000.

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

Using these recursions we get the following list of values for
n, L_n, and S_n:

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 S_1,000,000 is 1,000,000/3.

[plasmid]

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

[superprismatic]

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 " L₂=1, S₂=1 which forces L₃=2, S₃=1" earlier in the post.

[DeGe]

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

[bonanova]

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.

[plasmid]

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 October 10, 2013 by plasmid

[bonanova]

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

[superprismatic]

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

which is 500000/999999 + 499999*500000/999999
which is (500000²)/999999
which is 250000.250000250000250000...

[DeGe]

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

which is 500000/999999 + 499999*500000/999999

which is (500000²)/999999

which is 250000.250000250000250000...

I stand corrected

[bonanova]

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

[superprismatic]

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.

[bonanova]

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.