János A. Csirik's Web Site Distribution of coin types

The distribution of coin types in a jar

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:

• the distribution of prices modulo $1 is uniform; and
• change is always returned using the smallest possible number of coins.

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:

• b and c are zero: this is impossible, since the triple (0,e,f) is worth 25, 50 or 75 cents and so cannot possibly be optimal: If e is no more than four and and f is no more than one then it can be worth at most 45 cents, so it must be worth exactly 25 cents. Then there must be at least one nickel (so the total is not divisible by 10 cents) and therefore (0,e,f)=(0,2,1) which is not optimal.
• b and f are zero: this can't happen. By optimality, e is no more than four, which leaves us with either a quarter and a nickel vs. three dimes, which does not satisfy our conditions since 2<3; or a quarter and three nickels vs. four dimes, where the greedy algorithm still does better, by producing a quarter, a dime, and a nickel.
• e and c are zero: this can't happen, since then any coin from the first triple is more valuable than any coin in the second one. Therefore, to have an equal amount, the first triple should have fewer total coins, which contradicts our assumption again.
• e and f are zero: this can't happen, then the second triple is worth nothing, whereas the first one is worth at least 25 cents.

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

• 0 cents: no coins;
• 5 cents: one nickel;
• 10 cents: one dime;
• 15 cents: one dime, one nickel;
• 20 cents: two dimes.

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.