Normalizing double values for probability calculus

Question

I want to normalize weights in a list of particles. These weights belong to particle-objects. I try to normalize them by dividing them with the sum of the weights. All the weights are declared in doubles. When the program starts dividing at the start of the list, the value is correct, but soon after second or third division, I get wrong results.. which has the consequence that the sum of the weights after the operation is not 1, which it should be. Can anyone help me with this problem ? Maybe something to do with threading ? Thx in advance..

// normalizing weights
double weightsum = 0;
double check = 0;
List<ParticleRobot> temporalparticleSet = new List<ParticleRobot>();

for (int i = 0; i < particleSet.Count; i++)
{
    weightsum = weightsum + this.particleSet[i].Weight;
}

Program.Weightsum = weightsum;

Console.WriteLine("Sum of unnormalized particleweights is " + weightsum);

foreach (ParticleRobot p in this.particleSet)
{
    Program.Weight = p.Weight;
    p.Weight = Program.Weight / Program.Weightsum;
    Console.WriteLine("Updated Particleweight is now : " + p.Weight);
}

// checking that they sum up to 1
for (int i = 0; i < particleSet.Count; i++)
{
    check = check + this.particleSet[i].Weight;
}

Console.WriteLine("Check: Sum of particles-weights is = " + check);

Answer 1

First off, what is temporalparticleSet? Do you actually mean to be looping through that instead of this.particleSet? Other than that I don't see any issues with the code at all. I would modify:

Program.Weight = p.Weight;
p.Weight = Program.Weight / Program.Weightsum;

to

p.Weight = p.Weight / Program.Weight;

Also is p.Weight a double? Might be some rounding issue. Have you tried using a breakpoint and stepping through it?

Answer 2

Not a threading issue probably. Read up on floating point math in any numerical analysis book.Check out http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html. Rounding errors, precision issues, cancellation issues all can contribute.

Answer 3

I would be concerned that Program.Weight modifies the value it is assigned or is not the same data type.

I would try changing the following lines:

        Program.Weight = p.Weight;
        p.Weight = Program.Weight / Program.Weightsum;

to

        p.Weight = p.Weight / Program.Weightsum;

There are also rounding errors to consider.

Answer 4

Accumulation of a large set of numbers can lose precision. Here are two techniques that can help:

1. Sum the weights in increasing order of weight, starting with the lightest and proceeding to the heaviest. If the numbers can be negative, sum in order of increasing magnitude.
2. Use the Kahan summation algorithm to accumulate the weights. This is easier than (1) because it is not necessary to sort the array first.
3. Use both of the above, if the ratio of the sum to the smallest weight is huge, like 10^16.