# Concentration inequalities for random sets

$\newcommand{\abs}{\left|#1\right|}$

There is a population $O$ with a countable (finite or infinite) number of subjects. The population is colored randomly: for each subject, an unbiased coin-toss is used to decide whether the subject is colored red or green. Then, a sub-population containing $t$ subjects are selected; denote this sub-population by $T$ (so $T\subseteq O$ and $|T|=t$). Denote by $T^R$ the set of red subjects in $T$ and by $T^G$ the set of green subjects. The difference $\abs{|T^R|-|T^G|}$ denotes the imbalance caused by the randomization process. What is high-probability upper bound on this imbalance, as a function of $t$?

There are two extreme cases:

• The easy case is when $T$ does not depend on the coloring, i.e, $T$ is a deterministic set defined before the coin-tosses. Then, both $|T^R|$ and $|T^G|$ are expected to be near $|T|/2$. The difference between them can be bounded using standard concentration inequalities, e.g, by Hoeffding's inequality, with probability $1-o(1/t)$, the imbalance is $O(\sqrt{t \ln t})$.
• The hard case is when $T$ can depend on the coloring in an arbitrary way. Then, no non-trivial upper bound exists. For example, an adversary can select $T$ to contain $t$ red subjects. In this case, $T^R=T$ and $T^L=\emptyset$ and the difference between their sizes is $t$, which is as large as can be.

I am are interested in an intermediate case, in which $T$ may depend on the coloring but only in a restricted way. As an example, suppose all the subjects in $O$ are placed on the real line, and $T$ must be an interval. $T$ may depend on the coloring, so it is a random variable and the standard concentration inequalities do not apply. However, the restriction to an interval means that an adversary cannot always select $T$ to contain $t$ red subjects. Therefore we may hope to have a non-trivial upper bound on the imbalance $\abs{|T^R|-|T^G|}$.

In this draft, I developed some high-probability concentration inequalities for some families of random-sets (including the interval case and some generalizations). I thought of submitting it for publication in some letters journal, but then I had a feeling that this might be a known result.

So, my question is: what are some known concentration inequalities for random sets?

I'll combine Ryan's answer and my elaboration of it into a single (hopefully, coherent) answer.

I'll represent Erel's random R/G coloring as the assignment of a random $\sigma_i\in\{-1,1\}$ to each point $x_i\in O$. Put $n:=|O|$. I'll represent the set $T$ as a function $f:O\to\{0,1\}$, where $f$ is the characteristic (indicator) function of $T$. Finally, I'll represent by $F$ the collection of all permissible functions $f$. Erel's quantity of interest is $$\mathbb{E} \max_{f\in F} \sum_{i=1}^{n}\sigma_i f(x_i) \qquad (*).$$ (Now, Erel actually cares about the right tail of the random variable $\max_{f\in F} \sum_{i=1}^{n}\sigma_i f(x_i)$, but the latter is concentrated about the mean by McDiarmid's inequality -- so it suffices to bound the mean.) Up to a normalizing factor of $n$, the expression $(*)$ is just the Rademacher complexity of $F$, as Ryan pointed out. The latter can be bounded by the VC-dimension of $F$: denoting the latter by $D$, an upper bound on $(*)$ is $\Theta(\sqrt{nD})$ as shown, e.g., in my lecture notes.

• I forgot to say that, of course, the $\sigma_i$s are all independent. Dec 12, 2016 at 17:04
• This is much clearer now, thanks! But, what if the size of the global population ($n$) is not bounded? Is there a bound that only depends on the size of $T$? Dec 12, 2016 at 17:06
• The latter is unfortunately impossible; see Theorem 4 (Sudakov Minoration for Bernoulli Process) in springer.com/cda/content/document/cda_downloaddocument/… Dec 12, 2016 at 17:18
• But... how can this be impossible if I have proved such a bound here (in Lemma 3.5)? erelsgl.github.io/papers/randomsets-03.pdf Dec 13, 2016 at 7:42
• My guess is that your $d$ in $d$-boundedness plays the role of $n$. Dec 13, 2016 at 9:21

I think a keyword to help you here is Rademacher Complexity. Learning theorists know a lot about these kinds of questions. In particular, for the intervals-on-a-line case, the high-probability bound for the maximum discrepancy should be $O(1/\sqrt{n})$, where $n = |O|$. More generally, if $O \subset \mathbb{R}^d$ and $T$ must be the intersection of $O$ with a halfspace, the bound should be $O(\sqrt{d/n})$, I think. [I could be mistaken here, I didn't look at the details very carefully.]

• I read the definition, but I am not sure how to match it to my problem of random sets: (a) The definition is about a sample drawn i.i.d. from a given distribution; in my problem there is no distribution - there is a fixed population that is colored randomly. (b) The definition is about real-valued functions $h$ that operate on individual samples, $h(z_i)$; in my problem, there is a set-valued function $T$ that can be a function of the entire sample (e.g, "the interval that contains the largest number of red subjects"). Dec 10, 2016 at 21:20

To follow up on Ryan's answer, the combinatorial notion of VC-dimension characterizes the maximal deviation of an empirical average from the true mean. See my course notes here: https://www.cs.bgu.ac.il/~asml162/Class_Material in particular, lectures 05-05-2016--09-06-2016.

• I read your interesting lecture notes, but, I still do not see the connection to the problem of random sets... where here is the distribution? Dec 12, 2016 at 9:17
• I think the red-green labeling process corresponds to drawing a labeled sample (say, red is 1 and green is 0). You want to know how close the empirical average is to the "true" (i.e., population) mean. Dec 12, 2016 at 9:35
• OK, but the "red" sample is not drawn from a distribution... one may say that initially there is a distribution determined by the population, but, the distribution changes once we draw some elements (the samples are not i.i.d.) Dec 12, 2016 at 9:42
• I'll reply in a separate answer. Dec 12, 2016 at 16:19