Expectation of minimum of two random numbers

Question

Let's assume we picked chose two numbers in the range $[1,n]$ where $n\in \mathbb N$ independently, such that each one of them is distributed randomly.

How can I find the expectation of the minimum of these two numbers?

I know that we have $2n-1$ possibilities of getting $1$ as minimum, $2(n-1)-1$ possibilities of getting $2$ as minimum, and so on!

But how do I formalize this and calculate the expectation?

Answer 1

For $1 \le k \le n$, let $p_k$ be the probability that the minimum of the two numbers is $k$, and let $e$ be the expected minimum value. \begin{align*} \text{Then}\;\;p_k &= 2 \left( {\small{\frac{1}{n}}} \right) \left( {\small{\frac{n-k+1}{n}}} \right) - {\small{\frac{1}{n^2}}} \\[6pt] &=\frac{2n-2k+1}{n^2}\\[8pt] \text{Hence}\;\;e &=\sum_{k=1}^n kp_k\\[4pt] &=\sum_{k=1}^n k\left(\frac{2n-2k+1}{n^2}\right)\\[4pt] &=\frac{1}{n^2}\left(\sum_{k=1}^n k(2n-2k+1)\right)\\[4pt] &=\frac{1}{n^2}\left(\sum_{k=1}^n (2n+1)k-2k^2)\right)\\[4pt] &=\frac{1}{n^2}\left(\left(\sum_{k=1}^n (2n+1)k\right)-\left(\sum_{k=1}^n 2k^2)\right)\right)\\[4pt] &=\frac{1}{n^2}\left( \left((2n+1)\sum_{k=1}^n k\right) - \left(2\sum_{k=1}^n k^2)\right) \right)\\[4pt] &=\frac{1}{n^2} \left( (2n+1) \left({\small{\frac{n(n+1)}{2}}}\right) -2 \left({\small{\frac{n(n+1)(2n+1)}{6}}}\right) \right) \\[4pt] &=\frac{(n+1)(2n+1)}{6n}\\[4pt] \end{align*}

Answer 2

There is a simple but extremely useful fact:

Fact For a non-negative integer-valued random variable $Z$, $$ \mathrm{E}[Z] = \sum_{k\ge 1} \mathrm{P}(Z\ge k). $$

That said, for iid $X,Y$ $$ \mathrm{E}[\min(X,Y)] = \sum_{k\ge 1} \mathrm{P}(\min(X,Y)\ge k) = \sum_{k\ge 1} \mathrm{P}(X\ge k,Y\ge k) \\ = \sum_{k\ge 1} \mathrm{P}(X\ge k)\mathrm{P}(Y\ge k) = \sum_{k\ge 1} \mathrm{P}(X\ge k)^2. $$ In particular, if the distribution is uniform on $\{1,\dots,n\}$, then $$ \mathrm{E}[\min(X,Y)] = \sum_{k= 1}^n \mathrm{P}(X\ge k)^2 = \sum_{k= 1}^n \frac{(n-k+1)^2}{n^2} = \frac1{n^2}\sum_{j= 1}^n j^2 \\ = \frac{n(n+1)(2n+1)}{6n^2} = \frac{(n+1)(2n+1)}{6n}. $$

Exercise. Compute $\mathrm{E}[\min(X_1,X_2,X_2)]$, where $X_1,X_2,X_3$ are iid uniform on $\{1,\dots,n\}$.