An urn contains n balls numbered $2^i,i=0,\dots,n-1$. Select two w/o replacement -- what is the EV of the sum of 2 balls?

Question

Problem

An urn contains n balls numbered 1, 2, 4, 8, ..., 2^(n-1) where n > 1. If a person selects 2 balls without replacement, what is the expected value of the sum of the two balls?

Solution

I have solved the case where you select 2 balls with replacement and got the answer: (2/n)(2^n - 1) (I took the sum of 2^(i-1) from i to n and multiplied it by the probability 1/n and 2 for the two balls). I am having difficulty with this version of the problem (no replacement).

For the first ball, the EV will simply be (1/n)(2^n - 1). However, what about the second ball? You could draw the lowest valued ball (1) -- wouldn't that effect the 2nd ball's EV?

Looking for guidance/tips, thanks.

Answer 1

Hint:

Let $B_1$ denote the number on the first ball and $B_2$ the number on the second ball.

Then in both cases (with and without replacement) $B_1$ and $B_2$ have equal distribution so that $\mathbb EB_1=\mathbb EB_2$ hence by linearity of expectation: $$\mathbb E(B_1+B_2)=\mathbb EB_1+\mathbb EB_2=2\mathbb EB_1$$

The difference between the cases is that $B_1$ and $B_2$ are independent by replacement and are not independent in the other case.