# 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

-

Statisticians would usually refer to your "classes" as "bins".

Your requirements for "minimum number of bind" and "minimum size of the bins" are in opposition, and you would have to clarify how the conflict should be resolved. For instance, if one arrangement has 10 bins with 5 marks each, and another has 5 bins with 10 marks each, which is better? Or, one arrangement has 10 bins with 10 marks each, and another has 10 bins total, 9 with 9 marks each, and the last one with 19 marks. You have to specify a rule for how to identify which of any two arrangements is better. Only then can you ask how to achieve the best one, and whether it is unique.

-
Yes, the two requirements are in opposition. That's what makes me believe that there will be one "optimal" size and number of students. How about this rule: The summation of (product of size of a bin and the number of entries in it) should be minimum. – Utkarsh Sinha Dec 1 '10 at 15:13