4
$\begingroup$

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. :( enter image description here

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'’}.$$

$\endgroup$
11
  • 1
    $\begingroup$ 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$)? $\endgroup$
    – River Li
    Sep 10, 2021 at 5:38
  • $\begingroup$ @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$. $\endgroup$ Sep 10, 2021 at 17:38
  • $\begingroup$ 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$. $\endgroup$
    – River Li
    Sep 11, 2021 at 0:00
  • $\begingroup$ @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)$. $\endgroup$ Sep 11, 2021 at 1:52
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – River Li
    Sep 11, 2021 at 5:32

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Sep 11, 2021 at 17:16
  • 1
    $\begingroup$ 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}$. $\endgroup$ Sep 11, 2021 at 18:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .