Distribution of a ordered pile of rubble

Facebook Tweet LinkedIn

Imagine a pile of rubble ( $X$ ) where the separated elements of the pile are stones ( $x_i$ ). By picking $n$ stones we form a sample that we can sort by weight. A sequence $x_1,x_2,...,x_n$ becomes $x_{(1)},x_{(2)},...,x_{(m)},...x_{(n)}$ , where $(m)$ is called “rank”.

Pretend that we do the following. Apon picking a sample and sorting it we put stones into $n$ 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 # $1$ contains the lightest stones, whereas drawer # $n$ 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 $X_{(m)}$ , where $m$ is a rank. Thus a sorted sample looks like this

$X_{(1)},X_{(2)},...,X_{(m)},...,X_{(n)}$

Its elements $X_{(m)}$ (a set of elements (stones) $x$ from the general set $X$ (pile) with rank $m$ (drawer)) are called $m$ order statistics.

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

Elements $X_{1}$ and $X_{(n)}$ are called “extreme”. If $n$ is odd, a value with number $m=\frac{(n+1)}{2}$ is central. If $m$ is of order $\frac{n}{2}$ this statistics is called “ $m$ central” A curious question is how define “extreme” elements if $n \to \infty$ . If $n$ increases, then $m$ increases as we.

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

Let us derive a density function of $m$ order statistics with the sample size of $n$ . Assume that parenting distribution $F(x)$ and density $f(x)$ are continues everywhere. We’ll be dealing with a random variable $X_{(m)}$ 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).

Untitled

The figure has $F(x)$ and $f(x)$ and the function of interest $\varphi_n (\cdot)$ . Index $n$ indicates the size of the sample. The $x$ axis has values $x_{(1)},...,x_{(m)},...,x_{(n)}$ that belong to a particular realization of $X_{(1)},X_{(2)},...,X_{(m)},...,X_{(n)}$

The probability that m-order statistics $X_{(m)}$ is in the neuborhood of $x_{(m)}$ is by definition (recall identity: $dF = F(X + dx) - F(x) = \frac{{F(x + dx) - F(x)}}{{dx}} \cdot dx = f(x) \cdot dx &s=-3$ ):

$dF_{n}(x_{(m)})=p[x_{(m)}<X_{(m)}<x_{(m)}+dx_{(m)}]=\varphi_n (x_{(m)})dx_{m}$

We can express this probability in term of parenting distribution $F(x)$ , thus relating $\varphi_n (x_{(m)})$ and $F(x)$ .

(This bit was a little tricky for me; read it twice with a nap in between) Consider that realization of $x_1,...,x_i,...,x_n$ 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 $X<x_{(m)}$ is observed, and “failure” is when $X>x_{(m)}$ (if still necessary return to a pile and stone metaphor). Obviously, the probability of success is $F(x_{(m)})$ , and of a failure is $1-F(x_{(m)})$ . The number of successes is equal to $m-1$ , failures is equal to $n-m$ , because $m$ value of $x_m$ in a sample of a size $n$ is such that $m-1$ values are less and $n-m$ values are higher than it.

Clearly, that the process of counting of successes has a binomial distribution. (recall that probability of getting exactly $k &s=-3$ successes in $n &s=-3$ trials is given by pms: $p(k;n,p) = p(X = k) = \left( \begin{array}{l} n\\ k \end{array} \right){p^k}{(1 - p)^{n - k}} &s=-3$ In words, $k &s=-3$ successes occur with $p^k &s=-3$ and $n-k &s=-3$ failures occur with probability $(1-p)^{n-k} &s=-3$ . However, the $k &s=-3$ successes can occur anywhere among the $n &s=-3$ trials, and there are $\left( \begin{array}{l} n\\ k \end{array} \right) &s=-3$ different ways of distributing $k &s=-3$ successes in a sequence of $n &s=-3$ trials. A little more about it)

The probability for the parenting distribution to take the value close to $x_{(m)}$ is an element of $dF(x_{(m)})=f(x_{(m)})dx$ .

The probability of sample to be close to $x_{(m)}$ in such a way that $m-1$ elements are to the left of it and $n-m$ to the rights, and the random variable $X$ to be in the neighborgood of it is equal to:

$C_{n - 1}^{m - 1}{[F({x_{(m)}})]^{m - 1}}{[1 - F({x_{(m)}})]^{n - m}}f({x_m})dx$

Note that this is exactly $p[x_{(m)}<X_{(m)}<x_{(m)}+dx_{(m)}]$ , thus:

$\varphi_n (x_{(m)})dx_{m}=C_{n - 1}^{m - 1}{[F({x_{(m)}})]^{m - 1}}{[1 - F({x_{(m)}})]^{n - m}}f({x_m})dx$

Furthermore if from switching from $f(x)$ to $\varphi_n (x_{(m)})$ we maintaine the scale of $x$ axis then

$\varphi_n (x_{(m)})=C_{n - 1}^{m - 1}{[F({x_{(m)}})]^{m - 1}}{[1 - F({x_{(m)}})]^{n - m}}f({x_m})$

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 $m=1$ and $m=n$

The maximum to the right element has the distribution $F^{n}(x)$ and the minimumal $1-[1-F(x)]^n$ . As an example observe order statistics for ranks $m=1,2,3$ with the sample size $n=3$ for uniform distribution on the interval $[0,1]$ . Applying the last formula with $f(x)=1$ (and thus $F(x)=x$ we get the density of the smallest element

$\varphi_3 (x_{(1)})=3(1-2x+x^2)$ ;

the middle element

$\varphi_3 (x_{(2)})=6(x-x^2)$

and the maximal

$\varphi_3 (x_{(3)})=3x^2$ .

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 $\varphi_3 (x_{(1)}), \varphi_3 (x_{(2)}), \varphi_3 (x_{(3)})$ and dividing the result over their number:

$\frac{1}{3}\sum\limits_{m = 1}^3 {{\varphi _3}({x_{(m)}}) = \frac{1}{3}(3 - 6x + 3{x^2} + 6x - 6{x^2} + 3{x^2}) = 1 = f(x)}$

on the interval $[0,1]$

The normolized sum of order statistics turned out to equla the parenting distribution $f(x)$ . It means that parenting distibution is combination of order statistics $X_{(m)}$ . 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.

Further read: Ефимов-1980; Arnord-balakrishnan-2008.

Facebook Tweet LinkedIn

One Reply to “Distribution of a ordered pile of rubble”

foloren torium says:

01.04.2019 at 19:40

Pretty section of content. I just stumbled upon your web site and in accession capital to assert that I get in fact enjoyed account your blog posts. Anyway I will be subscribing to your augment and even I achievement you access consistently fast.

Distribution of a ordered pile of rubble

Published by Sergey Alexeev

One Reply to “Distribution of a ordered pile of rubble”

Leave a Reply Cancel reply