5
$\begingroup$

I'm looking for a seemingly natural generalization of a Chernoff bound.

In many scenarios, we have a distribution $D$ with support $\mathsf{Supp}(D)$, and some event $E \subset \mathsf{Supp}(D)$ telling us whether a property of a sample from $D$ holds (i.e. $a \in E$ iff $a\sim D$ has the property we want). Denoting $p =\Pr_{a\sim D}[a \in E]$, we use Chernoff to say something of the kind: if I draw $n$ independent samples from $D$, then with probability at least $1-\exp(-\delta^2pn/2)$, my multiset $A = \{a_1, \cdots, a_n\}$ of samples will be "$\delta$-good", where "$\delta$-good" means that if I fix this multiset $A$ once for all and sample (uniformly over the multiset) $a$ from $A$, then $a \in E$ will hold with probability $(1-\delta)p$. This is the standard Chernoff bound for Bernouilli random variables.

In my scenario, I need a generalization of the above, where the event is over $k$-tuples of samples from $D$ (i.e. $E \subset \mathsf{Supp}(D^k)$). Let $p = \Pr_{(a_1, \cdots, a_k)\sim D^k}[(a_1, \cdots, a_k) \in E]$. Suppose that for $i=1$ to $k$, I draw $n$ independent samples $(a_{i,1}, \cdots, a_{i,n})$ from $D$, which form a multiset $A_i$. I want to be able to make statements of the form: with probability at least 'something', the multisets $(A_1, \cdots, A_k)$ will be "$\delta$-good", where "$\delta$-good" means that if I fix $(A_1, \cdots, A_k)$ once for all and uniformly sample a $k$-tuple $(a_1, \cdots, a_k)$ from $A_1 \times \cdots \times A_k$, then $(a_1, \cdots, a_k)\in E$ will hold with probability at least $(1-\delta)p$.

Of course, the standard Chernoff bound does not apply anymore (it would apply if, instead, I had fixed a single multiset $A$ of $n$ random $k$-tuples sampled from $D^k$). Other concentration bounds I'm familiar with, such as Azuma's inequality or McDiarmid's bounded difference inequality, do not seem to apply either.

Question: is any such bound known in the literature, or does it follow from any standard concentration bound? Any pointer would be welcome. To be clear, I crucially need Chernoff-level strength: Markov or anything of the kind wont do. I've tried to derive a bound of this kind, first from standard concentration bounds with limited dependence (e.g. McDiarmid), and I've searched a bit the literature, both without success. Before trying to establish it from first principles, I figured it would be better to ask first, since it looks like something people should have considered before.

--

EDIT - answering the comments of kodlu

Do you have any other constraints on your function $f$? Lipschitz type? Subgaussian type?

Are you referring to the function $f$ that I initially used to define the event $E$? If so, why would this function being Lipschitz or Subgaussian matter in any way? Note that $f$ has nothing to do with the function we want to be Lipschitz when applying e.g. McDiarmid's inequality. For example, if you consider the case $k=1$ (which is the base case I'm trying to generalize), then whatever $f$ is, the resulting bound is exactly a bound on a sum of independent Bernouilli random variables - that is, the function is just a direct sum, and $f$ is just what defines whether the event happened or not. I understand that my choice of notations might have been confusing, I hope switching to $E$ as suggested by dohmatob makes things better.

What makes you think you'll get concentration in such an arbitrary setting in a product space? Do you have any experimental evidence?

My intuition is that there should be such a bound - now, that is barely more than an intuition. I have some kind of experimental evidence, but only for the very specific context I'm actually working on, though I believe that such a bound should hold in a more general setting (which is why I refrained from describing my precise and confusing setting).

In case it helps, anyway (and simplifying a bit): in the concrete setting I'm working on, a sample from $D$ is a length-$t$ vector of bits (for some parameter $t$) where each entry is sampled independently and is biased towards $0$, and the event over a $k$-tuple of samples $(a_1, \cdots, a_k)$ is defined as follows: the fraction of positions $i \in [1, t]$ such that at least one $a_j$ contains a $1$ at position $i$ belongs to $[1/10, 9/10]$. I'm trying to show that this event happens often enough it I fix $k$ multisets of samples as I described above, and sample one entry of the $k$-tuple from each multiset.

In this setting, yes, I have some weak kind of experimental evidence, coming from the fact that this bound captures the hardness of attacking a cryptographic primitive with a restricted family of attacks (well, at least a part of the analysis requires this bound). Since it's a primitive some people tried to break with these attacks and failed, it appears likely that there is such a bound.

$\endgroup$
12
  • $\begingroup$ The notation $a \leftarrow D$ really looks odd for what it is. $\endgroup$
    – dohmatob
    Aug 24, 2020 at 7:34
  • $\begingroup$ This is the standard notation for "a is sampled from D" in my field of research (cryptography), but I'll be happy to switch to any notation which will look more natural to people here on MathOverflow :) Can you suggest any? $\endgroup$ Aug 24, 2020 at 9:12
  • 1
    $\begingroup$ How about about "$a \sim D$" ? $\endgroup$
    – dohmatob
    Aug 24, 2020 at 9:28
  • 1
    $\begingroup$ Hi kodlu, thanks for your comment. I tried to address the question it contains directly in the body of the post, since 500 characters would not have sufficed. $\endgroup$ Aug 26, 2020 at 9:33
  • 1
    $\begingroup$ Is this summary right? You have $nk$ i.i.d. draws from $D$, arranged in $k$ columns each of height $n$. You have that any fixed row falls in $E$ with probability $p$. You want to show that with high probability, about a $p$ fraction of the possible combinations obtained by taking one element from each column fall in $E$. $\endgroup$
    – usul
    Aug 26, 2020 at 16:01

1 Answer 1

4
$\begingroup$

Theorem 2 in [1] gives a bound of $1-\frac{4e^{-\delta^2n/8}}{\delta}$. I think you can incorporate $p$ in the bound since the proof of that theorem uses the standard Chernoff bound.

[1] Yakov Babichenko, Siddharth Barman, Ron Peretz (2017) Empirical Distribution of Equilibrium Play and Its Testing Application. Mathematics of Operations Research 42(1):15-29. http://dx.doi.org/10.1287/moor.2016.0794

$\endgroup$
3
  • $\begingroup$ Many thanks! I will read that carefully and accept your answer afterwards. By the way, for other readers, here is the direct link to the paper without paywalls: arxiv.org/pdf/1310.7654.pdf $\endgroup$ Aug 26, 2020 at 14:01
  • $\begingroup$ The arxiv version is slightly different, but i guess you can get the idea from looking at Lemma 1 in the arxiv version. $\endgroup$
    – Ron P
    Aug 26, 2020 at 14:53
  • $\begingroup$ Yes, that's what I figured. Otherwise, is there a way to get access to the version which is behind a paywall? $\endgroup$ Aug 26, 2020 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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