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
    Feb 26 at 3:39

2 Answers 2

Reset to default
6
$\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
    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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.