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!

$\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$ Commented May 9, 2024 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$ Commented May 9, 2024 at 14:32

1 Answer 1

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$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.