$\newcommand{\abs}[1]{\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](http://erelsgl.github.io/papers/randomsets-03.pdf), 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?



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.


