Sums of partially dependent Bernoulli random variables

Question

I am looking for any kind of Chernoff type large deviation bound for the following random variable: $$X = \sum_{i=1}^NX_i$$ where each $X_i$ is an identically distributed Bernoulli random variable which depends on exactly on $K$ other variables. I want to determine the upper bound on $$Pr[X \ge E[X]+\delta]$$ for some small $\delta > 0$.

Answer 1

In this preprint of Svante Jansson, this problem is examined. There are many citations to this paper but essentially such bounds do exist and you will need to dig around to find the best one. One example bound (derived from the Theorem 2.5 in 1) is the following:

$$P[X\geq E[X]+\delta] \leq \exp\left(-\frac{N p}{(1-p)K} \varphi\left[\frac{\delta}{Np(1+\frac{K}{8N})}\right]\right) $$

where $\varphi(x):=(1+x)\ln(1+x)-x.$ Hopefully I haven't made any mistakes translating it, so caveat emptor.