# Gaussian Distribution + Hash Tables

The original question I posted on StackOverflow. I think it's more mathematically inclined so I posted it here again. In terms of math.

There's a class of students. Each students has a score between 0 and 300 (gaussian, with some known average and standard deviation). I need to find classes of marks (like 0-100, 101-125, 126-140, 141-160, 161-175, 176-200, 201-300) such that:

• The number of classes is minimum
• The number of students in each class is minimum

How do I go about doing this? Is this a standard problem? Also, is it possible to prove that only this set of classes will have the above property.

-
I remember this book tackles the problem of choosing a binning optimally: All of non-parametric statistics. –  Raskolnikov Dec 1 '10 at 14:02
@Raskolnikov: Thanks! I'll try to get that book. –  Utkarsh Sinha Dec 1 '10 at 15:14

You question is a bit underdefined, but in general what you're looking for is index (order?) statistics. For example, if the number of classes is to be $2$, you need to cut them at the median. If it's $3$, you cut them at the $1/3$ and $2/3$ order statistics, and so on. The classes will be entirely evenly-spread.

The former paragraph assumed the classes can depend on the data. If the classes are not supposed to depend only on the distribution, then you just need to find the index statistics for the distribution. For example, the median of a Gaussian is equal to its mean, and for the other points you can consult a table (there is no closed form). You can then estimate how evenly spread the scores are going to be, e.g. the spread in the L2 spread is given by a $\chi^2$ distribution, whose mean you can look up in Wikipedia.

-

To have the minimum number of classes, take a class from 0 to 300. To have the minimum number of students per class, take each different score to be a class.

More seriously, you generally need to define the number of classes you want, and whether you want all the classes to be about a given size. You might want this when giving grades, say 50% A's, 40% B's and 10% C's. For other applications you are just trying to group "things that are close enough together that we can treat them the same." If the distribution is a true Gaussian, with no noise, there is no nice answer. But with a reasonably small sample, you can just plot a histogram, look for scores that are relatively rare, and make the cut there.

In more than one dimension it gets harder. You might look at cluster analysis

-