What is the distribution of the maximum of random variables? What started out a utilitarian question in my exploration of some generalized versions of the secretary problem turns out to be quite a deep topic.

(Note that I have little background in probability and statistics. Please forgive (and inform me of, so I can fix!) errors of notation or language. Or general confusion on my part.)

### Geometric Interpretation of Maximum

Consider the cumulative density function . You can picture two copies of the distribution as forming sides of a square. is the inside.

More generally, can be visualized as an -cube and equal to . By differentiation we get the probability density function,

(Note that we need to be a bit careful about the semantics of . This makes sense for discrete distributions, but for others we need to think of it as probability density. For the benefit of intuition, we will continue to use this notation, however.)

This can also be observed as a simple geometric fact, the probability being the expanding surface of the cube.

### Combinatorial Interpretation of Maximum

We may also observe that in a nice combinatorial way.

Given random variables , we imagine them ordered . (Note the notational difference between which is some arbitrary random variable and which is the one that turned out to be in position when we ordered them.)

There are possibilities for which random variable is the last one (). The probability that , which will be equal to the maximum, will be is . The probability that the other variables will be less than equal to is .

The result follows.

### Minimum

The probability that is the probability that are not all greater than .

The probability that that a particular variable is greater than is the probability that it isn’t less than or equal to it.

Therefore,

It this feels familiar to you, it’s probably because it’s just application of De Morgan’s law, equivalent to how A OR B is the same as NOT ((NOT A) AND (NOT B)).

You can also interpret this geometrically, similarly to how we interpreted maximum.

From here, differentiate to get probability density.

### Combinatorial Construction of Order Statistics

Suppose we have a number of random variables, from the same distribution. We want to know the distribution to expect from the random variable in a particular position after we order them, , the order statistics. Let’s consider the distribution to expect of a variable which has variables less than (or equal to) it and variables greater than (or equal to) it.

The number of ways to select elements for the less than set, for the actual element, and for the greater than from elements is . Then, the probability distribution of is

It’s a little bit less elegant, but the usual way to think of this is as , the -th order statistic of random variables. Or more so, as the -th order statistic of random variables.

(This is my first writing done in emacs org mode + LaTeX and wordpress integration. Thanks to Sacha Chua for help! This is awesome.)

Tags: math, probability, statistics

August 30, 2013 at 16:38 |

[…] 2013-08-30: By the way, here’s the link to Christopher Olah’s first post using org2blog. […]

January 23, 2014 at 06:47 |

Please post the org file that produced this page. Thanks.

July 1, 2014 at 01:43 |

Thanks for the exposition, I’ve been thinking about max distribution in the context of latency tail for parallel requests.