2
$\begingroup$

Given $x_1,x_2,\ldots,x_n$ i.i.d. bernoulli random variables with $P(x_i=1)=\frac1n$. Given a constant $c=1+\frac{1}{m}, m\geq n$. Is there an explicit theorem that can derive a concentration argument (possibly a modified Chernoff or similar) for the following:

$$P(\sum_{i=1}^n c^{i-1} \cdot x_i - E(x_i)\cdot \sum_{i=1}^n c^{i-1}>\epsilon)<\delta$$

All the posts I found are for general weighted sum Bernoulli and there's not an explicit form yet, but here my question has more structure to it. Thanks!

Improve this question
$\endgroup$
2
  • $\begingroup$ If $c\ge2$ (say) or, more generally, if $c\ge1+t_n$ with $nt_n\to\infty$, then the weighted sum of the $n$ random variables $c^{i-1}x_i$ will be close to the sum of a few $c^{i-1}x_i$'s with the largest values of $i$, and then there will no concentration. That is, you can get concentration only if $c=1+O(1/n)$. $\endgroup$
    – Iosif Pinelis
    Commented May 9 at 12:40
  • $\begingroup$ Thanks for the comments, I have updated the question. For $c=1+1/m$ with $m\geq n$, how should I derive the concentration bound? $\endgroup$
    – Betty
    Commented May 9 at 14:32

1 Answer 1

Reset to default
1
$\begingroup$

$\newcommand\ep\epsilon$Let $X_i:=c^{i-1}(x_i-Ex_i)$, so that the $X_i$'s are independent zero-mean random variables. The condition $c=1+1/m$ for $m\ge n$ implies that $$c=1+b/n,$$ where $0<b=O(1)$. Let $S:=\sum_1^n X_i$. We have to upper-bound $P(S\ge\ep)$ for real $\ep>0$.

It follows from the proof of inequality (2.9) in Hoeffding (1963) (see formula (4.18) in Hoeffding's paper and the last equality in formula (12) in Bennett (1962)) that $$ P(S\ge\ep)\le Q(\ep):=\exp\Big\{\frac{B^2}{y^2}\,\psi\Big(\frac{\ep y}{B^2}\Big)\Big\},\tag{10}\label{10}$$ where $\psi(u):=u-(1+u)\ln(1+u)$, and $B^2$ and $y$ are any positive real numbers such that $$X_i\le y\text{ for all }i\text{ and }\sum_1^n EX_i^2\le B^2. \tag{20}\label{20} $$ (Inequality (2.9) in Hoeffding's paper was established using a condition that can be written, in our terms, as $\sum_1^n EX_i^2=B^2$, instead of the condition $\sum_1^n EX_i^2\le B^2$ in \eqref{20}. A much simpler way to derive \eqref{10} assuming \eqref{20} is to note that the function $r$ is increasing on $\Bbb R$, where $r(u):=(e^u-1-u)/u^2$ for real $u\ne0$ and $r(0):=1/2$. -- See the details at the end of this answer.)

Note that $$X_i\le c^{i-1}\le c^n=(1+b/n)^n<e^b$$ for all $i=1,\dots,n$ and $$\sum_1^n EX_i^2=\sum_1^n c^{2i-2}\frac1n\Big(1-\frac1n\Big) \le\frac1n\frac{c^{2n-1}-1}{c^2-1}<\frac{e^{2b}-1}{2b}.$$ So, \eqref{10} holds with $$B^2=\frac{e^{2b}-1}{2b},\quad y=e^b.$$

Note that, in view of the condition $0<b=O(1)$, we have $B^2\asymp1$ and $y\asymp1$. So, the bound $Q(\ep)$ in \eqref{10} will go to $0$ iff $\ep\to\infty$, and then we will have $$Q(\ep)=e^{-C\ep\ln\ep},$$ where $C\asymp1$, so that the distribution of $S$ has a Poisson-like right tail. This shows that the bound $Q(\ep)$ on $P(S\ge\ep)$ is good, because even for $b=0$ the distribution of $S$ converges to a Poisson distribution (as $n\to\infty$).

Proof of \eqref{10}: For any real $h\ge0$, \begin{align} P(S\ge\ep)&\le e^{-h\ep}\prod_1^n Ee^{hX_i} \\ &\le e^{-h\ep}\exp\sum_1^n (Ee^{hX_i}-1) \\ &= e^{-h\ep}\exp\sum_1^n (Ee^{hX_i}-1-hX_i) \\ &= e^{-h\ep}\exp\sum_1^n r(hX_i)h^2EX_i^2 \\ &\le e^{-h\ep}\exp\sum_1^n r(hy)h^2EX_i^2 \\ &\le e^{-h\ep}\exp(r(hy)h^2B^2) \\ &= \exp\{-h\ep+(e^{hy}-1-hy)B^2/y^2\} \\ &=Q(\ep) \end{align} if $h=\frac1y\,\ln(1+\frac{\ep y}{B^2})$ (the minimizer of $-h\ep+(e^{hy}-1-hy)B^2/y^2$ in $h$). $\quad\Box$

Improve this answer
$\endgroup$

You must log in to answer this question.

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