30
$\begingroup$

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?

$\endgroup$
1
  • 7
    $\begingroup$ I would start with the same problem, but bounds 1-2. $\endgroup$
    – usul
    Commented Aug 23, 2022 at 23:52

10 Answers 10

36
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I understand $E[XY]=\rho \sigma_x \sigma_y + E[X]E[Y]$. However, I don't think $\rho$ is the only changing variable here. $E[Y]$ and $\sigma_y$ should be different. How do we tackle this? $\endgroup$
    – user334639
    Commented Aug 23, 2022 at 3:31
  • $\begingroup$ The expectation is unchanged and the value of the $\sigma$'s is not required; you only need focus on the sign. See my edit, which goes into more detail. $\endgroup$
    – Glen_b
    Commented Aug 23, 2022 at 4:56
  • 1
    $\begingroup$ @user334639 see my answer below that EX = EY, so indeed as Glen_b points out you only need to consider the covariance. $\endgroup$
    – bdeonovic
    Commented Aug 23, 2022 at 21:03
25
$\begingroup$

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)
$\endgroup$
3
  • 1
    $\begingroup$ Your "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" answers the question in itself $\endgroup$
    – Henry
    Commented Aug 24, 2022 at 17:12
  • $\begingroup$ I have a feeling that when considering the diagonal, somehow the rearrangement inequality can be applied here. $\endgroup$
    – qwr
    Commented Aug 24, 2022 at 18:52
  • $\begingroup$ @qwr possibly, but the number of terms is not the same on both sides of the inequality. $\endgroup$ Commented Aug 24, 2022 at 18:59
20
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ +1 for reasoning that is more likely intuitive so others can understand while also applying to many variations of the problem. $\endgroup$
    – Nij
    Commented Aug 24, 2022 at 6:29
9
$\begingroup$

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')

enter image description here

$\endgroup$
1
  • 3
    $\begingroup$ You could also run this for vals = 1:3 to better understand things. $\endgroup$
    – Eoin
    Commented Aug 23, 2022 at 9:09
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ (2) is incorrect without suitable qualifications. First, exactly how does one "increase the variance"? Second, consider distributions that have negative support. $\endgroup$
    – whuber
    Commented Aug 24, 2022 at 15:41
  • $\begingroup$ @whuber Translations are irrelevant. $\endgroup$ Commented Aug 25, 2022 at 0:21
  • $\begingroup$ @Accumulation That's erroneous, because they are relevant to translations (#1) and does not explain the mechanism in #2 whereby somehow variances are "increased." $\endgroup$
    – whuber
    Commented Aug 25, 2022 at 13:30
3
$\begingroup$

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

Figure showing the three events in the (j, k) plane

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

$\endgroup$
6
  • $\begingroup$ $$0 \le E[(X - \overline{X})^2] = \operatorname{Var}(X) = E[X^2] - E[X]^2$$ this is different from Glen_B's point. He uses the rule $$E[XY] = E[X]E[Y] + \text{Cov}(X,Y)$$ which is a more general situation. When $X=Y$ then you get the $$E[X^2] = E[X]^2+ \text{Var}(X)$$ but in Glen_B's answer he doesn't use it like in that second equation. $\endgroup$ Commented Aug 24, 2022 at 17:13
  • $\begingroup$ @Sextus Because covariances are variances, there is no difference in generality. I am pleased, though, that you appear to view my approach as being different from Glen_b's. $\endgroup$
    – whuber
    Commented Aug 24, 2022 at 17:25
  • $\begingroup$ I see variance as being applied to a single variable $X$ as in $\text{Var}(X)$ and covariance as being applied to two variables $X$, $Y$ as in $\text{Cov}(X,Y)$. In the approach with $\text{Var}(X)$ we look at the diagonal of squares as a variance, and this only works when $X$ and $Y$ are identical. $\endgroup$ Commented Aug 24, 2022 at 17:27
  • $\begingroup$ @Sextus stats.stackexchange.com/a/142472/919 explains my perspective. $\endgroup$
    – whuber
    Commented Aug 24, 2022 at 17:33
  • $\begingroup$ I believe that the covariance trick from Glen_B relates more to the answer by Eoin. $$\text{Cov}(X,Y) = P(X=x) \cdot x \cdot E[Y|X=x]$$ You get that in the case of 'without replacement' that the values of $E[Y|X=x]$ will shift a bit. The shift is equal and opposite for large and low values of $x$ ,but that symmetry breaks due to a multiplication by $x$ $\endgroup$ Commented Aug 24, 2022 at 18:43
2
$\begingroup$

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*} $$

$\endgroup$
3
  • 3
    $\begingroup$ You can also reason intuitively that you should get $E[X] = E[Y]$ because of the symmetry of the problem. If somebody would switch the variables $X$ and $Y$ then the distribution remains unchanged as the outcome $x,y$ has equal probability as the outcome $y,x$. $\endgroup$ Commented Aug 23, 2022 at 23:36
  • $\begingroup$ under what conditions does this hold? Is uniform distribution the only possibility? $\endgroup$
    – bdeonovic
    Commented Aug 24, 2022 at 18:13
  • $\begingroup$ ah, that intuition is dangerous because the symmetry breaks indeed when the distribution is not uniform. It is already clear with a Bernoulli variable when $p\neq 0.5$ then 'head, tails' and 'tails, heads' do not have equal probability. $\endgroup$ Commented Aug 24, 2022 at 19:25
2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ This inductive argument might be simplified by using it to proof the lemma $$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$$ And use that in the comparison of $$\frac{1}{n^2} \sum_{i,j = 1}^n ij = \frac{(n+1)^2}{4}$$ and $$\frac{1}{n(n-1)} \sum_{i,j = 1 \\ i\neq j}^n ij = \frac{1}{n(n-1)} \left( \sum_{i,j = 1}^n ij - \sum_{k=1}^n k^2 \right)= \frac{1}{n-1}\left(\frac{(n+1)^2 n}{4} - \frac{(n+1)(2n+1)}{6}\right)$$ $\endgroup$ Commented Aug 26, 2022 at 9:07
1
$\begingroup$

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

$\endgroup$
2
  • 6
    $\begingroup$ This answer is clever but won't get you the job. One would need to be able to read between the lines that a 'pick' means a random draw. $\endgroup$ Commented Aug 24, 2022 at 14:30
  • 1
    $\begingroup$ And assumed uniform random pick. If the pick wasn't uniformly random that could really complicate any easy answer. $\endgroup$
    – qwr
    Commented Aug 24, 2022 at 21:40
0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.