Sample two numbers from 1 to 10; maximize the expected product Assume you sample two numbers, randomly drawn from 1 to 10; you could choose two strategies: 1) pick with replacement and 2) pick without replacement. Which strategy would you prefer to maximize the expected product?
I encountered this problem while preparing for an interview. My intuition is picking with replacement would be better. However, I found it too complex to use the brute-force method to prove it. Could anyone suggest a better approach?

This is a different shortcut than Glen_B's -- but of course they must be related at some level.  It all comes down to the fact that squares of numbers are non-negative.
Let there be $n$ ($10$ in this instance) objects $i_1, i_2, \ldots, i_n$ in the box bearing the numbers $x_1, x_2, \ldots, x_n,$ respectively.  Write $j$ for the index of the first object drawn and $k$ for the index of the second; and let $X_1 = x_j,$ $X_2 = x_k$ be the corresponding random values.
The expectation of the product $X_1X_2$ with replacement is easy to find because the two values $X_1$ and $X_2$ are independent and identically distributed (that's what "with replacement" means) and therefore, writing $\overline{x} = (x_1 + \cdots + x_n)/n,$
$$E[X_1X_2] = E[X_1]E[X_2] = \overline{x}^2.$$
The key idea is that the joint distribution of $(X_1,X_2)$ with replacement can be expressed as a mixture of the distribution conditional on the events $\mathcal{E}_\lt: j \lt k,$ $\mathcal{E}_\gt: j \gt k,$ and $\mathcal{E}_=: j = k.$

The conditional expectation of $X_1X_2$ for the first two events (red and blue in the figure) is the same as sampling without replacement, because in both cases the probability is uniform on the set of distinct unordered pairs $\{j, k\}.$  The conditional expectation in the third case (the white diagonal strip in the figure) is that of $X_1^2$ because $X_1 = X_2.$
Many famous inequalities -- Cauchy-Schwarz, Jensen's, etc. -- tell us that for any random variable $X,$
$$E[X^2] \ge E[X]^2$$
with equality if and only if $X$ is almost surely constant.  A statistical proof observes that the expectation of any squared random variable, such as the residual $X - \overline{X},$ cannot be negative:
$$0 \le E[(X - \overline{X})^2] = \operatorname{Var}(X) = E[X^2] - E[X]^2,$$
which is Glen_B's point of departure.
Since, when sampling with replacement, the expectation of $X_1X_2$ is the probability-weighted sum of these three conditional expectations, and one of them exceeds the without-replacement expectation, sampling with replacement has a greater expectation than sampling without replacement.
The inequality reduces to an equality if either (a) $X_1$ or (equivalently) $X_2$ is almost surely constant or (b) $\Pr(X_1 = X_2) = 0,$ which occurs only when the $X_i$ have a continuous distribution (never the case for finite $n$).
