Coin distribution

What is the distribution of coins you'd expect to see in a coin jar? This post will make a guess based on the following simplifying assumptions.

1. Change is in US currency, with coins in denominations of 1, 5, 10, and 25 cents.
2. The change due in a transaction is uniformly distributed from 0 to 99 cents.
3. Clerks make change with the fewest number of coins possible.

Each of these assumptions is basically accurate, though you could find exceptions to each [1]. It would be interesting to compare the results here to an empirical survey of actual coin jars.

What distribution of coins would you expect given these assumptions?

You can make change with the fewest number of coins by giving out as many quarters (25 cent pieces) as possible first, then as many dimes (10 cent pieces) as possible next, etc. Here's Python code implementing this algorithm.

 def make_change(n): quarters = n // 25 n -= 25*quarters dimes = n // 10 n -= 10*dimes nickels = n // 5 n -= 5*nickels pennies = n return (quarters, dimes, nickels, pennies)

Exercise: Give an example of a coin system in which the analogous algorithm does not give the fewest number of coins. Why does it work for US coin denominations?

You can use the code above to confirm that on each transaction, you expect to get back 1.5 quarters, 0.8 dimes, 0.4 nickels, and 2 pennies. So based on this you'd expect a jar of coins to be 32% quarters, 17% dimes, 8.5% nickels, and 42.5% pennies.

Related post: Making change with Scheme and generating functions

[1] An actual coin jar is likely to contain these coins, plus an assortment of pesos, buttons, arcade tokens, etc. Prices before adding sales tax may not be so uniform, with a bias toward prices ending in multiples of 5, and more prices ending in 95 than in 5, but adding sales tax makes the distribution more uniform. Clerks may not give out optimal change because they may be out of one kind of coin. And of course some people spend their change, and may have a bias toward spending some coins over others.

The post Coin distribution first appeared on John D. Cook.