Randomly selected subset, expected value of the sum

Question

Interesting problem I spotted while learning:

Let $X=\left\{1,..,n\right\}$. We randomly select subset of $X$ and name it $A$. Each subset if equally likely.

a) Find the expected value of the sum of elements of A.

b) Find the expected value of the sum of elements of A, on condition that it has $k$ elements.

a) I think I know how to solve a). If each subset is selected with the same probability then I think it is equivalent to selecting each element of $X$ with probability $\frac{1}{2}$. So, using indicators, we got that expected value we are looking for is $\frac{n(n+1)}{4}$. But I can't find any rigorous argument why it is equivalent to selecting each element with probability $1/2$.

b) Small observation with $k=1$ (each element selected with probability $1/n$) and $k=n$ (each element selected with probability $1$) gives me feeling that approach from a) can be used with probability $k/n$ and then the result is $\frac{k(n+1)}{2}$. But it is much less intuitive than observation in a). No idea, how to prove this. Can anyone help?

Answer 1

Regarding your first question, note that a subset has an equivalent representation as a binary sequence. For example, for $n = 4$, the subset $\{1,3\}$ can be identified with $(1,0,1,0)$. Now, picking a subset uniformly at random, is like picking a sequence uniformly at random out of the $2^n$ possibilities. You should be able to argue the rest.

Regarding your 2nd question, let $X_i$ be the indicator that the $i$ is present in the random subset (i.e., $i$-th position in the binary representation above has a $1$) Then, you want $$ E\Big[ \sum_{i=1}^n i X_i \Big| \sum_{i=1}^n X_i = k\Big] = \sum_{i=1}^n i\, E\Big[X_i \Big| \sum_j X_j = k\Big] $$ Now, you can use symmetry. Let $a_i :=E[X_i \Big| \sum_j X_j = k]$ (which is the conditional probability of choosing the $i$). Then all $a_i$ should be equal and $\sum_i a_i = k$ (why?), from which it follows that $a_i = k/n$. This give you the answer that you have, and also shows that the conditional probability of choosing the $i$ is $k/n$ for every $i$.

Answer 2

All your guesses are correct. What happens here is that you initially work on the probability space $\Omega={\cal P}(X)$, the set of all subsets of $X$.

On that probability space, you can define the random variable $V_i$, equal to $1$ if $i\in A$ and $0$ otherwise.

Denote by $E_i=\lbrace A \in \Omega | i \in A \rbrace$ and $N_i=\lbrace A \in \Omega | i \not\in A \rbrace$. Then $E_i$ and $N_i$ have the same number of elements (indeed $A \mapsto \lbrace i \rbrace \cup A$ is a bijection between $E_i$ and $N_i$) so it is equally likely that $A$ contains $i$ or not : $P(V_i=0)=P(V_i=1)=\frac{1}{2}$. This justifies your “a)”.

Answer 3

For a) you can pair each subset with its complement to show that a given element is in half the subsets, so is in the chosen subset half the time.

For b) each element has the same chance to be chosen. If you want to get $k$ of them, you need that chance to be $\frac kn$.

Good thinking on both.