Tail bound of a distribution

Question

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}$.

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.