What is the probability that the max of $n$ numbers from some distribution is a greater than another number from the same distribution?

Independently choose $n$ numbers $X_1, X_2, \ldots, X_n$ from some distribution. And Independently choose another number $X_{n+1}$ from the same distribution. Let $P(\max(X_1, X_2, \ldots,,X_n) > X_{n+1}))$ means the probability that the maximum of $X_1, X_2, \ldots, X_n$ is bigger than $X_{n+1}$. What is $P(\max(X_1, X_2, \ldots,X_n) > X_{n+1}))$? I think that $P(\max(X_1, X_2, \ldots,X_n) > X_{n+1})) = \frac{n}{n+1}$. Here is my proof.

The case that any one of $X_1, X_2, \ldots X_n, X_{n+1}$ is the maximum is symmetric. So $P(X_i\text{ is the maximum)} = \frac{1}{n+1}, (i = 1,\ldots,n+1)$.

$P(\max(X_1, X_2, \ldots,X_n) > X_{n+1})) = P(X_i \text{ is the maximum}, i =1,\ldots,n)= \sum_{i=1}^{n}P(X_i \text{ is the maximum}) = n \cdot \frac{1}{n+1} = \frac{n}{n+1}$

But I think that my proof is not rigorous. https://math.stackexchange.com/a/20841/16625 gives a rigorous proof for the $n=1$ case. Can anyone give a rigorous proof for the general case?

• You should get $\frac{n}{n+1}$. $\frac{1}{n+1}$ is the probability that $\max(X_i)<X_{n+1}$. – Thomas Andrews Jan 20 '16 at 3:53
• This only works for continuous random variables, of course. For instance, if the $X_i$ are die rolls, you will get a very different result. – Thomas Andrews Jan 20 '16 at 3:58
• @ThomasAndrews Yes. For discrete random variables, the case that random variables are equal can not be ignored. – Jingguo Yao Jan 21 '16 at 7:21

Probably easier to compute the probability that the max is less. Specifically, $P(\max(X_i)<x)=P(X<x)^n$. So if $p$ is the CDF for $X$ then the probability is:

$$\int p(x)^n\,dp(x) = \frac{1}{n+1}p(x)^{n+1}\Bigg{|}_{-\infty}^{\infty}=\frac{1}{n+1}$$

This is sort of obvious - the probability that the last one is the largest is the same as the probability that any other is the largest. (If the pdf is discontinuous, it is possible, with non-zero probability, for two to be equal, of course. So we assume continuous.)

So the probability that you were seeking is $\frac{n}{n+1}$.

Here is a slightly more formal argument. Suppose $X_1, X_2, \ldots,$ are independent and identically distributed random variables. Then the maximum order statistic $X_{(n)}$ of a sample of size $n$ has CDF $$F_{X_{(n)}}(x) = \Pr[X_{(n)} \le x] = \prod_{i=1}^n \Pr[X_i \le x] = F_X(x)^n.$$ Suppose we are now interested in the random variable $Y = X_{(n)} - X_{n+1}$, and in particular, $$\Pr[Y > 0] = 1 - \Pr[Y \le 0] = 1- \int_{x = -\infty}^\infty F_{X_{(n)}}(x) f_X(x) \, dx = 1 - \int_{x = -\infty}^\infty F_X(x)^n f_X(x) \, dx.$$ With the substitution $$u = F_X(x), \quad du = f_X(x) \, dx, \quad F_X(-\infty) = 0, \quad F_X(\infty) = 1,$$ we arrive at $$\Pr[Y > 0] = 1 - \int_{u=0}^1 u^n \, du = 1 - \frac{1}{1+n} = \frac{n}{n+1},$$ as claimed.

Assuming that the $P(X_i=X_j)=0$ for $i\ne j$, $$P(\max(X_1,X_2,\dots,X_n)\gt X_{n+1})$$ is the probability that $X_{n+1}$ is not the greatest of the $n+1$ samples. The probability that it is the greatest of $n+1$ samples is $$P(\max(X_1,X_2,\dots,X_n)\le X_{n+1})=\frac{n!}{(n+1)!}=\frac1{n+1}$$ because there are $n!$ arrangements where $X_{n+1}$ is greatest and $(n+1)!$ arrangements altogether.

Therefore, $$P(\max(X_1,X_2,\dots,X_n)\gt X_{n+1})=1-\frac1{n+1}=\frac n{n+1}$$

Your argument is correct if the $n+1$ observations are independent, an assumption that you did not state.