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