Sample two numbers from 1 to 10; maximize the expected product

Question

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?

Answer 1

Hint: Note the relationship between $E[XY]$ and the covariance. Now think about the sign of the covariance - or if you prefer it in those terms, the sign of the correlation will work - under the two sampling schemes (it's zero under one but clearly not under the other, noting that we're here taking $X$ and $Y$ as the values on the two draws). The solution to maximizing $E[XY]$ is immediate.

This sounds like the sort of thing one might encounter in one of those interviews where they try to ask you some odd question and see what you do with it -- there's typically a shortcut that avoids explicit calculation; this one definitely has a shortcut. Realizing the connection between $E[XY]$ and $\text{Cov}[XY]$ and then the connection to the two sampling methods, one should be able to answer it in a matter of seconds, and justify it.

---

It seems further explanation may be helpful. These are the ideas involved.

1. Unconditional expectations are unchanged whether you use with replacement or without replacement. That is $E[Y]=E[X]$* under both schemes.

2. If you sample without replacement, the covariance must be negative because when you take a value below the population mean there's now more values available above the population mean than below it for the second draw, and vice versa. That is, the second value is more likely to be the opposite side of the mean from the first value than on the same side in a way that will make the covariance negative for this case.

3. $E[XY] = E[X]E[Y]+\text{Cov}[X,Y]$

   With replacement, covariance is 0 and $E[XY]=E[X]E[Y]$

   Without replacement, covariance is <0 and $E[XY] < E[X]E[Y]$

---

