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.

  • $\begingroup$ 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? $\endgroup$
    – PThomasCS
    Jun 29 '16 at 15:22
  • $\begingroup$ 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. $\endgroup$ Jun 29 '16 at 15:45
  • $\begingroup$ Ah, I see - "all cases other than the one considered" is referring to $n>1$. Thanks. $\endgroup$
    – PThomasCS
    Jun 29 '16 at 16:26
  • $\begingroup$ 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]$. $\endgroup$ Jun 29 '16 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.