<p>I'm posting a suitable answer that I found for this problem. The approach linked <a href="http://users.math.cas.cz/~gavinsky/papers/Tail-read-k.pdf" rel="nofollow noreferrer">here</a> 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. </p>

CC BY-SA 3.0
2017-11-26T16:52:36.807Z
2017-11-26T16:52:36.807Z
mm8511
<p>So I am trying to figure out an upper bound on the probability of the following... </p>

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

<p>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}$</p>

<p>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]$.</p>

<p>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.</p>

CC BY-SA 3.0
2018-02-24T18:33:48.817Z
Reading the question, I don't see where $I_r$ shows up at all. It does not appear in the definition of $Z$...
Clement C.
CC BY-SA 3.0
2018-02-25T18:21:16.037Z
@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.)
mm8511
CC BY-SA 3.0
2017-11-11T05:29:40.720Z
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?
kodlu
CC BY-SA 3.0
2017-11-13T17:46:58.470Z
@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
mm8511
<reference-request><pr.probability><chernoff-bound>
Janson-type inequality, limited dependence
mm8511
# Janson-type inequality, limited dependence

(Asked by: username_0 on 2017-11-08)

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.

**Tags:** reference-request, pr.probability, chernoff-bound
> **Comments:**
> **username_2**: 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?  
> **username_0**: @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  
> **username_1**: Reading the question, I don't see where $I_r$ shows up at all. It does not appear in the definition of $Z$...  
> **username_0**: @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.)  

---

## 1 answers

### Answer by username_0 on 2017-11-26. Score: 1

I'm posting a suitable answer that I found for this problem. The approach linked [here](http://users.math.cas.cz/~gavinsky/papers/Tail-read-k.pdf) 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.


---

