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.



Chernoff-style concentration inequality for k-tuples
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>


