Sat, 20 Dec 2003

Allocating rounding errors fairly

Last Monday, I visited a client in California. Their programmer showed me some code he'd been working on and mentioned that he was having some difficulty with rounding errors accumulating.

I shared a technique with him I've used to solve the same problem.

Having way too much time in airports and on planes to think about it, I realized that the method I shared, while quite good for most cases, fails to allocate rounding errors fairly in extreme cases. I spent many hours since trying to find an optimal solution.

Consider the problem of distributing money, evenly, across three accounts. If we only have one cent to distribute, which account should get it?

Using the naive rounding method, none of the accounts will get anything and we will be left with one cent undistributed.

Using the technique I shared with Russ, we would consider the first account and attempt to distribute 1/3 cents. That rounds to zero. We would then restate the problem as distributing our single cent across the remaining two accounts. So, we would attempt to distribute 1/2 cent to the second account. That rounds to one cent. Finally, having nothing left to distribute, we assign zero cents to the third account.

This works well for any number of accounts ensuring that the maximum rounding error applied to any given account is less than one cent.

But what happens if we distribute one cent to the same three accounts 10,000 times? Ideally, two accounts should end up with $33.33 and one should end up with $33.34.

Using naive rounding, all three accounts would still have zero balances. Using the second method described, the first and third accounts would have zero balances, and the second account would have a balance of $100.00, since it would always get the benefit of the rounding errors.

I spent a lot of time working on a fair method for distributing the rounding errors. I'm certain I spent my time simply reinventing the wheel, but it was a very interesting problem to solve.

Consider the same problem: distributing $0.01 across 3 accounts.

The first account should get 1/3 cents. Since we can't divide a cent, we'll give the first account a 1 in 3 chance at rounding up. 2 out of 3 times, we'll move on to the second account and give it a 1 out of 2 chance at rounding up. 1 out of 2 times we'll still have our cent to distribute and we'll move to the third account, which will always get the cent if we reach it, because it is the only remaining account.

If you work out the math, you'll see that each account has exactly a 1 in three chance at getting the cent.

• The first account gets a 1 in 3 chance directly.
• 2 out of 3 times, the second account gets a 1 out of 2 chance; 2/3 x ½= 1/3.
• The third account gets a 1 out of 1 chance if the other two accounts do not get it. The odds of the first two accounts not getting the cent are 2/3 * ½= 1/3.

Surprisingly (at least it surprised me), this works out with any amount to be allocated, and with any weighting.

For instance, assume we have 3 accounts with weights 1, 2, and 1 respectively. If we want to allocate 1 cent to these accounts, we would attempt to allocate ¼cents to the first account, giving it a 1 in 4 chance to round up. 3 out of 4 times, we'll move to the second account and give it a 2 out of 3 chance (2 is it's weight, and we consider only the remaining 2 accounts for a total weight of 3) at rounding up.

To allocate a larger number, we simply allocate the the integer portion after multiplying the amount to allocate by the account's weight and dividing by the total weight. The odds of rounding up are given by the fractional remainder. We reduce the total amount to be allocated by the amount allocated to each account and the total weight by the account's weight at each round and move on.

The following perl subroutine demonstrates the algorithm:

 # usage: allocate(amount, weight_1, weight_2, ..., weight_n)
 # returns an array of n allocated amounts
 sub allocate {
    my $value = shift;
    my $basis = 0;
    $basis += $_ for @_;
    map {
       my $allocation = $value * $_ / $basis;
       my $allocated = int($allocation);
       my $remainder = $allocation - $allocated;
       ++$allocated if rand() < $remainder;
       $basis -= $_;
       $value -= $allocated;
       $allocated;
    } @_;
 }

[/programming] [link]

About this weblog

This site is the personal weblog of Marc Mims. You can contact Marc by sending e-mail to:
[email protected].

Marc writes here about cycling, programming, Linux, and other items of personal interest.

This site is syndicated with RSS.

Credits

CSS stolen from Tom Coates who didn't even complain.