Puzzle Time - Magnetic Dollars

[jon-nyc]

One million magnetic "susans" (Susan B. Anthony dollar coins) are tossed into two urns in the following fashion: The urns begin with one coin in each, then the remaining 999,998 coins are thrown in the air one by one.  If there are x coins in one urn and y in the other, magnetic attraction will cause the next coin to land in the first urn with probability x/(x+y), and in the second with probability y/(x+y).

What’s the expected value of the contents of the urn that ends up with fewer susans?

[Klaus]

Is there anything specific about "susans" that one should know about this puzzle?

Unless I'm missing something this looks relatively simple...

[jon-nyc]

Nope. Just dollar coins. They exist but never really circulate.

[Klaus]

One thing I find a little confusing about the task is the "ends up with fewer susans" part, because it could be the case that they have the same number of susans.

[Klaus]

I'd say the expected value is 250,000.

Let (a,b) describe the situation with a coins in urn 1 and b coins in urn 2.

The probability for (a,n-a) after round n is 1/(n+1) for any a, i.e., the distribution is uniform.

This sounds almost too simple for a Jon puzzle. Am I missing something?

[Klaus]

Another way to look at it: Without the "magnetic attraction", the distribution would be normal. But the magnetic attraction flattens the Gauss curve to be uniform.

[jon-nyc]

I get 1/3 of the coins in the lesser urn, so 333,333. Will lay out logic in a bit.

[jon-nyc]

Maybe run some simulations and see what you get

[jon-nyc]

Suppose the proportion of coins in the lesser urn is r after n coins have been tossed. Calculate the expected ratio after the n+1 toss.

This is:

r * (rn+1)/(n+1)
+
(1-r) * (rn/(n+1)

= r(n+1)/(n+1)

= r

So the expected ratio never changes. Toss 1, since we start with one coin in each urn, is guaranteed to give us a ratio of 1/3. This expected ratio is the same for any number of tosses. So one third of our million coins are expected to be in the lesser urn.

[Klaus]

This post is deleted!

[Klaus]

I'm not sure that's correct.

Take the situation after two tosses, that is 4 coins:

The probability distribution, unless I miscalculated, is as follows:

(2,2) with p = 0.33
(1,3) with p =0.33
(3,1) with p = 0.33

The expected value of the "lesser urn" is
1 x 0.33 + 1 x 0.33 = 0.66 or 16.5%.

With five coins in the system, the distribution is:

(1,4) 0.25
(2,3) 0.25
(3,2) 0.25
(4,1),0.25

Expected value of lesser urn:

1 x 0.25 + 2 x 0.25 + 2 x 0.25 + 1 x 0.25 = 1.5 or 30%.

After the next toss, we get that every combination has a probability of 0.2, yielding an expected value of 20% for the lesser urn.

The value oscillates around and converges to 25% by the argument in my post above.

[jon-nyc]

@klaus

I’m probably overlooking something obvious but how do you get from this:

The probability for (a,n-a) after round n is 1/(n+1) for any a, i.e., the distribution is uniform.

To 250k?

[Klaus]

@jon-nyc said in Puzzle Time - Magnetic Dollars:

@klaus

I’m probably overlooking something obvious but how do you get from this:

The probability for (a,n-a) after round n is 1/(n+1) for any a, i.e., the distribution is uniform.

To 250k?

Let's take n = 1,000,000 and consider only the first half of the distribution, i.e., (1, 999.999) to (499.999,500.000), all with equal. Urn 1 is always the one with fewer susans in this half. Let's project on the first component, i.e., the value of urn 1. This is now the uniform distribution unif{1,499.999}. Its mean is (1 + 499.999)/2 = 250.000, see also the last line of the screenshot from the Wikipedia entry on discrete uniform distributions.

By the same technique we can symmetrically analyze the second half of the distribution, which will also yield a mean of 250.000.

[jon-nyc]

I like your answer better than mine.

[Klaus]

@jon-nyc said in Puzzle Time - Magnetic Dollars:

I like your answer better than mine.

I've made a screenshot of that post and put a yearly reminder in my calendar.

Now, the icing on the cake would be if my answer is even correct

[jon-nyc]

Clever proof.

SOLUTION: You might very reasonably worry that one urn will "take over" and leave very little for the other. In my experience, faced with this problem, most people are unwilling to offer $100 in advance for the contents of the lesser urn.

In fact, the lesser urn is worth, on average, a quarter of a million dollars. (Of course, that doesn't mean you are willing to take this much risk!) This is because the final contents of (say) Urn A is precisely equally likely to be any whole number of dollars from $1 all the way to $999,999. Thus, the average amount in the lesser urn is about $250,000.

How can we see this? There are several proofs, but here's my favorite. Imagine that we shuffle a fresh-from-the-box deck of cards in the following careful manner. We place the first card, say the Ace of Spades, face down on the table. Then we take the second card, maybe the Deuce of Spades, and randomly place it over or under the ace. Now there are three possible slots for the Three of Spades; choose one at random, putting it on top of the current pile, under the current pile, or between the ace and deuce, each with probability 1/3.

We continue in this manner; the nth card is inserted in one of n possible slots, each with probability 1/n. The result eventually is a perfectly random permutation of the cards.

Now think of the cards that go in above the Ace of Spades as the coins (not counting the first) that go into Urn A, and the ones that go under as coins going into Urn B. The magnetic rule above describes the process perfectly, because if there are currently x−1 cards above the Ace of Spades (thus x slots) and y−1 cards under the Ace of Spades (thus y slots), the probability that the next card goes above the Ace of Spades is x/(x+y).

Since, in the final shuffled deck, the Ace of Spades is equally likely to be in any position, the number of slots ending up above it is equally likely to be anything from 1 to the number of cards in our deck, which for our puzzle is 999,999.

[Probabilists call the mechanism of this puzzle the Polya urn, after the late George Polya, a Hungarian-born professor at Stanford who famously wrote about problem-solving in mathematics.]