|János A. Csirik's Web Site Distribution of coin types|
What is the distribution of coins in your change jar?
(This page deals with U.S. coins only. For other currencies, similar calculations are possible. In fact, the calculation is much simpler for currencies where the value of each coin evenly divides the value of each of the coins of larger value.)
Assume that someone always pays for all purchases using bills, and saves the resulting change to be dumped into a change jar. Assume that:
First, observe that the number of pennies is each of 0, 1, 2, 3 or 4 equally frequently, therefore the expected number of pennies is 2. We may now restrict our attention to amount of change divisible by 5 cents.
Let the triple (a,b,c) denote a quarters, b dimes and c nickels. Let such a triple be called optimal if there is no way to pay the same amount of change using fewer coins. Clearly, if (a,b,c) is optimal it must be the case that a is less than four (otherwise, a dollar bill would be given), b is less than five (otherwise, five dimes would be replaced by two quarters), and c is less than two (otherwise, a dime would be substituted for two nickels). A triple (a,b,c) cannot be optimal if b is at least two and c is at least one, since the two dimes and the nickel could then be exchanged for a quarter. It is also always true that if the triple (a,b,c) is optimal and we reduce any of its non-zero entries by one, it will still be optimal.
Does paying out the maximum possible number of quarters, then dealing with the dimes and nickels (the greedy algorithm) always result in using the fewest possible coins? To investigate this, assume that the triple (a,b,c) and the optimal triple (d,e,f) represent the same amount of change, but a+b+c>=d+e+f, despite the fact that a>d. Setting a'=a-d we have that (a',b,c) and (0,e,f) represent the same amount of change (and the second triple is still optimal). Similary, we can assume that one or both of b and e is zero; and that one or both of c and f is zero. There are now four possibilities:
Now we know that for any amount, the greedy algorithm gives us the only possible optimal triple. Therefore, it is clear that the number of quarters is 0, 1, 2 or 3 in the same number of transactions, so the expected number of quarters in any transaction is 1.5.
For paying out 0, 5, 10, 15 or 20 cents, the optimal allocation of nickels and dimes is clear (no more than one nickel, if needed), yielding
In summary, in a single transaction, the expected number of coins received is 4.7, consisting of 1.5 quarters, 0.8 dimes, 0.4 nickels and 2 pennies. The expected total value of the coins received is of course 49.5 cents (since we have assumed that it is uniformly distributed among the integers 0, 1, ..., 99), consisting of 37.5 cents in quarters, 8 cents in dimes, 2 cents in nickels and 2 cents in pennies. These imply the distributions of the coins by number of by value as stated above.
As for the weights of the coins, apparently they are 5.670 grams for a quarter, 2.268 grams for a dime, 5.000 grams for a nickel, and 2.500 grams for a penny. Thus, in a single transaction, the expected weight of coins received is 17.319 g, consisting of 8.505 g of quarters, 1.814 g of dimes, 2.000 g of nickels and 5.000 g of pennies. This implies the distribution of the coins by weight as stated above.
Finally, since the expected value of the coins received in a single transaction is 49.5 cents and their expected weight is 17.319 g, it follows that we can expect 1 kilogram of mixed coins (of the above distribution) to be worth about $28.58, which is about $12.96 a pound.
PS. Are you interested in how many ways there are to pay a fixed amount of money using coins? Here is a document by Alex Healy that you will find helpful.
This page was last edited on 11th February 2003, but pages linked from here might have been edited more recently. HTML 4.01.