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.
- Change is in US currency, with coins in denominations of 1, 5, 10, and 25 cents.
- The change due in a transaction is uniformly distributed from 0 to 99 cents.
- 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.
Interestingly, there is a dataset on the distribution of coins in the wallets of ~22.5k participants in Europe: https://data.mendeley.com/datasets/f257j67ym6/2
Fun post. Here’s a similar analysis that yielded results in line with yours (see below). I believe real jars will have fewer quarters and more pennies because (a) people spend quarters, and (b) clerks will often round up your change and forgo giving out pennies.
[1] https://dfkoz.tumblr.com/post/20389927354/whats-a-pound-of-change-worth
I think in a 1, 3, 4 cent coin system:
Making 6 cents of change: optimal is 3+3, but the algorithm would give 4+1+1?
I think the rule might be that the delta between coins is >= the smaller coin?
Another tweak in the spirit of Jack’s enhancement –
1) A non-uniform skew of prices to “$X.99” will tend to put prices close-to-but-just-below a round dollar amount.
2) State+Local taxes (https://taxfoundation.org/2020-sales-taxes/) generally add about 9% or less to price.
Going off of what Douglas said, I think the rule is that the spacing between coins needs to be monotonically increasing.
Another fun case is making 25c of change in US coin system but the 25c piece is a 13c piece. 13+10+1+1 instead of 10+10+5
Those interested in the greedy change-making algorithm and optimal denomination sequences should read this paper by Jeffrey Shallit, which received some coverage in the popular press: “What This Country Needs is an 18¢ Piece” https://cs.uwaterloo.ca/~shallit/Papers/change2.pdf