Skip to main content
deleted 4 characters in body; edited title
Source Link
MR_BD
  • 550
  • 5
  • 18

Simple proof for sampling Why sum of samples without replacement concentrationis more concentrated than with replacement?

Set $n\le N$.

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

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

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

Simple proof for sampling without replacement concentration

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  ?

Why sum of samples without replacement is more concentrated than with replacement?

Set $n\le N$.

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

In addition, let ${y_1,...,y_n}$ be an $n-$subset of $[N]$ that is chosen uniformly random among all $N \choose n$ possibilities.

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

Source Link
MR_BD
  • 550
  • 5
  • 18

Simple proof for sampling without replacement concentration

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 ?