Let $(X_i)_{i\leq N}$ be a set of i.i.d. random variables, with $X_i$ mapping to some interval $[a,b]$.
Let $Y_{k:N}$ be the $k$th order statistic of this set and $v\in[a,b]$.
Denote by $f_X,F_X$ the continuous pdf and the continuous CDF of $X_i$ and by $f_{Y_{k:N}}$ the pdf of $Y_{k:N}$

Quantity of interest
I am interested in the truncated expectation of the order statistic $$E[Y_{k:N}|Y_{k:N}>v].$$ This can be written as $$E[Y_{k:N}|Y_{k:N}>v]=\frac{\int_v^\infty yf_{Y_{k:N}}(y)dy}{\int_v^\infty f_{Y_{k:N}}(y)dy}.$$ Conjecture
Computing this quantity in MATLAB, suggests that $$E[Y_{k:N}|Y_{k:N}>v]\underset{N\rightarrow\infty}{\rightarrow}v.$$ Also my intuition is in line with this conjecture: For growing $N$, the support of $f_{Y_{k:N}}$ shrinks to a small region and we can predict $E[Y_{k:N}|Y_{k:N}>v]$ better. Furthermore, the probability of the next value being close to $v$ is large.

However, I am missing a formal proof.
Any ideas?

  • 1
    $\begingroup$ You need to assume $X_1$ has a continuous CDF. It is not necessarily true otherwise, for example take $X_i$ Bernoulli $\{0,1\}$ and $v=1/2$. Then $E[Y_{k:n}|Y_{k:n}>1/2]=1$ for all $k, n$. $\endgroup$ – Michael May 24 '18 at 17:05
  • 1
    $\begingroup$ Here is one way to go (for the continuous case): Suppose that for all $\epsilon>0$ we can prove $\lim_{n\rightarrow\infty}P[Y_{k:n} \in (v, v+\epsilon]|Y_{k:n}>v]=1$. Can you prove $\lim_{n\rightarrow\infty} E[Y_{k:n}|Y_{k:n}>v]=v$? If so, then it remains only to prove that limit. $\endgroup$ – Michael May 24 '18 at 17:15
  • $\begingroup$ By the way, how did you simulate this in matlab? It is nontrivial. For example if you assume $X_i$ are uniform over $[0,1]$ and let $v=1/2$, when $n$ is siginificantly larger than $k$, it will take forever to randomly generate instances of $\{X_1, ..., X_n\}$ for which $Y_{k:n}>1/2$ (since that is an extremely rare event when $n$ is large). So likely you did something else. It seems easier to do the numerical integration of that PDF than to simulate. $\endgroup$ – Michael May 24 '18 at 17:25
  • 1
    $\begingroup$ You can write $E[Y|A] = E[Y|Y \leq v+\epsilon, A]P[Y\leq v+\epsilon|A] + E[Y|Y>v+\epsilon, A]P[Y>v+\epsilon|A]$. Stefan is correct that when I wrote "continuous CDF" I should have written "a distribution that gives positive probability to any positive-sized interval in $[a,b]$" which holds when $F_X(x)$ is increasing over $[a,b]$. You can modify my above Bernoulli counter-example to also work with $X$ uniform over the disjoint intervals $[0, 0.1] \cup [0.9,1]$ and that has a continuous CDF. $\endgroup$ – Michael May 25 '18 at 14:27
  • 1
    $\begingroup$ I think Stefan did a good job on this. Here is a way to proceed in my way, which may overlap some of his approaches as well. Assume $n>2k$. Let $A_i$ be the event that exactly $i$ of the random variables are larger than $v$. So then $$ P[Y_{k:n}>v\} = \cup_{i=n-(k-1)}^n A_i $$ and $$\cup_{i=n-(k-1)}^n\{ A_i \cap \{\mbox{at least $k$ are in $(v, v+\epsilon]$}\}\} \subseteq \{Y_{k:n} \in (v, v+\epsilon]\}$$ $\endgroup$ – Michael May 26 '18 at 23:09

We need to assume something. Assume $E|X| < \infty$ and $F(v)$ is increasing, such that for all $u>v$, $F(u) > F(v)$

