0
$\begingroup$

Additive Chernoff

Suppose $X_1, \ldots, X_n$ are i.i.d. random variables, taking values in $\{0,1\}$. Let $p=\mathrm{E}\left[X_i\right]$ and $\varepsilon>0$.

\begin{gather*} \operatorname{Pr}\left(\frac{1}{n} \sum X_i \geq p+\varepsilon\right) \leq\left(\left(\frac{p}{p+\varepsilon}\right)^{p+\varepsilon}\left(\frac{1-p}{1-p-\varepsilon}\right)^{1-p-\varepsilon}\right)^n=e^{-D(p+\varepsilon \mathbin\| p) n } \\ \operatorname{Pr} \left(\frac{1}{n} \sum X_i \leq p-\varepsilon\right) \leq\left(\left(\frac{p}{p-\varepsilon}\right)^{p-\varepsilon}\left(\frac{1-p}{1-p+\varepsilon}\right)^{1-p+\varepsilon}\right)^n=e^{-D(p-\varepsilon \mathbin\| p) n} \end{gather*}

where $$ D(x \mathbin\| y)=x \ln \frac{x}{y}+(1-x) \ln \left(\frac{1-x}{1-y}\right). $$

For sums of i.i.d random variables, is there any bound tighter than the additive Chernoff?

$\endgroup$
3
  • $\begingroup$ @DavidRoberts, while doing some other tidying edits, I considered capitalising ‘chernoff’ (as adjective) and ‘bernoulli’ (as non-proper noun), but thought that it might be a domain-specific peculiarity. For example, though I don't, it is quite common to refer to ‘abelian groups’ and ‘euclidean spaces’, and I have even seen the startling term ‘hilbertspace’. $\endgroup$
    – LSpice
    Commented Oct 30, 2023 at 17:25
  • $\begingroup$ @LSpice The answer by Iosif below capitalised Chernoff, and I've only ever seen it written that way. "Bernoullis" was slightly amusing to me, given how many of them were mathematicians, but I didn't edit it to "Bernoulli random variables". $\endgroup$
    – David Roberts
    Commented Oct 31, 2023 at 2:26
  • $\begingroup$ The Karns-Saul inequality is relevant here, see my answer to this question cstheory.stackexchange.com/questions/32978/… $\endgroup$ Commented Oct 31, 2023 at 11:04

2 Answers 2

2
$\begingroup$

Simple and explicit upper and lower bounds on the binomial tail that are asymptotically sharp (as $n\to\infty$) and improve the Chernoff upper bound by a factor $\asymp1/\sqrt n$ were rather recently obtained by Ferrante.

Specifically, for $\bar X_n:=\frac1n\,\sum_{i=1}^n X_i$ it was shown in that paper that one has the following upper and lower bounds on the right binomial tail: $$P(\bar X_n\ge a) \le U_{n,p,a}:=\frac1{1-r}\frac1{\sqrt{2\pi(1-a)an}}\,e^{-n D(a\parallel p)}$$ if $a>p\in(0,1)$, $1\le an\le n-1$, and $$r:=\frac pa\frac{1-a}{1-p}$$ and $$P(\bar X_n\ge a) \ge L_{n,p,a}:=\Big(1-\frac cn\Big)U_{n,p,a}$$ if $a>p\in(0,1)$, $1\le an\le n-1$, $an\in\mathbb N$, and $$c:=\frac1{(1-a)a}\Big(1+\frac{(1+r)r}{(1-r)^2}\Big).$$

Upper and lower bounds on the left binomial tail immediately follow from these results by the reflection $X_i\leftrightarrow1-X_i$.

$\endgroup$
2
  • $\begingroup$ This is helpful! Thanks! Could you also comment on my second question? $\endgroup$
    – Dotman
    Commented Oct 29, 2023 at 22:06
  • 2
    $\begingroup$ @Dotman : I am glad this was helpful. As for your second question, according to MathOverflow (MO) guidlines, MO users should avoid answering posts with multiple questions. This especially concerns questions added after the original question was answered. So, please roll back your edit by removing the additional question. After that, please follow these other MO guidelines. You may then also want to post any additional questions elsewhere. $\endgroup$ Commented Oct 30, 2023 at 1:33
0
$\begingroup$

Your latter question was

