# Taking the mean of a data set with a skewed distribution

I'm running experiements that record the time my algorithm takes to solve a set of problem instances on a particular benchmark. Each problem has an associated difficulty in the range [1, n]. Ideally these should be evenly distributed across the difficulty spectrum but this is not the case: the problem sample I have is skewed toward the easier end of the spectrum.

To account for this, I have grouped the problems by difficulty e.g. [1-10], [11-20], ... , [n-9, n]. Each interval usually contains contains at least 10 problems (usually more; 50+ is not uncommon) and I take the average time required to solve all problems in each interval. This gives me a clearer picture of how my algorithm performs on both easy and hard problems with the caveat that the data is somewhat less reliable for the harder end of the spectrum.

First question: is this okay or are there some gotchas I haven't accounted for?

Next: For comparative purposes, I need to summarise performance on each benchmark as a single number. I am loath to simply take the average across all problems as this figure is skewed by too many easy problems. Which brings me to...

Second question: can I take an average of all interval averages instead?

-
Wouldn't the skewness be a more appropriate measure here? I say this because this seems to be what you are interested in. So rather than take the average time $\overline{t}$, take $\frac{1}{n}\sum_{i}(t_{i}-\overline{t})^{3}$, or why not take both mean and skewness? Any particular reason you can't take two numbers? –  probabilityislogic May 2 '11 at 8:18
I understand you have n problems grouped by difficulties. But what do you mean when you say “each benchmark”? By “interval averages” do you mean averages within a difficulty-group? –  GaBorgulya May 2 '11 at 10:16

You have a hierarchy of measurements, the first level of multiple time measurements on problem number $i$ ($1\leq i \leq n$), the second level is multiple problems of the same difficulty group.

Level 1. The measured times follow a distribution. This distribution may be normal (if the run time is influence by a large number of more or less independent factors), exponential distribution (if the algorithm waits for a random event to occur), or something complicated (e.g. multimodal, where run time strongly depends on initial decisions). The average is useful in case of the normal and exponential distributions, but may not be useful in the complicated cases without a large number of runs on the same problem. To determine the distribution of run times it may be useful to (a) pick a couple of problems, and measure the run time with a large number of repetitions, (b) to think over the mechanism, the details of the algorithm. You may find that a few repetitions are generally enough, or that many repetitions are needed and perhaps median may be a better statistic than mean.

Level 2. The difficulties within a difficulty group are not the same, but you think that they are similar. The differences in run times between groups may be small or large. If the times within difficulty groups are close to each other compared to the differences between adjacent difficulty groups it may not be very important to find a perfect summary measure to characterise a difficulty group, mean will probably do. If, however, the differences between difficulty groups are small you probably want to have the best summary measure of the difficulty of groups. In this case again, the distribution of problem times within a difficulty group decides which method to use.

I generally advice against using “a single number”, because usually expressing the level of uncertainty is almost as important as finding the most likely values.

-