* If this doesn't seem obvious, consider the following thought experiment: I take a deck of cards numbered 1 to 10 and thoroughly shuffle them, placing the deck face down on the table. Person A will take the first card and person B the second card. But now person B asks that we extend the shuffling a little further and interchange the positions of the top two cards. Clearly that last step doesn't change the distributions experienced by A and B (the additional mixing step doesn't make it any less random). So B must experience the same distribution under both schemes, and thereby B has the same (unconditional) distribution as A does -- it doesn't matter if you take the first card or the second card. Plainly, then, $E[Y]=E[X]$.

(Naturally, however, if B observes what A got before drawing, B's conditional distribution and hence the conditional expectation $E[Y|X=x]$ is impacted by the specific value of $x$. This is not the situation we're dealing with, since we were trying to find the unconditional expectation $E[Y]$.)

Answer 2

If you don't get to the smart covariance trick by Glen B, then you could also consider the following approach which is one level of abstraction lower

• Step 1: consider computing the hard way by adding all 10 by 10 terms from a table $$\frac{1}{100}\sum_{x_1=1}^{10}\sum_{x_2=1}^{10} x_1 \cdot x_2 = E[X]^2 = 5.5^2$$

  $$\begin{array}{cccccccccc} 1&2&3&4&5&6&7&8&9&10\\ 2&4&6&8&10&12&14&16&18&20\\ 3&6&9&12&15&18&21&24&27&30\\ 4&8&12&16&20&24&28&32&36&40\\ 5&10&15&20&25&30&35&40&45&50\\ 6&12&18&24&30&36&42&48&54&60\\ 7&14&21&28&35&42&49&56&63&70\\ 8&16&24&32&40&48&56&64&72&80\\ 9&18&27&36&45&54&63&72&81&90\\ 10&20&30&40&50&60&70&80&90&100 \end{array}$$

• Step 2: without replacement you get a similar sum but without the terms where $x_1=x_2$.

  $$\begin{array}{cccccccccc} &2&3&4&5&6&7&8&9&10\\ 2&&6&8&10&12&14&16&18&20\\ 3&6&&12&15&18&21&24&27&30\\ 4&8&12&&20&24&28&32&36&40\\ 5&10&15&20&&30&35&40&45&50\\ 6&12&18&24&30&&42&48&54&60\\ 7&14&21&28&35&42&&56&63&70\\ 8&16&24&32&40&48&56&&72&80\\ 9&18&27&36&45&54&63&72&&90\\ 10&20&30&40&50&60&70&80&90& \end{array}$$

  Then a trick to answer the question is to analyse only the difference in this diagonal with the average of the previous step. The question is whether the average of this diagonal $E[X^2]$ is lower or smaller than $E[X]^2 = 5.5^2$. Since $E[X^2] = E[X]^2 + VAR[X] > E[X]^2$ you get that the diagonal has a more than average contribution and leaving it out would reduce the expectation of the outcome (thus you get the higher result when you use replacement, and leave the diagonal in the draw).

Here is a simple way to compute it with brute force in R

n = 10
generate a matrix of the outer product
M = outer(1:n,1:n, FUN = "*")
make a second matrix but with the diagonal zero
M2 = M
diag(M2) = NA
with replacement 30.25
mean(M)
without replacement (no diagonal) 29.3333
mean(M2, na.rm = TRUE)

Answer 3

Here is an intuitive approach to the problem. Suppose the first number we pick is a 1 - we'd obviously be better off picking the second number without replacement, in order to eliminate the chance of getting another 1. Suppose the first number we pick is a 10 - we'd obviously be better off picking the second number with replacement, to allow for the possibility of getting another 10. You can extend this logic to see that if we pick a number above the average of 5.5, we would prefer to pick with replacement, but if we pick below the average, we would prefer to pick without replacement.

There are 5 numbers above average and 5 below, so an equal number of instances where we'd prefer one strategy versus the other, all of which are equiprobable. But the difference is in the value of the potential product. If the first number is a 1, it doesn't really matter a whole lot what the second number is, since the score is multiplied by just 1 - with replacement, the score will be between 1 and 10, instead of between 2 and 10 without. But if the first number is a 10, there is a greater impact due to the fact that it is multiplied by 10, giving us a possible score between 10 and 100 with replacement, instead of 10 to 90 without. If we adopt the "with replacement" strategy, the "gain" from getting double 10's is larger than the "loss" we get from picking double 1's. You can extend this symmetrically to see that the gain from double 9's is greater than the loss from double 2's, and so forth. We always gain more at the upper end with the "with replacement" strategy than we lose at the lower end, so the "with replacement" strategy is preferable overall.

Answer 4

If you're better at programming than maths, I believe there's a reasonably simple way to get this by brute force as well.

It provides a slightly different intuition: $E[XY]$ is higher without replacement when $X < \text{mean}(X)$, because removing a low value of $X$ increases $E[Y]$, it is lower, and by a greater amount, when $X > \text{mean}(X)$. A little thought shows that this asymmetry occurs because we're looking at the product, e.g. it wouldn't happen for $E[X + Y]$.

library(tidyverse)
vals = 1:10
Calculate E[XY|x] conditional on each possible value of X
no_replace = map_dbl(vals, function(x) mean(x * vals[vals != x])) 
with_replace = map_dbl(vals, function(x) mean(x * vals))
Take averages over X values to get E[XY]
mean(no_replace) # 29.33333
mean(with_replace) # 30.25
Plot
df = data.frame(x = vals, 
                Replacement=with_replace, 
                Without replacement=no_replace)
df %>% pivot_longer(-x) %>% 
  ggplot(aes(x, value, color = name)) + 
  geom_point() +
  geom_path() +
  geom_vline(linetype = 'dashed', xintercept = mean(vals)) +
  scale_x_continuous(breaks = vals) +
  labs(x = 'X', y = 'E[XY]', color = 'Method')

Answer 5

There are three facts that led me to the conclusion that replacement gives a higher expected value:

1. Products result in right-skewed distributions. When you multiply numbers together, you tend to get results clustered mostly in small numbers, with a few large results.
2. Among right-skewed distribution, increasing the variance tends to increase the mean. Since extremes above the median are more extreme than the extremes below it, getting more extreme increases the result on average. For instance, in the question you present, we can quickly estimate the median as being somewhere around $5\times6$ (the product of the two middle numbers). The minimum is $1\times1$, and the maximum is $10\times10$. So getting an extremely low number costs us at most $30$, while an extremely high number can give us as much as $70$ over the median.
3. Allowing replacement increases the variance. With replacement, you can get something consisting entirely of the most extreme numbers. Without replacement, you can only get one instance of the maximum and the other one can be at most second highest, and similarly for the minimum.

This isn't a rigorous proof, but understanding how asymmetry, variance, and replacement interact is important for working with statistics.

As a side note, I don't think is really game theory. If simply phrasing it as a choice between options made it game theory, then all optimization problems would be game theory (and pretty much everything can be phrased as an optimization problem).

Answer 6

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

Answer 7

I think Glen_b's answer is wonderful intuition that you need to only consider the the covariance, as the unconditional expectations are the same. Below I prove the unconditional expectations are the same (ie $EX = EY$) $$ \begin{align*} EX &= \dfrac{1}{n}\sum_{i=1}^n i = \dfrac{n(n+1)}{2n} = \dfrac{(n+1)}{2}\\ E[Y|X=j] &= \dfrac{1}{n-1}\sum_{i \in [1,n] \setminus j} i = \dfrac{1}{n-1}\left(\dfrac{n(n+1)}{2} - j\right)\\ EY &= E[EY|X]\\ &= \dfrac{1}{n}\sum_{j=1}^n \dfrac{1}{n-1}\left(\dfrac{n(n+1)}{2} - j\right)\\ &= \dfrac{n(n+1)}{2(n-1)} - \dfrac{n+1}{2(n-1)} \\ &= \dfrac{(n+1)(n-1)}{2(n-1)} \\ &= \dfrac{(n+1)}{2} \end{align*} $$

Answer 8

Don't know if this counts as simpler than doing direct computation (you have to know Gauss's formula for the sum of the first $n$ numbers), but you can prove your guess by induction on the number of randomly drawn numbers $n$ (and then, your case follows from the special case $n=10$). So, we have to prove that for each $n \in \mathbb{N}$ with $n \ge 2$ it holds that $$\frac{1}{n(n-1)}\sum_{\substack{i,j=1 \\ i\neq j}}^n i j < \frac{1}{n^2}\sum_{i,j=1}^n ij\;,$$ and since, by straightforward computations, we have that $$ \frac{1}{n^2}\sum_{i,j=1}^n ij = \frac{(n+1)^2}{4} \;, $$ everything boils down to proving that $$\frac{1}{n(n-1)}\sum_{\substack{i,j=1 \\ i\neq j}}^n i j < \frac{(n+1)^2}{4}\;.$$ The base case $n=2$ is clear. Assuming we have proven the claim for $n \in \mathbb{N}$ with $n \ge2$, we can prove that the claim is true also for $n+1$ in the following way: \begin{align*} \frac{1}{(n+1)n}\sum_{\substack{i,j=1 \\ i\neq j}}^{n+1} i j &= \frac{1}{(n+1)n}\sum_{\substack{i,j=1 \\ i\neq j}}^n ij + \frac{2}{n} \sum_{k=1}^n k = \frac{1}{(n+1)n}\sum_{\substack{i,j=1 \\ i\neq j}}^n ij + (n+1) \\ &= \frac{n-1}{n+1} \frac{1}{n(n-1)}\sum_{\substack{i,j=1 \\ i\neq j}}^n ij + (n+1) \\ &< \frac{n-1}{n+1} \frac{(n+1)^2}{4} + (n+1) = \frac{(n+1)(n+3)}{4} < \frac{(n+2)^2}{4} \;, \end{align*} where the first inequality follows by the induction hypothesis and the second one by the fact that the square is among the rectangles of a given perimeter the one that has the largest area.

