GATE CS 2006 Q18 — Probability: Random Variables and Distributions

Let $Y$ be the random variable representing the smallest number in the selected sample $S$.

The elements of the set $X$ are $X_i = 2^i$ for $i = 1, 2, \dots, n$. That is, $X = \{2^1, 2^2, \dots, 2^n\}$.

Since each element $X_i$ is chosen independently with probability $P_i = \frac{1}{2}$:

• The smallest element in $S$ is $2^1$ if $X_1 \in S$. This occurs with probability: $$\text{P}(Y = 2^1) = \frac{1}{2}$$
• The smallest element in $S$ is $2^2$ if $X_1 \notin S$ and $X_2 \in S$. This occurs with probability: $$\text{P}(Y = 2^2) = \left(1 - \frac{1}{2}\right) \cdot \frac{1}{2} = \left(\frac{1}{2}\right)^2$$
• In general, the smallest element in $S$ is $2^i$ if $X_1, X_2, \dots, X_{i-1} \notin S$ and $X_i \in S$. This occurs with probability: $$\text{P}(Y = 2^i) = \left(\frac{1}{2}\right)^{i-1} \cdot \frac{1}{2} = \left(\frac{1}{2}\right)^i$$
• If the sample $S$ is empty (which happens when no elements are selected, with probability $\left(\frac{1}{2}\right)^n$), the value of the smallest element is $0$.

Now, we calculate the expected value of $Y$:

Thus, the expected value of the smallest number in the sample $S$ is $n$.