MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Once again stackexchange is not responding to one of my questions (so far no comments, no answers, two up-votes). Hence this "crossposting":

Is there a simple (or not simple?) algorithm that will churn out examples of pairs of moderately small finite multisets (hereinafter called "sets") of moderately small integers satisfying the following desiderata, or at least the first several of them, for suitable values of "several"?

  • The first set in the pair has a larger standard deviation and a smaller mean absolute deviation from the mean than the second;
  • The SD and/or the MAD are, at least approximately, what I want them to be;
  • The mean is an integer;
  • The SD and/or the MAD is an integer;
  • The are right-skewed or left-skewed or concentrated near the mean or approximately uniformly distributed according according to the user's choice.
  • One can in other (specify) ways make them do one's bidding.
share|cite|improve this question
Maybe the stats stackexchange or stack overflow. Is this to generate homeworks and exams? Would you be interested in a randomized search that runs until it is stopped and is not guaranteed to find anything interesting? – psd Sep 28 '11 at 23:47
It could be useful for generating exercises or exam questions. What I was actually thinking of was something that could be presented in class to show that the two ideas are essentially different. – Michael Hardy Sep 29 '11 at 0:26

This is kind of a vague problem statement, so I don't feel bad about giving a vague answer. Pick some distribution over the reals that has the properties you like, like being concentrated on the integers, or being skew or whatever (integrality of the mean, SD or MAD is harder to get). Construct sets by i.i.d. sampling from this distribution. Look at the SD and the MAD for each set. They will be correlated, but not perfectly correlated. If you construct enough sets, eventually you will get a pair with the desired relation of their SD and MAD. If you were to scatter-plot the SD versus the MAD, you would see a cloud of points that are mostly along the southwest-northeast diagonal. What you need is to throw so many points into that cloud that some pair of them are connected northwest-southeast.

share|cite|improve this answer
This may well be the only way to proceed, but it seems like solving a Diophantine equation by randomly picking tuples of integers and seeing whether they are solutions. Maybe picking these at random and checking to see whether they have the desired properties is quicker than any sort of systematic searching, but it might also be nice to have an algorithm that didn't require checking lots of wrong answers before getting a right answer. – Michael Hardy Sep 29 '11 at 14:20

There are a lot of ways to bend this question. Is the emphasis on finding clean/briefly exhibited examples, or is the emphasis really on searching?

If I just want an instructive set of examples, maybe one wants a family of examples. E.g.:

  • {-s,s} (population sd of s, mean absolute deviation from mean (henceforward MADM) of s)
  • s*{-j^2,j^2, 0 repeated 2*j^2-2 times} (population sd of s*j, MADM of s)

But if I truly want an class of algorithms to exhibit more peculiar examples, then I think we should generalize the problem to searching over multisets of integers exhibiting some property P. Given such an algorithm one could apply it twice to find a multiset for the left and right sides of the pair. I interpret the question that we desire to find multisets that are as simple as possible, i.e. having as few distinct elements as possible, and as few elements in total as possible, and as small of values as possible. If we settle on a total ordering on multisets consistent with these criteria, then we can make progress with an exhaustive algorithm that eliminates all simple possibilities before moving to more complex ones. The algorithm could be assisted with search bounds that would limit the number of things for it to try so that it can eliminate entire search branches as early as possible (ala branch and bound). For example, to have mean 0 and sd=s with a total set size of less than n, one needn't consider any sets with an element of absolute value larger than s*sqrt(n). The more results of this sort we can prove, the fewer possibilities the search needs to try.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.