5
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Can one show that the $y_1,\dots,y_n$ are negatively associated random variables? Then since the marginals are the same, it would imply that any Chernoff-type bound that applies to the x's also applies to the y's. $\endgroup$
    – usul
    Commented Feb 26 at 3:39

2 Answers 2

Reset to default
7
$\begingroup$

the variance of $Y$ is smaller than the variance of $X$ by a factor $\sqrt{1-\frac{n-1}{N-1}}$; for a derivation, see for example section 1.2 of these notes.

Improve this answer
$\endgroup$
1
  • $\begingroup$ In this case does this mean that I can apply concentration inequalities for with replacement (like chernoff bounds) for the case without replacement, just based on the variance inequality? I know that in "Probability Inequalities for Sums of Bounded Random Variables" Theorem 4 Hoeffding proved that you can use them but the proof was not based on the variance inequality. $\endgroup$
    – Dotman
    Commented Nov 17, 2023 at 11:23
3
$\begingroup$

Another way to measure the concentration is through the rate function, which is larger for $Y$ than for $X$. See Section 7.2 of Dembo-Zeitouni "Large Deviations Techniques and Applications".

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .