8
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 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$
    – Serguei Popov
    Commented 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
    Commented 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$
    – Davide Giraudo
    Commented Nov 14, 2017 at 14:27

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .