Taking the mean of a data set with a skewed distribution

Question

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?

Answer 1

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.

Answer 2

I would take a look at the median score and see if it is a better representation of what you want. If not you can do two other things. 1) Use the mean and standard deviation. Yes, I know that is 2 numbers, but it would give you a better representation of the distribution. 2) Use the mean and standard deviation to come up with a composite score. e.g. you might want to divide the mean by the standard deviation, or come up with some other linear combination of these two factors depending upon what you feel is more important. If you are "loath" to take the average, for example, you might want to give more weight to the standard deviation, e.g. 60% of the total score. But even so, two numbers are better, and I would plot the scores to see if they made sense.