# Distribution of a ordered pile of rubble

Imagine a pile of rubble () where the separated elements of the pile are stones (). By picking stones we form a sample that we can sort by weight. A sequence becomes , where is called “rank”.

Pretend that we do the following. Apon picking a sample and sorting it we put stones into drawers and mark each drawer by rank. Now repeat the procedure again and again (picking a sample, sorting and putting stones into drawers). After several repetitions, we find out that drawer # contains the lightest stones, whereas drawer # the heaviest. An interesting observation is that by repeating the procedure indefinitely we would be able to put all parenting set (the whole pile or the whole range of parenting distribution) into drawers and later do the opposite — take all stones (from all drawers) mix them to get back the parenting set. (The fact that distributions (and moments) of stones of particular rank and the parenting distribution are related is probably the most thought-provoking)

Now let us consider the drawers. Obviously, the weight of stones in a given drawer (in a rank) is not the same. Furthermore, they are random and governed by some distribution. In other words, they are, in turn, a random variable, called order statistics. Let us label this random variable , where is a rank. Thus a sorted sample looks like this

Its elements (a set of elements (stones) from the general set (pile) with rank (drawer)) are called order statistics.

//////////////

Elements and are called “extreme”. If is odd, a value with number is central. If is of order this statistics is called “ central” A curious question is how define “extreme” elements if . If increases, then increases as we.

//////////////

Let us derive a density function of order statistics with the sample size of . Assume that parenting distribution and  density are continues everywhere. We’ll be dealing with a random variable which share the same range as a parenting distribution (if a stone comes from the pile it won’t be bigger than the biggest stone in that pile).

The figure has and and the function of interest . Index indicates the size of the sample. The axis has values that belong to a particular realization of

The probability that m-order statistics is in the neuborhood of is by definition (recall identity: ):

We can express this probability in term of parenting distribution , thus relating and .

(This bit was a little tricky for me; read it twice with a nap in between) Consider that realization of is a trias (a sequence generated by parenting distribution, rather then the order statistics; remember that range is common) where “success” is when a value is observed, and “failure” is when (if still necessary return to a pile and stone metaphor). Obviously, the probability of success is , and of a failure is . The number of successes is equal to , failures is equal to , because value of in a sample of a size is such that values are less and values are higher than it.

Clearly, that the process of counting of successes has a binomial distribution. (recall that probability of getting exactly successes in trials is given by pms:  In words, successes occur with and failures occur with probability . However, the successes can occur anywhere among the trials, and there are different ways of distributing successes in a sequence of trials. A little more about it)

The probability for the parenting distribution to take the value close to is an element of .

The probability  of sample to be close to in such a way that elements are to the left of it and to the rights, and the random variable to be in the neighborgood of it is equal to:

Note that this is exactly , thus:

Furthermore if from switching from to we maintaine the scale of axis then

The expression shows that the density of order statistics depends on the parenting distribution, the rank and the samples size. Note the distribution of extreme values, when and

The maximum to the right element has the distribution and the minimumal . As an example observe order statistics for ranks with the sample size for uniform distribution on the interval . Applying the last formula with (and thus we get the density of the smallest element

;

the middle element

and the maximal

.

With full concordance with the intuition, the density of the middle value is symmetric in regard to the parenting distribution, whereas the density of extreme values is bounded by the range of the parenting distribution and increases to a corresponding bound.

Note another interesting property of order statistics. By summing densities and dividing the result over their number:

on the interval

The normolized sum of order statistics turned out to equla the parenting distribution . It means that parenting distibution is combination of order statistics . Just like above had been mentioned that after sorting the general set by ranks we could mix the sorting back together to get the general set.