4
$\begingroup$

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

$\endgroup$

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I forgot to say that, of course, the $\sigma_i$s are all independent. $\endgroup$ Dec 12, 2016 at 17:04
  • $\begingroup$ 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$? $\endgroup$ Dec 12, 2016 at 17:06
  • $\begingroup$ The latter is unfortunately impossible; see Theorem 4 (Sudakov Minoration for Bernoulli Process) in springer.com/cda/content/document/cda_downloaddocument/… $\endgroup$ Dec 12, 2016 at 17:18
  • $\begingroup$ 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 $\endgroup$ Dec 13, 2016 at 7:42
  • $\begingroup$ My guess is that your $d$ in $d$-boundedness plays the role of $n$. $\endgroup$ Dec 13, 2016 at 9:21
1
$\begingroup$

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.]

$\endgroup$
1
  • $\begingroup$ 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"). $\endgroup$ Dec 10, 2016 at 21:20
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Dec 12, 2016 at 9:17
  • $\begingroup$ 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. $\endgroup$ Dec 12, 2016 at 9:35
  • $\begingroup$ 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.) $\endgroup$ Dec 12, 2016 at 9:42
  • $\begingroup$ I'll reply in a separate answer. $\endgroup$ Dec 12, 2016 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.