Let $X_1, X_2, \ldots, X_n, Y_1, Y_2, \ldots, Y_n$ be independent binary random variables each being $1$ with probability $\frac{1}{k}$.

Let $Z = X_1(Y_1 + \cdots + Y_k) + X_2(Y_2 + \cdots + Y_{k+1}) + \cdots + X_n(Y_n + Y_1 + \cdots + Y_{k-1})$.

It is easy to see that the expected value of $Z$ is $\mu = \frac{n}{k}$.

Can someone suggest the best possible bound one can obtain for the probability $\Pr[Z \ge (1+\varepsilon) \mu]$?

The setting I am interested in where $n$ is large, and $k \approx \sqrt{n}$.

  • 2
    $\begingroup$ Do you need really the precise asymptotics of that probability? Or a "reasonably good" bound (with fast decay in $n$) will do? $\endgroup$ Nov 13, 2017 at 20:31
  • $\begingroup$ I expect the decay to be exponential in $\sqrt{n}$ for $k \approx \sqrt{n}$. I need as good a bound as possible, but for now, even a reasonably good bound will be helpful. $\endgroup$
    – user47772
    Nov 13, 2017 at 23:25
  • $\begingroup$ The first idea I had in mind was the following: condition on $Y_1,\dots,Y_n$ to be reduced to a deviation inequality of independent sequence, in this case a weighted sum of i.i.d. However, we have to control the sum of variances, which does not seem easy. This can probably be done by having information about the eigenvalues of a symmetric real matrix, since it will be a quadratic form applied to $(y_1,\dots,y_n)$. $\endgroup$ Nov 14, 2017 at 14:27

1 Answer 1


Here are some ideas, which may be too long for a comment. Denote for fixed $n$ and $k$: $$ Z_{n,k}:=\sum_{i=1}^n\left(X_i\sum_{j=1}^k Y_{i+j-1 \mod n}-\frac 1k\right). $$ Let $$ A_{n,k}:=\sum_{i=1}^{n-k}\left(X_i\sum_{j=1}^k Y_{i+j-1} -\frac 1k\right)\mbox{ and } $$ $$ B_{n,k}:=\sum_{i=n-k+1}^n\left(X_i\sum_{j=1}^k Y_{i+j-1 \mod n}-\frac 1k\right). $$ It seems that the contribution of $B_{n,k}$ in the setting you are interested in would not be too big. In order to bound that of $A_{n,k}$, let us denote $$ I_l:=\left\{i\in\mathbb N, kl\leqslant i\leqslant\left(k+1\right)l-1\right\} $$ and $$C_{l}:=\sum_{i\in I_l}\left(X_i\sum_{j=1}^k Y_{i+j-1} -\frac 1k\right).$$ We can express $A_{n,k}$ in terms of a sum of $C_l$ plus a negligible term. Moreover the sequence $\left(C_{2l}\right)_{l\geqslant 1}$ is centered and independent, as well as $\left(C_{2l-1}\right)_{l\geqslant 1}$ hence we can apply an inequality by Fuk and Nagaev (1971). It remains to control the tail of $C_l$ and its variance.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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