Let $s = \{x_1, x_2, \ldots, x_n\}$ be a set of $n$ random non-negative integers where $\sum_i x_i = n$. And let $\{y_1, y_2, \ldots, y_{\sqrt{n}}\}$ denote a subset of size $\sqrt{n}$ of $s$, chosen uniformly at random. Defining $y$ to be $\sum_i y_i$ I am interested in calculating the value of $y$.

By linearity of expectation, I know $E[y] = \sum_i E[y_i] = \sqrt{n}$. But can I prove with high probability that $y$ is close to its mean?

I tried using Chernoff bound but unfortunately since $x_i$'s and therefore $y_i$'s are not independent, I can't apply it here.

I also tried using Chebyshev's inequality since $y_i$'s seem to be negatively correlated but I can't calculate the variance of $y_i$ and the proof would be messy even if I do.

Does anyone have any idea for a simpler proof?

  • $\begingroup$ Welcome to CS.SE! Are the $y_i$'s chosen with replacement? (or without replacement?) The $y_i$'s are independent conditioned on the $x_i$'s, if they're chosen with replacement. $\endgroup$
    – D.W.
    Mar 12, 2017 at 23:42
  • $\begingroup$ @D.W. Thanks! Actually the $y_i$'s are chosen without replacement. That is, the subset $\{y_i\}_i$ is chosen uniformly at random from all subsets of size $\sqrt{n}$ of $s$. So that does not really help here. $\endgroup$
    – Soheil
    Mar 16, 2017 at 5:01

1 Answer 1


You can bound the variance as follows. Let $b_i$ be an indicator variable signaling that $x_i$ was chosen. You are interested in $y = \sum_i b_i x_i$. We have $$ \mathbb{E}[(b_ix_i)^2] = \frac{x_i^2}{\sqrt{n}}, \quad \mathbb{E}[b_ix_i\cdot b_jx_j] = \frac{\sqrt{n}(\sqrt{n}-1)}{n(n-1)}x_ix_j = (1-O(1/\sqrt{n}))\frac{x_ix_j}{n}. $$ Therefore $$ \mathbb{E}[y^2]=\sum_i \frac{x_i^2}{\sqrt{n}}+\frac{1-O(1/\sqrt{n})}{n}\sum_{i \neq j} x_ix_j \leq \frac{(x_1+\cdots+x_n)^2}{n} + \frac{\sum_i x_i^2}{\sqrt{n}}. $$ This shows that $$ \mathbb{V}[y] \leq n + \frac{\sum_i x_i^2}{\sqrt{n}} - (\sqrt{n})^2 = \frac{\sum_i x_i^2}{\sqrt{n}}. $$ The error in this estimate is quite small. The quantity $\sum_i x_i^2$ is maximized when $x_i = n$ for some $i$, and we conclude that $\mathbb{V}[y] \leq n^{3/2}$. This is of course not very helpful, if you are trying to use Chebyshev's inequality!

A cheap way out is to "filter out" all elements which are at least, say, $n^{1/2+\epsilon}$. There are at most $n^{1/2-\epsilon}$ of these, and so it is very likely that the sample contains none of them. This allows us to essentially assume that all $x_i$ are at most $n^{1/2+\epsilon}$, and so $$\sum_i x_i^2 \leq \left(\sum_i x_i\right) \max_i x_i \leq n^{3/2+\epsilon}.$$ This shows that the "effective" variance is at most $n^{1+\epsilon}$, and so with high probability the deviation from the mean is at most, say, $n^{1/2+2\epsilon}$.

You can probably get better bounds with improved technology, but this bound is already pretty reasonable. When $x_1 = n$, you are always within distance at least $\sqrt{n}$ from the mean.

  • $\begingroup$ Thanks for your quick response Yuval. I can't upvote your answer now, but will do when I can. $\endgroup$
    – Soheil
    Mar 12, 2017 at 22:07

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.