# Orlicz norm of random variable and variance

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?

• crossposted on math.stackexchange Nov 3 '15 at 23:03
• 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. Nov 4 '15 at 1:47
• @kodlu I have deleted the question at math overflow Nov 4 '15 at 3:37
• @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$) Nov 4 '15 at 3:42
• See the Kearns-Saul inequality for the optimal subgaussian constant of biased Bernoullis: ecp.ejpecp.org/article/view/2359 Nov 6 '15 at 6:59

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$.