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.
