We are given a set X = {x_1, ..., x_n}, where x_i = 2^i. A sample S ⊆ X is…
2006
We are given a set X = {x_1, ..., x_n}, where x_i = 2^i. A sample S ⊆ X is drawn by selecting each x_i independently with probability p_i = 1/2. The expected value of the smallest number in sample S is:
- A.
1/n
- B.
2
- C.
sqrt(n)
- D.
n
Show answer & explanation
Correct answer: D
We are given X = {2^1, 2^2, ..., 2^n} and each element is included independently with probability 1/2.
Key observation: For k = 1,...,n, the event that the smallest selected element equals 2^k occurs exactly when 2^k is selected and all smaller elements 2^1,...,2^{k-1} are not selected. The probability of that event is (1/2)^k.
For each k, P(min = 2^k) = (1/2)^k and the contribution to the expected minimum is 2^k * (1/2)^k = 1.
Summing contributions for k = 1 to n gives sum_{k=1}^n 1 = n.
Convention note: If the sample is empty we take the minimum to be 0; with that convention the unconditional expected minimum is n. If instead you condition on the sample being non-empty, then normalize the probabilities by 1 - 2^{-n} and the expected minimum becomes n/(1-2^{-n}).
Final answer: n (unconditional, with minimum = 0 when empty).