# Symmetry of concentration bounds on mean

Question summary:

If I have a two-sided bound, can I immediately get a one-sided bound with tighter constants?

Question details:

Let $\mathbf X = X_1,...,X_n$ be $n$ i.i.d. real-valued random variables where $X_i \in [a,b]$ and $\mu = \mathbf E[X_1]$. For $\delta\in(0,1)$, let $f(\mathbf X, \delta)$ be a function such that:

$$\Pr\left (\left | \mu -\frac{1}{n} \sum_{i=1}^n X_i \right | \leq f(\mathbf X, \delta) \right ) \geq 1-\delta \tag{*}$$

For example, if using Hoeffding's inequality, then $f(\mathbf X, \delta) := (b-a)\sqrt{\frac{\ln(1/\delta)}{2n}}$. However, we do not assume that $f$ uses Hoeffding's inequality - it is any $f$ that makes the above equation hold given our assumptions.

The question: Can we conclude that therefore the one-sided bound also holds with $f/2$? That is:

$$\Pr\left ( \mu -\frac{1}{n} \sum_{i=1}^n X_i \leq \frac{1}{2}f(\mathbf X, \delta) \right ) \geq 1-\delta \tag{**}$$

This holds for Hoeffding's inequality, but does it hold in general?

The answer is negative. Indeed, for simplicity, let $a=-1$ and $b=1$.
In the case when $\delta=1/10$, $n=1$, and $X_1$ is uniformly distributed on $[-1,1]$ (so that $\mu=0$), let $f(\mathbf X,\delta):=1-1/10$. Then $\Pr\left (\left | \mu -\frac{1}{n} \sum_{i=1}^n X_i \right | \leq f(\mathbf X, \delta) \right ) = \Pr(|X_1|\le1-1/10) = 1-1/10=1-\delta$, so that $(*)$ holds -- whereas $$\Pr\left ( \mu -\frac{1}{n} \sum_{i=1}^n X_i \leq \frac{1}{2}f(\mathbf X, \delta) \right ) =\Pr\left(X_1\ge-\frac12\,(1-1/10)\right)=29/40$$ $$\not\geq 1-1/10=1-\delta ,$$ so that $(**)$ fails to hold.
In all cases other than the one just considered, let e.g. $f(\mathbf X, \delta) := b-a$, so that $(*)$ hold.
• Thanks for the counterexample. What did you mean by the last line of your answer? Yes, that $f$ makes $(*)$ hold, but why do you bring this up? Jun 29 '16 at 15:22
• I thought you wanted $f(\mathbf X, \delta)$ to be defined for all $n$, $\mathbf X=(X_1,\dots,X_n)$, and $\delta\in(0,1)$. That is why I wrote the last line, to complement the definition of $f(\mathbf X, \delta)$ in the particular case considered first. Jun 29 '16 at 15:45
• Ah, I see - "all cases other than the one considered" is referring to $n>1$. Thanks. Jun 29 '16 at 16:26
• More precisely, "all cases other than the one considered" refers to the negation of the conjunction of the conditions that $\delta=1/10$, $n=1$, and $X_1$ is uniformly distributed on $[-1,1]$. Jun 29 '16 at 19:56