As a side effect, note that as a corollary of previous result, we can recycle the previous proof to prove the stronger claim that, for each $n \in \mathbb{N}$ such that $n \ge 2$, we have $$ \frac{1}{n(n-1)}\sum_{\substack{i,j=1 \\ i\neq j}}^n i j \le \frac{n(n+2)}{4} \;,$$ with strict inequality as long as $n \ge 3$ (base case $n =2$ by direct computation, and then the same proof as before ending just before the last inequality).

Answer 9

I would pick 10 twice, this results in 100 which is the largest possible product of two numbers between 1 and 10.

Answer 10

There are two states: pick new number or not. In replacement there are four choices and without replacement there are three:$(0, 0), (0, 1), (1, 0)$. The probability of the last two is $\frac{1\cdot(n-1)}{n(n-1)}$ and the expected value is $n\frac{n-1+1}{2}$. Multiplying and simplifying gives $n/2$. Let $e_n$ be the replacement expectation and $r_n$ the expectation without replacement: $$ r_n = \frac{(n-1)(n-2)}{n(n-1)} r_{n-1} + 2\frac{n}{2} = (1 - \frac{2}{n}) r_{n-1} + n $$ so $r_n = \frac{1}{12} (n + 1) (3n + 2)$. Since $e_n = \frac{(n+1)^2}{4}$, $$ e_n - r_n = \frac{n^2 + 2n + 1}{4} - \frac{n^2}{4} -\frac{5n}{12} - \frac{1}{6} = \frac{n+1}{12}>0. $$