# Hoeffding’s inequality for a modified concentration

The Hoeffding's inequality is $$P(S_n - E[S_n] \geq \epsilon) \leq e^{-2\epsilon^2/k'},$$ where $$S_n = \sum_{i=1}^{n} X_i$$, $$X_i$$'s are independent bounded random variables, and $$k'$$ depends on the bounded ness of those random variables.

My question: Can we get a similar high probability result as follows? $$P(\sqrt{S_n} - \sqrt{E[S_n]} \geq \epsilon) \leq e^{-2\epsilon^2/k'’}.$$

My try so far: Using variations of the fact $$\sqrt{a+b} \leq \sqrt{a} + \sqrt{b}$$ for $$a,b \geq 0$$, we get $$P(\sqrt{S_n} - \sqrt{E[S_n]} \geq \epsilon) \leq e^{-2\epsilon^4/k'’}.$$ Although this is quite loose compared to $$e^{-\epsilon^2}$$. :(

Or, is this expected for the problem I am looking at? Is $$\sqrt{E[S_n]}$$ a bad approximation of $$\sqrt{S_n}$$? Ofcourse it is a biased approximation.

Any help/pointers is appreciated! :)

Edit 1: Lemma 2.1 in this note might have some insightful algebra that is required to show a tighter bound, although I am successful in doing so yet. :(

Edit 2: Also, notice that naturally the question is intended to work for the symmetrical version as well: $$P(|\sqrt{S_n} - \sqrt{E[S_n]}| \geq \epsilon) \leq e^{-2\epsilon^2/k'’}.$$

• How about dealing with $S_n \ge (\sqrt{E[S_n]} + \epsilon)^2$ (or $S_n - E[S_n] \ge 2\sqrt{E[S_n]}\epsilon + \epsilon^2$)? Sep 10, 2021 at 5:38
• @RiverLi nice trick, but still the $\epsilon^4$ dominates in this case as well. :( It feels simple but I am missing something obvious somewhere! This should be simpler than that of known results of form $P(f(S_n) - E[f(S_n)]>\epsilon)$ for convex $f$. Sep 10, 2021 at 17:38
• If we know the bounds for $E[S_n]$, we may deal with $S_n - E[S_n] \ge 2\sqrt{E[S_n]}\epsilon + \epsilon^2$: for example, $2\sqrt{E[S_n]}\epsilon > \epsilon^2$. Sep 11, 2021 at 0:00
• @RiverLi Yes, with this we get $$P(\sqrt{S_n} - \sqrt{E[S_n]} \geq \epsilon) \leq e^{-2\epsilon^4/k'’}.$$ I am trying to see if we can further improve this from $e^{-\epsilon^4}$ to $e^{-\epsilon^2}$. Note that $\epsilon$ Is typically small for better sample approximation; can take it to be in $(0,1)$. Sep 11, 2021 at 1:52
• Actually, we do not need to assume that. I just assume that in case $E[S_n] = 0$, in that case, $P(\sqrt{S_n} - \sqrt{E[S_n]} \ge \epsilon) = P(S_n - E[S_n] \ge 2\sqrt{E[S_n]}\epsilon + \epsilon^2) \le P(S_n - E[S_n] \ge \epsilon^2)$. Sep 11, 2021 at 5:32

I am assuming that $$X_i \ge 0$$. From the concave function version of Jensens inequality, we have that

$$\epsilon + \mathbb{E}[\sqrt{S_n}] \le \epsilon + \sqrt{\mathbb{E}[S_n]}.$$

Thus, we have that

$$\Pr\left[\sqrt{S_n} > \epsilon + \sqrt{\mathbb{E}[S_n]}\right] \le \Pr\left[\sqrt{S_n} > \epsilon + \mathbb{E}\left[\sqrt{S_n}\right]\right] = \Pr\left[\sqrt{S_n} - \mathbb{E}\left[\sqrt{S_n}\right] > \epsilon\right].$$

Since the $$X_i$$'s are bounded, we can bound the last term using the bounded differences inequality. Let $$f: A^n \to \mathbb{R}$$ given by $$f(x_1, \ldots, x_n) = \frac{\sqrt{\sum_{i=1}^n x_i}}{\sqrt{n}}$$. Here $$A$$ is the bounded interval that $$X_i$$ is defined on. Let $$C$$ be the diameter or length of $$A$$. Then we have that for all $$x_1, \ldots, x_n, x_i' \in A$$,

$$|f(x_1, \ldots, x_i, \ldots, x_n) - f(x_1, \ldots, x_i', \ldots, x_n)| \le \frac{\sqrt{C}}{\sqrt{n}}.$$

Then we can use the bounded differences in equality (See, lecture notes 1) to get that

$$\Pr\left[\sqrt{S_n} - \mathbb{E}[\sqrt{S_n}] > \epsilon\right] \le \exp\left(-\frac{2\epsilon^2}{C}\right).$$

• This is interesting. Although not asked in OP, this argument via Jensen’s fails to get $$\Pr\left[ \mathbb{E}[\sqrt{S_n}] - \sqrt{S_n} > \epsilon\right] \le \exp\left(-\frac{2\epsilon^2}{C}\right).$$ Or, does this still hold by some other manipulation? Sep 11, 2021 at 17:16
• We might not be able to show the bound for $\Pr[\sqrt{\mathbb{E}[S_n]} - \sqrt{S_n} > \epsilon]$. As the original question says, $\sqrt{\mathbb{E}[S_n]}$ is a biased estimate for $\sqrt{S_n}$. Sep 11, 2021 at 18:09