5
$\begingroup$

In probability and statistics Orlicz norms are frequently used in concentration inequalities. For example, for Bernstein's inequality, we have versions for sub-exponential random variables using $\psi_1$-norm and for bounded random variables using variance.

My first thought is that the $\psi_1$-norm version is more general, and includes the case of bounded random variables as a special case. However, an example of Bernoulli random variable with probability $1/n$ being $1$ and $1-1/n$ being $0$ suggests this is not true. For $n$ very large, the variance is roughly of the order $1/n$. However, its $\psi_1$-norm is roughly of the order ${1}/{\log n}$.

This suggests that $\psi_1$-norm (or similarly, $\psi_2$-norm) is actually very loose for very biased Bernoulli random variables. Is there any other notions like $\psi_1$-norm that can accommodate biased Bernoulli random variables?

Improve this question
$\endgroup$
17
  • 1
    $\begingroup$ crossposted on math.stackexchange $\endgroup$
    – kodlu
    Commented Nov 3, 2015 at 23:03
  • $\begingroup$ Does the Bernstein-Orlicz norm from this paper answer your question: arxiv.org/pdf/1111.2450v2.pdf? They define an Orlicz norm that is equivalent to Bernstein-type concentration bounds, and do give the classical Bernstein inequality for sums of independent random variables. $\endgroup$
    – Sasho Nikolov
    Commented Nov 4, 2015 at 1:47
  • $\begingroup$ @kodlu I have deleted the question at math overflow $\endgroup$
    – Minkov
    Commented Nov 4, 2015 at 3:37
  • $\begingroup$ @SashoNikolov The Bernstein-Orlicz norm (equation (1)) is basically a interpolation between $\psi_2$-norm and $\psi_1$-norm. For the Bernoulli random variable "very biased" towards $0$, the $\psi_2$-norm is also much larger than $1/n$ (also roughly of the order $1/\log n$) $\endgroup$
    – Minkov
    Commented Nov 4, 2015 at 3:42
  • 1
    $\begingroup$ See the Kearns-Saul inequality for the optimal subgaussian constant of biased Bernoullis: ecp.ejpecp.org/article/view/2359 $\endgroup$
    – Aryeh
    Commented Nov 6, 2015 at 6:59

1 Answer 1

Reset to default
3
$\begingroup$

The Kearns-Saul inequality states that if $X\sim Ber(p)$ then $$ E[\exp(t(X-p))] = (1-p)e^{-tp}+pe^{t(1-p)} \le \exp\left(\frac{1-2p}{4\log((1-p)/p)}t^2\right).$$

The subgaussian constant $\frac{1-2p}{4\log((1-p)/p)}$ is optimal. See http://ecp.ejpecp.org/article/view/2359 and especially the appendix in http://www.jmlr.org/papers/v16/berend15a.html for background and a slick proof.

The K-S inequality is a considerable improvement over Hoeffding and Bernstein for very small/large $p$.

Improve this answer
$\endgroup$

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.