For sums of i.i.d random variables, is there any bound tighter than the additive Chernoff?

Here's an argument that says that under nice conditions, one can improve on the Chernoff inequality by a factor of $1/\sqrt{n}$. In other words, it should be the case that for nice i.i.d. variables with mean $\mu$, for $t > \mu$ we have \begin{align*} \mathbb{P} \left( \frac{X_1 + \ldots + X_n}{n} > t \right) \sim \frac{c_t}{\sqrt{n}}e^{-nI(t)}, \end{align*} where "$e^{-nI(t)}$ is the Chernoff bound" (see below for a precise statement).


Under a probability law $\mathbb{P}_0$, let $X_1,\ldots,X_n$ be i.i.d. random variables that, for the sake of simplicity, have a globally defined moment generating function $f(\lambda) := \mathbb{E}[e^{\lambda X_1}]$. Suppose $\mathbb{E}[X_1] = \mu$, and $t > \mu$.

For $\lambda \in \mathbb{R}$, define a change of measure by \begin{equation} \frac{d\mathbb{P}_\lambda}{d \mathbb{P}_0} := f(\lambda)^{-n} \prod_{i=1}^n e^{ \lambda X_i}. \end{equation} Then under $\mathbb{P}_\lambda$, the $X_i$ are still i.i.d., but with an exponentially tilted version of the originally probability law. When $\lambda$ is positive, the $X_i$ tend to take larger values.

For any $t > \mu$, there is a $\lambda_t > 0$ such that $\mathbb{E}_\lambda[X_1]=t$.

Then with $\lambda_t$ the tilting factor required to bring the mean up to $t$, we have \begin{equation} \mathbb{P}_0 \left( \frac{X_1 + \ldots + X_n}{n} > t \right) = f(\lambda_t)^n \mathbb{P}_{\lambda_t} \left[ \mathrm{1}\left\{ \frac{X_1 + \ldots + X_n}{n} > t \right\} e^{ - \lambda_t \frac{X_1+\ldots+X_n}{n} } \right], \end{equation} which reduces a bit further to \begin{equation} \mathbb{P}_0 \left( \frac{X_1 + \ldots + X_n}{n} > t \right) = e^{ - nI(t) } \mathbb{P}_{\lambda_t} \left[ \mathrm{1}\left\{ Z_n > 0 \right\} e^{ - \lambda_t \sqrt{n} Z_n } \right], \end{equation} where \begin{align*} I(t) := - \log f(\lambda_t) + t \lambda_t. \end{align*} and \begin{align*} Z_n := \frac{(X_1 - t) + \ldots + (X_n - t)}{\sqrt{n}} . \end{align*} The standard Chernoff inequality now follows from using the simple bound \begin{align*} \mathbb{P}_{\lambda_t} \left[ \mathrm{1}\left\{ Z_n > 0 \right\} e^{ - \lambda_t \sqrt{n} Z_n } \right] \leq 1. \end{align*} On the other hand, $Z_n$ is approximately Gaussian with variance $\sigma_t^2$, where $\sigma_t^2 := \mathbf{E}_{\lambda_t}[(X_1-t)^2]$. In fact, by the Berry-Esseen theorem, the distribution function of $Z_n/\sigma_t$ agrees with the standard Gaussian distribution up to an error of $O(1/\sqrt{n})$. Thus we might expect that \begin{align*} \mathbb{P}_{\lambda_t} \left[ \mathrm{1}\left\{ Z_n > 0 \right\} e^{ - \lambda_t \sqrt{n} Z_n } \right] \approx \int_0^\infty e^{-\lambda_t\sigma_t\sqrt{n} u} \frac{ e^{ -u^2/2} du}{\sqrt{2\pi}} \approx \frac{1}{\sqrt{2 \pi}\lambda_t\sigma_t \sqrt{n}}. \end{align*} Thus we should in fact have, \begin{equation} \mathbb{P}_0 \left( \frac{X_1 + \ldots + X_n}{n} > t \right) = \left( \frac{1}{\sqrt{2 \pi}\lambda_t\sigma_t \sqrt{n}} + O_t(1/n) \right) e^{ - nI(t) }, \end{equation} where the exact form of the $O_t(1/n)$ terms can probably be described in terms of a local limit or Berry-Esseen theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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