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

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

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?

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

1. For sums of i.i.d random variables, is there any bound tighter than the additive Chernoff?
2. Using the result presented in this question on Theoretical Computer Science StackExchange, I believe I can use the additive form for sums of independent (not necessarily iid) Bernoullis. Is there any bound that outperforms additive Chernoff in this scenario?

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

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

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

1. For sums of i.i.d random variables, is there any bound tighter than the additive chernoff?
2. Using the result presented in this question on Theoretical Computer Science StackExchange, I believe I can use the additive form for sums of independent (not necessarily iid) bernoullis. Is there any bound that outperforms additive chernoff in this scenario?

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

1. For sums of i.i.d random variables, is there any bound tighter than the additive Chernoff?
2. Using the result presented in this question on Theoretical Computer Science StackExchange, I believe I can use the additive form for sums of independent (not necessarily iid) Bernoullis. Is there any bound that outperforms additive Chernoff in this scenario?