Simple proof for sampling without replacement concentration.

628 Views Asked by At

Set $n\le N$.

Suppose $x_1,...,x_n$ are uniformly random variables taking value in $[N]$

In addition Suppose ${y_1,...,y_n}$ are an $n-$subset of $[N]$ has been chosen uniformly random among all $N \choose n$ possibilities.

Is there any simple proof that shows $Y=\sum y_i$ is more tightly concentrated than $X=\sum x_i$ around their shared mean ?