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

$\endgroup$
  • 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 Nov 13 '17 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 '17 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 Nov 14 '17 at 14:27
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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