# Probability distribution of $X_N$, $N = min\{n \geq 2: X_n =$ second largest of $X_1, \ldots, X_n\}$

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)$.

• Are you alright ? – Gabriel Romon Feb 16 '17 at 18:24
• Shouldn't the last equation have $F(y)^{n-2}$ instead of $F(y)^{n-1}$? – 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,

• 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. – tlonuqbar Oct 5 '13 at 18:03
• @tlonuqbar : I edited my answer ; not surprisingly the result is still the same, but I corrected the proof. – Patrick Da Silva Oct 5 '13 at 22:26