$\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, 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?