01 May 2010

The probability that 901 coins have total value $100

Here's a cute little problem from Reddit: Tough question for you guys. Let's say you have 901 coins that come out to exactly $100. What are the odds? (Also here.)

Everyone there who gets a solution is assuming that all the possible coins are equally likely, which isn't a reasonable assumption. Years ago I looked at the density of money, where I used a model in which I get back from each transaction n cents with probability 0.01, for n = 0, 1, ... 99; furthermore I always get back the smallest possible number of coins. The only coins allowed are pennies, nickels, dimes, and quarters (worth 1, 5, 10, and 25 cents respectively).

As I calculated before, if I make 100 transactions, and I get each number of cents back exactly once, I'll get 200 pennies, 40 nickels, 80 dimes, and 150 quarters. This is a total of 470 coins, and worth $49.50. Thus the "average coin" is worth 495/47 = 10.53 cents; 901 coins are "on average" worth $94.89. The value $100 isn't that unreasonable.

So consider a jar with 901 coins, which are independent; they each have probability 20/47 of being a penny, 4/47 of being a nickel, 8/47 of being a dime, and 15/47 of being a quarter. The mean value of a coin is 495/47 = 10.53 cents; the variance is 238840/2309 = 108.12 "square cents".

The mean value of 901 coins, then, is 9489 cents; the variance is 93198 "square cents", so the standard deviation is 305 cents. (Everything here is rounded to the nearest integer.)

Invoking the central limit theorem, then, we say that the value of 901 randomly chosen coins is normally distributed with this mean and standard deviation. The probability of having value exactly 10,000 cents is approximated by the probability density function of this variable at 10,000; that's 0.000322, or 1 in 3101.

An exact answer is feasible -- but not worth computing, I'd say, because the error in the central limit theorem is surely much smaller than the error from the fact that this isn't a realistic model of what actually ends up in your change jar.


Anonymous said...

It's harder to get if we exclude copper... but perhaps more interesting

Efrique said...

The problem with this sort of calculation is that the event of interest is defined after the observation, not before.

The effective "event" is therefore
... whatever would make the person say "What are the odds of THAT!??"

The chances that *something* odd would happen is not all that low.

There are many combinations of large numbers of coins that would make one say "what are the odds of that?". The restriction to 901 coins seems entirely arbitrary, since if it had been 899 coins, would that not also have generated a similar question? The restriction to $100 also seems arbitrary - might not a similar question have been generated with a total of some other very round amount?

When there are lots of replications, it becomes even less surprising that something might happen...

If someone wins the lottery, they might ask "wow, what are the odds of that", but almost anyone else winning it would ask the same question... and what are the chances that somebody won the lottery?

Any calculation of the probability of a post-specified event as if it were a pre-specified event is ridiculously wrong, and leads to many of the abuses of statistics we see. People have ended up in jail on the basis of bad calculations like this.

Hooked said...

The exact answer isn't hard to compute if we consider each coin to be equally likely - it's a classic example of generating functions. I'll give an example and link to Wolfram alpha for the math, but to do so I have to use a smaller problem ($50 instead of $100).

The number of ways one could make $50 using 901 coins (.01, .05, .10, .25) is simply the coefficient in front of the x^5000 term in the expansion of:



Which is ~ 10^475

If you can choose those coins any way you like you get:

Eval -> (x=1) (x+x^5+x^10+x^25)^901

Which is ~ 10^542

Thus the odds are about 10^(-67), very, very small. This is of course a different answer then posted as we assumed each coin is equally likely (and I used $50 since Wolfram craps out at $100). Also as Efrique said, this _particular_ event is rare - however we typically look at the probability of getting some _range_, ie. the probability of 901 coins being < $100.