# Tail bound of a distribution

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

• Do you need really the precise asymptotics of that probability? Or a "reasonably good" bound (with fast decay in $n$) will do? Nov 13 '17 at 20:31
• 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. Nov 13 '17 at 23:25
• 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)$. Nov 14 '17 at 14:27

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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9892393946647644, "perplexity": 119.15369909872499}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2021-39/segments/1631780057039.7/warc/CC-MAIN-20210920131052-20210920161052-00568.warc.gz"}