a jewel of a probability puzzle

I've been spending way too much time reading John Baez' Azimuth blog. It's got lots of fascinating stuff, but one piece that really caught my eye is a probability puzzle:

Suppose I have a box of jewels. The average value of a jewel in the box is \$10. I randomly pull one out of the box. What’s the probability that its value is at least \$100?

First thought, of course, is: "I don't have enough information; the answer will depend on the distribution".  But in fact you can give quite a strong bound on the answer even without knowing the distribution, using Markov's inequality: the probability is +++\le 1/10+++.

At first, this looks impossible: how can this be independent of the distribution?  Surely I can have some strange collection of jewels that violates this bound?  But no, and in the comments section there are some great explanations that give an intuition about why this is so, including David Guild's:

As long as gems have non-negative value, then (probability of pulling a \$100 or better gem > 10%) implies that (average value > \$10). Since the average is exactly \$10, then the probability can’t be more than 10%.

A very clear proof is laid out by Greg Egan. I'll rework it here, for the general case of an average value of +++a+++ (rather than the specific \$10) and a big value of +++b+++ (rather than \$100), to get the general result.

Let +++A+++ be the set of all jewels, +++\#A+++ be the size of set +++A+++, and +++V(x)+++ be the value of jewel +++x+++. Let +++B+++ be the set of "big value" jewels
$$ B = \{x\in A | V(x) \ge b\}$$We know the average value of the jewels is +++a+++:
$$ a =  \frac{1}{\#A} \sum_{x \in A} V(x) $$If we replace the sum over all jewels +++A+++ with the sum over the smaller set of jewels +++B+++, we must get a smaller answer (assuming that all the values are non-negative: necessary in the general case, and implicit in the given example).  So:
$$ a \ge  \frac{1}{\#A} \sum_{x \in B} V(x) $$From the definition of +++B+++, we have +++\forall x \in B, V(x) \ge b+++.  This implies that
$$ \frac{1}{\#A} \sum_{x \in B} V(x) \ge  \frac{1}{\#A} \sum_{x \in B} b  $$We can do this last sum:
$$ \frac{1}{\#A} \sum_{x \in B} b =  \frac{\#B}{\#A} b$$Putting this all together, we have
$$ a \ge  \frac{1}{\#A} \sum_{x \in B} V(x)  \ge \frac{1}{\#A} \sum_{x \in B} b = \frac{\#B}{\#A} b$$So
$$ a \ge  \frac{\#B}{\#A} b$$Rearranging gives the result that the proportion of big value items to all items (the probability of drawing a big value item) is:
$$ \frac{\#B}{\#A} \le \frac{a}{b}$$For the example with +++a=10+++ and +++b = 100+++, this gives us +++1/10+++.

This derivation assumes that the chance of pulling out any jewel is the same.  But, as Baez explains, the result is independent of this.  If some jewels are more likely to be picked, and that likelihood is used to define the average value too, then the result stands. (I leave the proof as an exercise for the reader.)

So, from a problem that initially looked as if it doesn't have nearly enough information, we've moved to an intuition about why a result (albeit only a bound) can be given, and a simple proof of a general result for that bound: Markov's inequality.  The power of maths!

There's also a result for values that can go negative, which requires also knowing the standard deviation: Chebyshev's  inequality.  It's all on John Baez' blog.  Go there, and you to  might spend as much time reading around as I have!