0
$\begingroup$

Let $X$ be a collection of $2l$ non-negative numbers $X_1,X_2,\ldots,X_{2l}$. We draw $l$ weighted (proportional to values) samples without replacement from $X$. Let $S$ denote this set of $l$ samples. I want to prove a concentration result showing that with high probability the sum of the sampled numbers in $S$ is not small, say at least $T/2-\epsilon$ where $T$ denotes the sum of the numbers in $X$ and $\epsilon$ is a small constant.

Why I believe the concentration result should hold: Since we are doing weighted sampling with probabilities proportional to the values, the resulting sum of the samples should not be small compared to the sum of the population.

What I tried: I saw that Hoeffding's result for sampling without replacement implies a concentration bound for the sum without replacement using a concentration for the sum with replacement. This result in my opinion can be used to prove a concentration result that the sum of the sampled numbers cannot be too large. But, here I am more interested in proving concentration for the lower bound on the sum, that is the sum is not small.

Thanks

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You need some more strict conditions to get small bounds on the lower tail. For example, if one of the numbers is greater than the sum of all the others, then the probability of the sample sum being smaller than $T/2$ is 1/2. $\endgroup$
    – Brendan McKay
    Commented Jan 4 at 13:47
  • $\begingroup$ @Brendan They are "weighted (proportional to values) samples". So the large number would be drawn on the first step with probability greater than $1/2$. $\endgroup$
    – James Martin
    Commented Jan 5 at 12:18
  • $\begingroup$ "High probability" of exceeding $T/2$ is still too much to ask for in the general case, though. Consider for example the case where $X_1=1+\epsilon$ and $X_2=X_3=\dots=X_{2l}=1$. By choosing $\epsilon$ small, you can make the probability of exceeding $T/2$ arbitrarily close to $1/2$. $\endgroup$
    – James Martin
    Commented Jan 5 at 12:25
  • $\begingroup$ @James:Thanks, you are right, probability of exceeding T/2 might be very close to 1/2. I was not very clear about the bound I want to prove for the sampled sum. I want to show that sum cannot be much smaller than T/2, say $T/2-\epsilon$ with high probability. The problem I am facing is that since $X_i$s can be large, $0\leq X_i\leq T$ for all $i$, bounded differences inequalities do not seem to give much. Suggestions or pointers are welcome. $\endgroup$
    – Sankhya
    Commented Jan 5 at 12:54

0

Reset to default

You must log in to answer this question.