Skip to main content
2 of 5
added 162 characters in body
Iosif Pinelis
  • 127.9k
  • 8
  • 107
  • 229

$\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 in our terms can written 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 $u\ne0$ and $r(0):=1/2$.)

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

Iosif Pinelis
  • 127.9k
  • 8
  • 107
  • 229