3
$\begingroup$

I keep bouncing into the following result. Let $X$ be a random variable with a cumulative distribution function $P(X<x)$. We draw $n$ independent values from this distribution, and the minimum of these $n$ values is $x_{min}$. Then for large $n$, it is true that:

$P(X< \langle x_{min}\rangle) = 1/n$

where $\langle x_{min}\rangle$ denotes the mean of $x_{min}$ over many trials. Can anyone please provide a proof and an intuitive understanding of the above relation?

$\endgroup$
  • 1
    $\begingroup$ Lookup extreme value theory, it deals with extrema of random variables $\endgroup$ – Aksakal Feb 13 '18 at 20:28
  • 6
    $\begingroup$ This is not universally true. For instance, with $P(X\lt x) = 1/x^2$ for $x\le -1$, the limiting value of $P(X \lt E[x_{\text{min}}])$ as $n\to \infty$ is $1/(n\pi)$, not $1/n$. It looks like it might be true for any continuous random variable that has a finite lower bound and possibly for continuous variables that don't have overly heavy left tails. Simple counterexamples are easy to find if $X$ is not continuous. For instance, when $X$ has a Bernoulli$(p)$ distribution, $P(X \lt E[x_{\text{min}}])=1-p$ for all $n$. $\endgroup$ – whuber Feb 13 '18 at 22:08
  • 6
    $\begingroup$ I disagree with the closure of this question as a duplicate of "How is the minimum of a set of random variables distributed?" and have voted to reopen it The answers of that question have little to say about the question asked here: "Then for large $n$, it is true that: $$P(X< \langle x_{min}\rangle) = 1/n$$ where $\langle x_{min}\rangle$ denotes the mean of $x_{min}$ over many trials. Can anyone please provide a proof and an intuitive understanding of the above relation?" $\endgroup$ – Dilip Sarwate Feb 14 '18 at 14:50
  • $\begingroup$ What is the mathematical version of "the mean of $x_\text{min}$ over many trials"? $\endgroup$ – Xi'an Feb 14 '18 at 19:06
  • $\begingroup$ @Xi'an that would be the expected value of the minima. $\endgroup$ – Botond Feb 15 '18 at 16:05
5
$\begingroup$

For $n$ independent random variables $X_i$ each uniformly distributed on $[0,1]$, $E[X_{(1)}]$, the expected value of the minimum is known to be $\frac{1}{n+1}$ and so $$P\left\{X < E[X_{(1)}]\right\} = \frac{1}{n+1}$$ which is nearly the result you are looking for.

If the random variables are exponential random variables with parameter $\lambda$, the minimum is an exponential random variable with parameter $n\lambda$ and hence expected value $\frac{1}{n\lambda}$. Now we have $$P\left\{X < E[X_{(1)}]\right\} = P\left\{X < \frac{1}{n\lambda}\right\} = 1 - \exp\left(-\lambda\left(\frac{1}{n\lambda}\right)\right) = 1-\exp\left(-\frac 1n\right).$$ Since $1-\exp\left(-\frac 1n\right)\approx\frac 1n$ for large $n$ via the Taylor series for the exponential function, this too is nearly the result you are looking for.

More generally, for large values of $n$, the empirical CDF of $n$ independent samples of $X$ is a staircase function that is a reasonably good approximation of the actual CDF $F_X(x)$. For continuous random variables, the empirical CDF has value $\frac 1n$ at the smallest sample value $x_{(1)} = x_{\min}$, and so $F_X(x_{\min})$ can be expected to be reasonably close to $\frac 1n$ for large $n$. Unless $E[X_{(1)}] = \langle x_{\min} \rangle$ decreases rapidly with increasing $n$ (as can happen with heavy-tailed distributions with nonfinite expectation, cf. @whuber's comment on the OP's question), it is reasonable to expect that $P\{X < \langle x_{\min} \rangle\}$ also is approximately $\frac 1n$. That's about as much of an intuitive explanation as I can provide for the result stated by the OP.

$\endgroup$
6
$\begingroup$

The statement seems to be true for distributions whose lower tail of the CDF is approximately linear.

This is a proof for a distribution that is restricted to the domain from 0 to $a$ with $a$ finite,