For $u > v$ we have, $$ P(Y_{k:n} > u | Y_{k:n} > v) = \frac{P(Y_{k:n}>u)}{P(Y_{k:n}>v)}. $$

Now $P(Y_{k:n}>x)$ is asking for the probability that out of $n$ tries at most $k-1$ of the $X_i$ is below or equal to $x$. So if $N_{n,x} \in Bin(F(x),n)$ (binomial distributed) we have, $$ P(Y_{k:n}>x) = P(N_{n,x} < k). $$ Now this probability is decreasing in $x$ and it is not hard to see that we can write for a fixed $k$, $$ P(N_{n,x} < k) = C(x,n)n^{k-1}(1-F(x))^{n-k}, $$ with $C(x,n)<C_1$ and $C(v,n)>C_0$ if $F(v) > 0$, Hence, $$ \frac{P(Y_{k:n}>u)}{P(Y_{k:n}>v)} = \frac{P(N_{n,u}<k)}{P(N_{n,v}<k)}=\frac{C(u,n)n^{k-1}(1-F(u))^{n-k+1}}{C(v,n)n^{k-1}(1-F(v))^{n-k+1}}=\frac{C(u,n)}{C(v,n)}p^{n-k+1} < \frac{C_1}{C_0}p^{n-k+1}, $$ if $F(v) > 0$, with $0\leq p <1$ due to the fact that $F(v)$ is monotonically increasing at $v$. Hence, this goes to zero as $n$ goes to infinity. If $F(v)=0$, then we note, $E(Y_{k:n}|Y_{k:n}>v)=E(Y_{k:n})$ and it enough to observe that still we have $C(x,n)<C_1$ and $$ P(Y_{k:n}>u) = P(N_{n,u}<k) = C(u,n)n^{k-1}(1-F(u))^{n-k+1} < C_1 n^{k-1} p^{n-k+1} $$ Again with $0\leq p <1$ due to the fact that $F(v)$ is increasing at $v$. Again, because the geometric decrease is faster than the polynomial increase in $n^{k-1}$ this goes to zero as $n$ goes to infinity.

This shows the most probability mass lies at $v$ so expectation over any finite region above an $u$ will have a value that goes to zero and because of $E|X|$ is finite, the tail goes to zero and we are left with essentially a delta measure on $v$ and the expectation is indeed $v$.

  • $\begingroup$ Thanks for your answer. I am not sure, how you come to to the representation of $P(N_{n,x}<k)$ as a product of constants and polynomials. I think $k(n)$ does not behave like a polynomial but grows larger as it involves factorials. Could you please elaborate on that? I tried rewriting $\sum_{j=0}^{k-1}\binom{n}{j}F(x)^j[1-F(x)]^{n-j}$ into the form you proposed, but I can't see the polynomial part. Furthermore, I think it should be $[1-F(x)]^{n-k-1}$ in the representation, as we are only summing up to $k-1$. What do you think? $\endgroup$ – MathProb May 25 '18 at 9:31
  • $\begingroup$ Yes it is k-1, and n - (k - 1) = n - k + 1 else we sum up to k+1. note that $\binom{n}{k}=n(n-1) \cdots (n-k+2) / k!$ which is a polynomial (actually k is $n^{k-1}$) $\endgroup$ – Stefan May 25 '18 at 10:03
  • $\begingroup$ oops the expansion is to (n-k+1) and not (n-k+2) and I replaced $k(n)$ with $n^{k-1}$. $\endgroup$ – Stefan May 25 '18 at 10:10
  • $\begingroup$ In the sum of probabilities the powers of $(1-F)$ is $n,n-1,\ldots ,n-k+1$ you don't want to divide by $1-F$ so the best common factor is $n-k+1$ $\endgroup$ – Stefan May 25 '18 at 10:19
  • 1
    $\begingroup$ consider the n part in the sum, the first term has 1, the second one is $n$, the third one is a poynomial of the second order etc. the highest order is $n^{k-1}$ bringing that out that, the factors goes to zero or is bounded below and above (the last term) this is all bounded by above F and (1-F) are all below 1 and hence any power is below 1 and we get an upper bound. For the lower bound the last term is independant of $1-F$ and $F(u)>F(v)>0$ do you follow? $\endgroup$ – Stefan May 25 '18 at 13:15

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.