4
$\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?

$\endgroup$
  • 1
    $\begingroup$ crossposted on math.stackexchange $\endgroup$ – kodlu Nov 3 '15 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 Nov 4 '15 at 1:47
  • $\begingroup$ @kodlu I have deleted the question at math overflow $\endgroup$ – Minkov Nov 4 '15 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 Nov 4 '15 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 Nov 6 '15 at 6:59
2
$\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$.

$\endgroup$

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.