wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Magnetic Money
        
(Message started by: ThudanBlunder on Aug 20^th, 2010, 7:58am)

Title: Magnetic Money
Post by ThudanBlunder on Aug 20^th, 2010, 7:58am

A million magnetic pennies are thrown into two large urns such that:

1) The urns begin with a single penny in each and the remaining pennies are then thrown into the air one-by-one.

2) If there are n pennies in one urn and m in the other, then due to their magnetism pennies will fall into the first urn with probability n/(n + m) and into the second urn with probability m/(n + m).

How much are you and your silicon friends willing to pay in advance for the urn that ends up with fewer pennies?

Title: Re: Magnetic Money
Post by towr on Aug 20^th, 2010, 2:01pm

I'll go out on a limb and say [hide]very slightly more than a quarter million.[/hide]
And I'm not cutting in my silicon friends :P

(I'll try proving it later; but it seems to fit, from what I can see.)

Title: Re: Magnetic Money
Post by towr on Aug 21^st, 2010, 4:22am

[hide]
All outcomes are equally likely. So (1, N-1) (2, N-2) up to (N-1, 1) all occur with probability 1 in N-1.
From that it's easy to find that the expected payoff is (N+1)/4 if N is odd, and (N+1 + 1/(N-1) )/4 if N is even.
So I ought to have said: very slightly more than a quarter million and a quarter.

Of course, it remains to be proven that the outcomes are equally likely. So:

Consider one of the urns, and consider the distribution of states it can be in. We can represent it as an array of probabilities (indexed starting from 1); e.g. [1/2, 1/2] to say there's a 50% chance that there is one coin in it, and 50% chance there are two (and implicitly a probability of 0 for all other indices.)

The base case is [1], since the urn starts off with one coin it it when N=2.

Now assume that for N-1, we have A_N-1 = [1/(N-2), 1/(N-2), ..., 1/(N-2)], and we then add another coin.
Then there is (N-2)/(N-1) probability that an urn with one coin doesn't gain an extra coin, and 1/(N-1) probability that it gains one.
Similarly, for other indices i < N-1 there's an (N-1-i)/(N-1) probability of not gaining a coin, and a probability of i/(N-1) of gaining one.

So,
for i=1
A_N[1] = (N-2)/(N-1) A_N-1[1] = (N-2)/(N-1) * 1/(N-2) = 1/(N-1)
for 1 < i < N-1
A_N[i] =
(N-1-i)/(N-1) A_N-1[i] + (i-1)/(N-1) A_N-1[i-1] =
(N-2)/(N-1) * 1/(N-2) = 1/(N-1)
for i=N-1
A_N[i] =
(N-2)/(N-1) A_N-1[N-2] = (N-2)/(N-1) * 1/(N-2) = 1/(N-1)
So they are all equal again.

Therefore, for all N >= 2 we have A_N[i]=1/(N-1) for 0 < i < N and 0 otherwise.
[/hide]

How would it work out if we had three urns?