How could I find the expected value of the sum of the elements of a subset of $\{1,2,\ldots,n\}$ given that the elements must be distinct and the subset must be of size $k$, selected at random with $k<n$, with all integers in $\{1,2,\ldots,n\}$ having equal probability of being chosen.
[Math] Expected Value of sum of distinct random integers
expectationprobability
Best Answer
A "different" why to see that: we can call the chosen of some number of the set as some random variable $X_i$, and we can define the random variable of the sum as
$$X=\sum_{i=1}^{k}X_i$$
Then we have that
$$\Bbb E[X]=\Bbb E\left[\sum_{i=1}^{k}X_i\right]=\sum_{i=1}^{k}\Bbb E[X_i]$$
But we have that the $X_i$ are not independent but anyway they expected value is the same because
$$\Bbb E[X_i]=\sum_{x_1,x_2,...,x_i}x_i\Pr[X_i=x_i|X_1=x_1,X_2=x_2,...,X_{i-1}=x_{i-1}]\cdot\Pr[X_1=x_1,X_2=x_2,...,X_{i-1}=x_{i-1}]$$
where
$$\Pr[X_i=x_i|X_1=x_1,X_2=x_2,...,X_{i-1}=x_{i-1}]=\begin{cases}\frac1{n-i+1}\quad&\text{if }x_i\notin\{x_1,...,x_{i-1}\}\\0\quad&\text{if }x_i\in\{x_1,...,x_{i-1}\}\end{cases}$$
and
$$\Pr[X_1=x_1,X_2=x_2,...,X_{i-1}=x_{i-1}]=\frac1{(n)_{i-1}}$$
where $(a)_b$ is a falling factorial. So for any $x_i$ value we will have a limited number of (i-1)-tuplas $(x_1,x_2,...,x_{i-1})$ where probability is not zero. The number of these (i-1)-tuplas is $(n-1)_{i-1}$.
Then we have
$$\Bbb E[X_i]=\sum_{k=1}^{n}\frac{(n-1)_{i-1}}{(n)_{i-1}}k\frac{1}{n-i+1}=\frac1n\sum_{k=1}^{n}k=\frac{n+1}{2}$$
Then finally
$$\Bbb E[X]=\sum_{j=1}^{k}\Bbb E[X_j]=k\frac{n+1}{2}$$