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?

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.

*

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


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


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