Concentration bounds for a sum of dependent almost rademacher variables

102 Views Asked by At

Let $Y_1,\ldots, Y_n \in \{\pm1\}$ be i.i.d. Rademacher variables. Define the following "Rademacher" variables: $$Y'_i=\operatorname{sign}\left(\sum_{j\neq i} Y_iY_j + C\right)$$ for some constant $C$. The $Y'_i$ are identically distributed, but they are dependent. I am trying to bound $$\Pr\left(\sum_{i=1}^nY'_i - \sum_{i=1}^n\mathbb{E}\left[Y'_i\right]>\gamma\right)$$ Where $\gamma$ is a constant (i.e. does not depend on n). Intuitively (and in simulations), for large enough $n$ it seems like there should be some bound there, but I can't manage to prove it.