2
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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