4.6 Order Statistics

Let $X$ be a random variable with cumulative distribution function $F_X(x)$. We can derive the distribution function for the minimum $Y_n=\min(X_1,X_2,\cdots,X_n)$ and for the maximum $Z_n=\max(X_1,X_2,\cdots,X_n)$ of $n$ IID random variables with cdf $F_X(x)$ as

Expected value of max and min

Let $X_1,X_2,\cdots,X_n$ be IID random variables with uniform distribution between 0 and 1. What are the cumulative distribution function, the probability density function and expected value of $Z_n=\max(X_1,X_2,\cdots,X_n)$? What are the cumulative distribution function, the probability density function and expected value of $Y_n=\min(X_1,X_2,\cdots,X_n)$?

Solution: This is a direct test of textbook knowledge. For uniform distribution on $[0,1]$, $F_X(x)=x$ and $f_X(x)=1$. Applying $F_X(x)$ and $f_X(x)$ to $Z_n=\max(X_1,X_2,\cdots,X_n)$ we have

and $E[Z_n]=\int_0^1 xf_{Z_n}(x)dx=\int_0^1 nx^n dx=\frac{n}{n+1}\left[x^{n+1}\right]_0^1=\frac{n}{n+1}$.

Applying $F_X(x)$ and $f_X(x)$ to $Y_n=\min(X_1,X_2,\cdots,X_n)$ we have

and $E[Y_n]=\int_0^1 nx(1-x)^{n-1}dx=\int_0^1 n(1-y)y^{n-1}dx=\left[y^n\right]_0^1-\frac{n}{n+1}\left[y^{n+1}\right]_0^1=\frac{1}{n+1}$.

Correlation of max and min

Let $X_1$ and $X_2$ be IID random variables with uniform distribution between 0 and 1, $Y=\min(X_1,X_2)$ and $Z=\max(X_1,X_2)$. What is the probability of $Y\ge y$ given that $Z\le z$ for any $y,z\in[0,1]$? What is the correlation of $Y$ and $Z$?

Solution: This problem is another demonstration that a figure is worth a thousand words. As shown in Figure 4.7, the probability that $Z\le z$ is simply the square with side length $z$. So $P(Z\le z)=z^2$. Since $Z=\max(X_1,X_2)$ and $Y=\min(X_1,X_2)$, we must have $Y\le Z$ for any pair of $X_1$ and $X_2$. So if $y>z$, $P(Y\ge y\mid Z\le z)=0$. For $y\le z$, that $X_1$ and $X_2$ satisfies $Y\ge y$ and $Z\le z$ is the square with vertices $(y,y),(z,y),(z,z)$, and $(y,z)$, which has an area $(z-y)^2$. So $P(Y\ge y\cap Z\le z)=(z-y)^2$. Hence

Now let’s move on to calculate the correlation of $Y$ and $Z$.

Using previous problem’s conclusions, we have $E[Y]=\frac{1}{2+1}=\frac{1}{3}$, $E[Z]=\frac{2}{2+1}=\frac{2}{3}$. From the pdfs of $Y$ and $Z$, $f_{Y_n}(x)=n(1-x)^{n-1}=2(1-x)$ and $f_Z(z)=nz^{n-1}=2z$, we can also get $E[Y_n^2]=\int_0^1 2(1-y)y^2dy=\frac{2}{3}-\frac{2}{4}=\frac{1}{6}$ and $E[Z_n^2]=\int_0^1 2z^3dz=\frac{2}{4}$, which give us the variances: $\operatorname{var}(Y)=E[Y^2]-E[Y]^2=\frac{1}{6}-\left(\frac{1}{3}\right)^2=\frac{1}{18}$ and $\operatorname{var}(Z)=\frac{2}{4}-\left(\frac{2}{3}\right)^2=\frac{1}{18}$.³³

To calculate $E[YZ]$, we can use $E[YZ]=\int_0^1\int_0^z yzf(y,z)dydz$. To solve this equation, we need $f(y,z)$. Let’s again go back to Figure 4.7. From the figure we can see that when $0\le z\le1$ and $0\le y\le z$, $F(y,z)$ is the shadowed area with probability

An alternative and simpler approach to calculate $E[YZ]$ is again to take advantage of symmetry. Notice that no matter $x_1\le x_2$ or $x_1>x_2$, we always have $yz=x_1x_2$ ($z=\max(x_1,x_2)$ and $y=\min(x_1,x_2)$).

Hence $\operatorname{cov}(Y,Z)=E[YZ]-E[Y]E[Z]=\frac{1}{36}$ and $\operatorname{corr}(Y,Z)=\frac{\operatorname{cov}(Y,Z)}{\sqrt{\operatorname{var}(Y)}\times\sqrt{\operatorname{var}(Z)}}=\frac{1}{2}$.

Sanity check: That $Y$ and $Z$ have positive autocorrelation make sense since when $Y$ becomes large, $Z$ tends to become large as well ($Z\ge Y$).

Random ants

500 ants are randomly put on a 1-foot string (independent uniform distribution for each ant between 0 and 1). Each ant randomly moves toward one end of the string (equal probability to the left or right) at constant speed of 1 foot/minute until it falls off at one end of the string. Also assume that the size of the ant is infinitely small. When two ants collide head-on, they both immediately change directions and keep on moving at 1 foot/min. What is the expected time for all ants to fall off the string?³⁴

Solution: This problem is often perceived to be a difficult one. The following components contribute to the complexity of the problem: The ants are randomly located; each ant can go either direction; an ant needs to change direction when it meets another ant. To solve the problem, let’s tackle these components.

When two ants collide head-on, both immediately change directions. What does it mean? The following diagram illustrates the key point:

Before collision: ; After collision: ; switch label:

When an ant $A$ collides with another ant $B$, both switch direction. But if we exchange the ants’ labels, it’s like that the collision never happens. $A$ continues to move to the right and $B$ moves to the left. Since the labels are randomly assigned anyway, collisions make no difference to the result. So we can assume that when two ants meet, each just keeps on going in its original direction. What about the random direction that each ant chooses? Once the collision is removed, we can use symmetry to argue that it makes no difference which direction that an ant goes either. That means if an ant is put at the $x$-th foot, the 103expected value for it to fall off is just $x$ min. If it goes in the other direction, simply set $x$ to $1-x$. So the original problem is equivalent to the following:

What is the expected value of the maximum of 500 IID random variables with uniform distribution between 0 and 1?

Clearly the answer is $\frac{499}{500}$ min, which is the expected time for all ants to fall off the string.