The restricted domain is for simplicity, but I believe it can be extended to any finite lower bound and infinite upper bounds (in this way it relates to Whuber's conjecture that it looks like it might be true for continuous distributions with finite lower bounds.):

$$\begin{array}\\ \left< x_{min} \right> & = \int_{0}^{a} x P(x=x_{min}) dx \\ & = \int_{0}^a n x f(x) (1-F(x))^{n-1} dx\\ &= -x(1-F(x))^n\vert_{0}^{a} + \int_{0}^{a}(1-F(x))^n dx\\ &=\int_{0}^{a}(1-F(x))^n dx \\ \end{array}$$

Some more elegant shortcut to get to the above result would be to use the CDF for the minimal value $F_{min}=1-(1-F(x))^n$ as starting point, along with $E(X_{min}) = \int (1-F_{min}(x))dx$. But I happened to have started with this more clumsy, but more direct, derivation and I like it.

now I am taking a bit of an intuitive step but you can imagine that, when n goes to infinity, the integral is determined by the slope of $1-F(x)$ at $x=0$ (where $1-F(x)$ is closest to 1 and diminishes the least for growing $n \to \infty$).

So, let the taylor expansion of $F(x)$ be

$$ F(x) = b_1x + b_2x^2+b_3x^3+...$$ and the integral is then approximately (where I admit I have no strong argument):

$$ \left< x_{min} \right> = \int_0^a (1-F(x))^n = \int_0^a (1- b_1x - b_2x^2-b_3x^3+...)^n \simeq \frac{1}{b_1n} \qquad \text{ for } n\to \infty $$

and

$$P\left( X< \left< x_{min} \right> \right) = F\left( \left< x_{min} \right> \right) \simeq F \left( \frac{1}{b_1n} \right) = b_1\frac{1}{b_1n} + b_2 \left( \frac{1}{b_1n} \right)^2+... \simeq \frac{1}{n} $$


I believe that a proof could go according to these lines. I have marked two sentences in bold where I haven't been precise.

  • The first one about 'the limitation of the domain' is, I believe, not such a big deal but requires some more nasty descriptions of the integrals and the algebra. (but if we try to make the lower bound infinite then this method of proof doesn't work and this makes sense with Whuber's comments that '$P(X < x_{min}) = \frac{1}{n}$' is not generally true)
  • The second one about 'the integral being defined by the slope' is more difficult and I used intuition but could not turn it into a formal proof.

Note!:

I assumed the Taylor expansion to be:

$$ F(x) = b_1x + b_2x^2+b_3x^3+...$$

with non-zero coefficient $b_1$. This is a strong requirement. For instance if $F(x) = x^2$ from 0 to 1 then:

$$\begin{array}\\ \left< x_{min} \right> &=\int_{0}^{1}(1-x^2)^n dx = \frac{\sqrt{\pi} \Gamma \left( n+1 \right)}{2 \Gamma \left( n+\frac{3}{2} \right)} \\ \end{array}$$

and if you plug that into $F(x)=x^2$

$$\begin{array}\\ F(\left< x_{min} \right>) = \left(\frac{\sqrt{\pi} \Gamma \left( n+1 \right)}{2 \Gamma \left( n+\frac{3}{2} \right)}\right)^2 = \frac{\pi}{4n} + \mathcal{O} \left( \left( \frac{1}{n} \right)^2 \right) \\ \end{array}$$

So we can say that it is only true if F(x) is approximately linear near the lower bound

an intuition is that if the distribution of the minimum value is not continuous (linear F(x)), in the limit, then you will sample relatively lower values when you are below $\frac{1}{n}$ than high values when you are above $\frac{1}{n}$. Imagine that the $x_{min}$ will be equally often above and below the $\frac{1}{n}$-th percentile but the values sampled below will 'count relatively stronger' and 'push' the $\left< x_{min} \right> $ a bit below the $\frac{1}{n}$-th percentile.

It is a bit similar to why mean and modus are not the same. In this case you shrink the concept of mean and modus to the lower end of percentile by taking the limit of the minimum of $n$ variables, and if the distribution is not linear then your "1/n-th modus" and "1/n-th mean" won't agree.

$\endgroup$
  • 2
    $\begingroup$ This is supposed to be valid for large $n$ only. $\endgroup$ – Botond Feb 13 '18 at 20:50
  • 2
    $\begingroup$ I am always making these proofs like a physicist, not so rigourous, but because of Dilip's comment 'to look for a proof' I have still kept this answer even though it is quite a rough sketch. (I currently wonder what would be the result when the Taylor expansion of the cdf has $b_1=0$ which I assumed not to be the case). $\endgroup$ – Martijn Weterings Feb 14 '18 at 15:46
5
$\begingroup$

Here's more of a heuristic approach to understanding why something resembling the equation $P(X < \langle x_{min} \rangle) = 1/n$ makes sense in a broader context.

Let's use $F$ for the cdf of $X$, so that $P(X \leq t) = F(t)$. Let's also use $M_{n}$ to denote a random variable formed by taking the minimum of $n$ independent draws from $X$'s distribution. Finally, let's assume that $F$ is continuous and strictly increasing. (Basically, we want to insure that $F$ has a well-defined inverse function.)

Now let's think about the distribution of $M_{n}$. By a standard argument we have

\begin{equation} P(M_{n} > t) = (1 - F(t))^{n}. \end{equation}

Substituting $t = F^{-1}(c/n)$ into this equation, we get

\begin{equation} P[M_{n} > F^{-1}(c/n)] = (1 - c/n)^{n} \approx e^{-c} \end{equation}

for $n$ large. Interpreting this a little more, we can say that the median of $M_{n}$ is around $F^{-1}(\frac{\ln 2}{n})$, and the middle 50% of $M_{n}$'s mass lies roughly between $F^{-1}(\frac{0.29}{n})$ and $F^{-1}(\frac{1.39}{n})$. I would tend to think of this as a key insight: the mass of $M_{n}$ is concentrated near where $F \approx 1/n$. It's reasonable, then, to think that the mean of $M_{n}$ might follow a similar pattern. For example, the mean might look like $F^{-1}(\gamma/n)$ for some $\gamma > 0$. (This is where we get hand-wavey about the details.)

If we now assume this form for the mean (expectation) of $M_{n}$, we can circle back to the start: what is $P(X < \langle x_{min} \rangle)$? Or to use equivalent notation, what is $P(X < EM_{n})$? It is precisely $F(EM_{n}) = F(F^{-1}(\gamma / n)) = \gamma / n$. This isn't quite the same as $P(X < \langle x_{min} \rangle) = 1/n$, but it's in the ballpark.

$\endgroup$
  • 1
    $\begingroup$ This get's very close to my very lengthy answer. The statement that the mean $M_n \sim F^{-1}(\gamma/n)$ is key. We can say that $\gamma=1$ only when the left tail of $F$ is approximately linear. $\endgroup$ – Martijn Weterings Feb 14 '18 at 16:48
  • $\begingroup$ @MartijnWeterings "Approximately linear" can cover an awful lot of ground! $\endgroup$ – whuber Feb 14 '18 at 17:00
  • $\begingroup$ @whuber In my answer I worked with a Taylor series expansion at the boundary where F(x)=0 and first I assumed that the coefficient for the linear term was non-zero but then I found that the method of the proof does not work when this is not the case. Then I found out that the very simple pdf f(x)=2x from 0 to 1 is already making the statement of the OP not valid (so it is not only about a finite lower bound). $$\\$$ So that's what I mean with approximately linear. When it has a taylor series expansion with a non zero coefficient for the linear term. $\endgroup$ – Martijn Weterings Feb 14 '18 at 17:06
  • $\begingroup$ Maybe the idea of 'approximately linear' could be changed to allow it to be extended to distributions that do not have finite left tails. $\endgroup$ – Martijn Weterings Feb 14 '18 at 17:09
  • $\begingroup$ Exactly--that's where "approximately linear" needs a little elaboration. $\endgroup$ – whuber Feb 14 '18 at 22:53
5
$\begingroup$

As another counterexample, suppose the $X_i$'s are Weibull with scale parameter $\theta=1$ and shape parameter $\alpha$ such that $F(x) = 1-e^{-x^\alpha}$. The cdf of the minimum is then $ F_{X_{(1)}}(x) = 1 - (1-F(x))^n = 1-e^{-n x^\alpha}, $ that is, Weibull with shape $\alpha$ and scale parameter $\theta=n^{-1/\alpha}$. Hence, $E X_{(1)}=n^{-1/\alpha}\Gamma(\frac1\alpha+1)$ and $$ P(X<EX_{(1)}) = 1-e^{-\frac1n\Gamma(\frac1\alpha+1)^\alpha}\approx \frac1n \Gamma(\frac1\alpha+1)^\alpha $$ for large $n$ which only equals $1/n$ for $\alpha=1$ (the exponential case).

For a heavy left tail, e.g. $\alpha=.01$, $\Gamma(1/\alpha+1)^\alpha=37.99$ so then there would be a big difference indeed. For large $\alpha$, $\Gamma(1/\alpha+1)^\alpha$ tends to a limiting value of $e^{-\gamma}=0.56$.

$\endgroup$
  • 2
    $\begingroup$ +1 To complete the argument, we need to evaluate the limiting value of the coefficient of $1/n$ on the right hand side: after all, if its limit is $1$, then the result arguably is true for all sufficiently large $n$. However, the limit actually is $e^{-\gamma}\approx 0.56 \ne 1$. $\endgroup$ – whuber Feb 14 '18 at 15:35
  • $\begingroup$ But α is just a constant model parameter and is in no way going to infinity. $\endgroup$ – Jarle Tufto Feb 15 '18 at 13:08
  • $\begingroup$ I apologize. I was reading your post on a reduced-resolution device and the "$\alpha$" looked like an "$n$"! Regardless, it remains of interest to know how far $\Gamma(1/\alpha+1)^\alpha$ might depart from $1$: if it's always very close, the distinction you're making might be purely of theoretical interest but of no practical value. The limiting argument shows that for sufficiently large $\alpha$ your example indeed produces probabilities differing appreciably from $1/n$. $\endgroup$ – whuber Feb 15 '18 at 16:12
  • 1
    $\begingroup$ Yes, good point. For heavy left tails, e.g. $\alpha=.01$, $\Gamma(1/\alpha+1)^\alpha=37.99$ so then there is a big difference indeed. $\endgroup$ – Jarle Tufto Feb 15 '18 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.