4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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? $\endgroup$
    – kodlu
    Nov 11, 2017 at 5:29
  • $\begingroup$ @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 $\endgroup$
    – mm8511
    Nov 13, 2017 at 17:46
  • $\begingroup$ Reading the question, I don't see where $I_r$ shows up at all. It does not appear in the definition of $Z$... $\endgroup$
    – Clement C.
    Feb 24, 2018 at 18:33
  • $\begingroup$ @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.) $\endgroup$
    – mm8511
    Feb 25, 2018 at 18:21

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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