Given a sequence $X_1, X_2, \ldots$ of independent, continuous random variables with the same distribution function $F$ and density function $f$, let $N = min\{n \geq 2: X_n = $ second largest of $ X_1, \ldots, X_n\}$.

Denote $X_N$ as the first random variable which, at the time of observation, is the second largest of those observed so far. Find the probability density function $f_{X_N}(x)$.

I'm extremely lost on this problem; all I've come up with thus far is to look at random variables $X_M$, the maximum of all observed so far, and $X_{M-1}$, the 'second-to-maximum' but I have been unable to find their respective distribution/density functions.

Thanks in advance for any and all help.


Let $f(x)$ be the density function of the $X_i$, and $F(x)$ their cdf.

Let $Z$ be the maximum of the $X_i$. For completeness we find the distribution of $Z$, though that is likely familiar to you.

The event $Z\le z$ happens precisely if all the $X_i$ are $\le z$. This has probability $(F(z))^n$. Thus $$F_Z(z)=(F(z))^n.$$ For the density function of $Z$, differentiate. We get $f_Z(z)=nf(z)(F(z))^{n-1}$.

Let $Y$ be the second largest of the $X_i$. We give a highly informal derivation of the density function $f_Y(y)$ of $Y$.

Let $dy$ be "small." We find the probability that $Y$ lies between $y$ and $y+dy$. This will be approximately $f_Y(y)\,dy$.

Neglecting terms in higher powers of $dy$, the probability that the second largest lies between $y$ and $y+dy$ is the probability that some $X_i$ lies in this interval times the probability that $n-2$ of the $X_i$ lie below $y$ and $1$ lies above $y+dy$.

The $X_i$ that lies between $y$ and $y+dy$ can be chosen in $n$ ways. The probability it lies in the interval is approximately $F(y)\,dy$.

The probability that $n-2$ of the remaining $X_i$ lie below $y$, and $1$ lies above, is $\binom{n-1}{1}(1-F(y))^1 (F(y))^{n-2}$. "Thus," $$f_Y(y)=n\binom{n-1}{1}f(y)(1-F(y))(F(y))^{n-1}.$$ For the cdf $F_Y(y)$, integrate from $-\infty$ to $y$. The integral is in principle easy, make the substitution $u=F(y)$.

  • $\begingroup$ Are you alright ? $\endgroup$ – Gabriel Romon Feb 16 '17 at 18:24
  • 1
    $\begingroup$ Shouldn't the last equation have $F(y)^{n-2}$ instead of $F(y)^{n-1}$? $\endgroup$ – Vivek Bagaria Apr 18 '17 at 19:46

A different way to show André Nicolas' result:

Let $Y$ be the second largest $X_i$. Then $Y \le x$ if and only if there is at most one $i$ such that $X_i > x$. Let $F(x) = \mathbb{P}(X_1 \le x)$ be the distribution function of $X_1.$ Using the fact that the $X_i$ are i.i.d.: $$ \begin{align} \mathbb{P}(Y \le x) &= \mathbb{P}(\{\exists! i: X_i > x\}) + \mathbb{P}(\{\forall i: X_i \le x\})\\ &= \sum_i \mathbb{P}(X_1 \le x, \dots, X_{i-1} \le x, X_i > x, X_{i+1} \le x, \dots, X_n \le x) + \mathbb{P}(X_1 \le x, \dots, X_n \le x) \\ &= \sum_i \mathbb{P}(X_i > x) \prod_{j \neq i} \mathbb{P}(X_j \le x) + \prod_i \mathbb{P}(X_i \le x) \\ &= \sum_i (1-F(x)) F(x)^{n-1} + F(x)^n \\ &= n (1-F(x)) F(x)^{n-1} + F(x)^n. \end{align} $$

Differentiate to get the density $f_Y$.

P.S.: One can also show $\mathbb{P}(Z > x, Y \le x) = \mathbb{P}(Y \le x) - \mathbb{P}(Z \le x)$, even if the $X_i$ are not i.i.d.


What is the probability that $N = 2$? i.e. what is the probability that $X_1 > X_2$? Well since $X_1$ and $X_2$ are iid, $\mathbb P(X_1 > X_2) = \mathbb P(X_2 < X_1)$, and by continuity $\mathbb P(X_1 = X_2) = 0$. Therefore $\mathbb P(N = 2) = \mathbb P(X_1 > X_2) = 1/2$.

What is the probability that $N = 3$? If $N=3$, then in particular $N \neq 2$, so $X_1 < X_2$. But $N = 3$ means $X_3$ comes second, so we must have $X_1 < X_3 < X_2$. Since this is one of the $6$ possible configurations of $\{1,2,3\}$, $\mathbb P(N=3) = 1/6$.

What is the probability that $N=4$? Since $N \neq 2$ and $N \neq 3$, we must have $X_1 < X_2$, and we cannot have $X_1 < X_3 < X_2$, so we either have $X_3 < X_1 < X_2$ or $X_1 < X_2 < X_3$. But then $X_4$ comes in second so that leaves us with two possible permutations of $\{1,2,3,4\}$ ; $\mathbb P(N=4) = \frac 2{24} = \frac 1{12}$.

The probability that $N = k$, $k \ge 2$ will be given as follows : you consider all the possibilities $N \neq 2,3,\dots,k-1$ and then $N = k$. The steps $2,3,\dots,k-1$ will each give $1,2,\dots,k-2$ independent choices, and $N=k$ will force the position of $X_k$ to be second. You will then compute the probability of obtaining one of the $(k-2)!$ permutations of the possible orderings of $\{1,2,\dots,k\}$, i.e. $\mathbb P(N=k) = \frac{(k-2)!}{k!} = \frac 1{k(k-1)}$.

I didn't just give you the solution, I explained to you how I thought about it ; this is how you should've come up with the solution. Explore small cases, find a pattern. =D

Hope that helps,

  • $\begingroup$ I am not sure that I understand your approach - that, or you've misread OP. We can't get $X_1, X_3 < X_2 < X_4$ since at the time of observation of $X_3$, it can be the second-largest. For $N=4$, it must be that $X_4 < X_i$ for some $i$ in order to be second-largest. Edit: I do appreciate the intuition of the approach, thank you for that. $\endgroup$ – tlonuqbar Oct 5 '13 at 18:03
  • $\begingroup$ @tlonuqbar : I edited my answer ; not surprisingly the result is still the same, but I corrected the proof. $\endgroup$ – Patrick Da Silva Oct 5 '13 at 22:26

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.