# Janson-type inequality, limited dependence

So I am trying to figure out an upper bound on the probability of the following...

This is a question related to a problem I am working on (not for a class, just for fun)

Let $\Omega=\{X_{1},\dots,X_{n}\}$ where each $X_{i}$ is i.i.d Bernoulli with success probability 1/2. Let $Y=\{Y_{1},\dots,Y_{N}\}$ where $Y_{i}\subset\Omega$ and $|Y_{i}|=t$. Let $Z_{i}$ indicate the event that $\sum_{X\in Y_{i}}X\geq k$, where $k$ is some value close to $t$. Let $Z=\sum_{i=1}^{N}Z_{i}$

Say that $I_{r}= \{\{Y_{i},Y_{j}\}:|Y_{i}\cap Y_{j}|=r\}$, that is, $I_{r}$ is the set of all pairs from $Y$ that share $r$ elements from $X$. I am looking for an upper bound on $Pr[Z\leq\mathbb{E}[Z]-t]$.

I've seen Janson's inequality and notice that it looks quite similar to this, but I'm not sure where to go from here. Any help or any references would be greatly appreciated.

• I am confused by your notation but two upvoters arent... what is $X$? Is $\Omega$ a set? a vector? If $X_i$ are vectors they are not Bernoulli, right? Are they all same length? Nov 11 '17 at 5:29
• @kodlu Each $X_i$ is iid bernoulli (either 0 or 1) with success probability $p$, and the sets $Y_j$ are subsets of $\Omega$ i.e. are sets containing some of the $X_i$'s that are in $X$. I think of $\Omega$ as my probability space, and the $X_i$'s are the elements... I have information about the number of elements shared between any of the $Y_i$'s and want to derive a concentration bound from this Nov 13 '17 at 17:46
• Reading the question, I don't see where $I_r$ shows up at all. It does not appear in the definition of $Z$... Feb 24 '18 at 18:33
• @ClementC. The purpose of introducing $I_{r}$ (defined for $r=0,\dots,t$) was to give an idea of the amount of "dependence" between the $Y_{j}'s$. In the actual problem, I had $|I_{0}|>|I_{1}|> \dots >|I_{t}|=0$, and $|I_{r}| / |I_{r+1}| \approx n^{2}$. The set up is basically the same as that of Janson's inequality, but I was wondering if anyone knew of any stronger bounds for this specific instance (Each $X_i ~$ Bernoulli$(1/2)$ etc.) Feb 25 '18 at 18:21

I'm posting a suitable answer that I found for this problem. The approach linked here does not exploit the fact that no $t$-tuples of elements of $\Omega$ are present in too many subsets $Y$ (for arbitrary $t$), but it does end up giving me a good enough bound anyway.