<p>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).$$</p>

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

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

CC BY-SA 3.0
2015-11-06T07:09:16.073Z
2015-11-06T07:09:16.073Z
Aryeh
<p>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. </p>

<p>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}$. </p>

<p>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?</p>

CC BY-SA 3.0
2015-11-03T23:03:12.423Z
crossposted on math.stackexchange
kodlu
CC BY-SA 3.0
2015-11-04T01:47:33.237Z
Does the Bernstein-Orlicz norm from this paper answer your question: http://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.
Sasho Nikolov
CC BY-SA 3.0
2015-11-04T03:37:20.343Z
@kodlu I have deleted the question at math overflow
Minkov
CC BY-SA 3.0
2015-11-04T03:42:51.367Z
@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$)
Minkov
CC BY-SA 3.0
2015-11-04T04:51:08.733Z
One thing I don't understand: you don't actually mean Orlicz norms of Bernoulli random variables but rather of the binomial distribution with $p = 1/n$, right? In that case, if you take Corollary 1 from the paper and take each $X_i$ to be $-1/n$ with probability $1-1/n$ and $1-1/n$ with probability $1/n$ (so the Bernoulli r.v. but centered), don't you get that the $\psi_L$ norm is on the order of $1/n$? Do you object to the centering for some reason?
Sasho Nikolov
CC BY-SA 3.0
2015-11-04T05:16:35.663Z
Or actually maybe you do mean the a Bernoulli r.v.? Then the $\psi_q$ norm of a Bernoulli is $\log((1+p)/p)^{-1/q}$ unless I am messing up the calculation. But then I fail to understand the motivation for this question: there is no need for a concentration inequality for something as simple as Bernoulli. And if you mean concentration for sums of Bernoulli, then what you really care about is the Orlicz norm of a binomial r.v. which goes back to my previous comment, no?
Sasho Nikolov
CC BY-SA 3.0
2015-11-04T08:21:01.887Z
@SashoNikolov Actually I am interested in the case where each individual Bernoulli random variable has a very small mean. Sorry for the bad notation, I should have used another letter $m$ instead of $n$. So there is in total $n$ i.i.d. Bernoulli variables, each of them has mean $1/m$. Both $m$ and $n$ are large. My motivation is to understand whether $\psi$-norms are general and tight at the same time. This is an example I come up with. So the $\psi_L$-norm of an individual Bernoulli random variable is still roughly $1/\log m$, while its variance is $1/m$.
Minkov
CC BY-SA 3.0
2015-11-04T08:24:04.583Z
@SashoNikolov If this example is correct, then there might be other examples where $\psi$-norms can be very loose. Motivated by this example, I am trying to find a more refined replacement of $\psi$-norms that is as general but tighter.
Minkov
CC BY-SA 3.0
2015-11-04T09:14:07.153Z
"Tight/loose" with respect to what, standard deviation? Then you can just take the standard deviation ($L_2$ norm: all $L_p$ norms are Orlicz norms). Similarly, "general" in what way? If you dont precisely specify what you want from the norm there is no way to answer your question. And it still makes no sense to me why you take $n$ iid Bernoulli, but then ask about the Orlicz norm of *each one* of them rather than *their sum*. If you ask for the sum, then $\psi_L$ satisfies the property of implying a concentration bound at least as tight as the Bernstein inequality.
Sasho Nikolov
CC BY-SA 3.0
2015-11-04T19:51:56.910Z
@SashoNikolov Yes, I mean with respect to standard deviation. For bounded random variable, there are versions of Bernstein's inequality using variance or $\psi_1$-norm. So in my example, the one using variance is much tighter. This suggests that maybe we should not use the $\psi_1$-norm version of Bernstein's inequality all the time.
Minkov
CC BY-SA 3.0
2015-11-04T20:05:12.017Z
@SashoNikolov I agree with you. Even though I am talking about the $\psi_1$-norm of each random variable, what I eventually use is the sum. But if the $\psi_1$-norm of each random variable is not tight with respect to its variance, the sum should also be not tight.
Minkov
CC BY-SA 3.0
2015-11-05T06:35:25.717Z
I am not convinced that there is anything loose here. $\psi_1$ bounds imply exponential tails, and for a Bernoulli with probability of $1$ equal to $1/n$, the $\psi_1$ norm being $1/\log n$ implies exactly the right probability that the r.v. is $1$. If you look at a binomial r.v. $X$ with constant expectation (so the sum of $n$ Bernoulli, each equal to $1$ w.p. $O(1/n)$), Bernstein's inequality implies $\psi_1$ is constant. This implies $\Pr[X > t] \le \exp(-t)$, which is exactly what Bernstein says for variance this small (the $\exp(-t^2/\sigma^2)$ bound only works for $t\leq \sigma^2$)
Sasho Nikolov
CC BY-SA 3.0
2015-11-05T20:54:20.850Z
@SashoNikolov So which version of Bernstein's inequality are you using here? So maybe I am missing something here. I guess you are referring to the Bernstein's inequality for average of bounded random variable, which involves variance and the support size. You are right, this version is tight.
Minkov
CC BY-SA 3.0
2015-11-05T20:54:54.803Z
@SashoNikolov I am thinking about the Bernstein's inequality involving $\psi_1$-norms of individual random variables, like Proposition 5.16 in this book chapter (http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf). Using this version, since the $\psi_1$-norms of very biased Bernoulli doesn't really reflect the variance, it is loose compared to the aforementioned version that uses variance and support size.
Minkov
CC BY-SA 3.0
2015-11-06T00:08:31.830Z
I understand now: this inequality is indeed loose in your case. Part of the reason must be that the inequality is true for any subexp. r.v.'s while the classical Bernstein ineq. is only true for bounded r.v.'s. I think you should include the reference to Prop. 5.16. in the monograph in your question, to make it clear what you are getting at. Right now it is confusing because $\psi_1$ norm bounds on the sum are essentially equivalent to exponential concentration bounds.
Sasho Nikolov
CC BY-SA 3.0
2015-11-06T05:30:00.960Z
@SashoNikolov Now I see what you mean:) I am curious about a "general" version of Bernstein's inequality that adapts to the two current versions. I am very grateful for your helpful discussion:)
Minkov
CC BY-SA 3.0
2015-11-06T06:59:55.467Z
See the Kearns-Saul inequality for the optimal subgaussian constant of biased Bernoullis: http://ecp.ejpecp.org/article/view/2359
Aryeh
<pr.probability><chernoff-bound>
Orlicz norm of random variable and variance
Minkov
# Orlicz norm of random variable and variance

(Asked by: username_0 on 2015-11-03)

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?

**Tags:** pr.probability, chernoff-bound
> **Comments:**
> **username_1**: crossposted on math.stackexchange  
> **username_2**: Does the Bernstein-Orlicz norm from this paper answer your question: http://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.  
> **username_0**: @kodlu I have deleted the question at math overflow  
> **username_0**: @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$)  
> **username_2**: One thing I don't understand: you don't actually mean Orlicz norms of Bernoulli random variables but rather of the binomial distribution with $p = 1/n$, right? In that case, if you take Corollary 1 from the paper and take each $X_i$ to be $-1/n$ with probability $1-1/n$ and $1-1/n$ with probability $1/n$ (so the Bernoulli r.v. but centered), don't you get that the $\psi_L$ norm is on the order of $1/n$? Do you object to the centering for some reason?  
> **username_2**: Or actually maybe you do mean the a Bernoulli r.v.? Then the $\psi_q$ norm of a Bernoulli is $\log((1+p)/p)^{-1/q}$ unless I am messing up the calculation. But then I fail to understand the motivation for this question: there is no need for a concentration inequality for something as simple as Bernoulli. And if you mean concentration for sums of Bernoulli, then what you really care about is the Orlicz norm of a binomial r.v. which goes back to my previous comment, no?  
> **username_0**: @SashoNikolov Actually I am interested in the case where each individual Bernoulli random variable has a very small mean. Sorry for the bad notation, I should have used another letter $m$ instead of $n$. So there is in total $n$ i.i.d. Bernoulli variables, each of them has mean $1/m$. Both $m$ and $n$ are large. My motivation is to understand whether $\psi$-norms are general and tight at the same time. This is an example I come up with. So the $\psi_L$-norm of an individual Bernoulli random variable is still roughly $1/\log m$, while its variance is $1/m$.  
> **username_0**: @SashoNikolov If this example is correct, then there might be other examples where $\psi$-norms can be very loose. Motivated by this example, I am trying to find a more refined replacement of $\psi$-norms that is as general but tighter.  
> **username_2**: "Tight/loose" with respect to what, standard deviation? Then you can just take the standard deviation ($L_2$ norm: all $L_p$ norms are Orlicz norms). Similarly, "general" in what way? If you dont precisely specify what you want from the norm there is no way to answer your question. And it still makes no sense to me why you take $n$ iid Bernoulli, but then ask about the Orlicz norm of *each one* of them rather than *their sum*. If you ask for the sum, then $\psi_L$ satisfies the property of implying a concentration bound at least as tight as the Bernstein inequality.  
> **username_0**: @SashoNikolov Yes, I mean with respect to standard deviation. For bounded random variable, there are versions of Bernstein's inequality using variance or $\psi_1$-norm. So in my example, the one using variance is much tighter. This suggests that maybe we should not use the $\psi_1$-norm version of Bernstein's inequality all the time.  
> **username_0**: @SashoNikolov I agree with you. Even though I am talking about the $\psi_1$-norm of each random variable, what I eventually use is the sum. But if the $\psi_1$-norm of each random variable is not tight with respect to its variance, the sum should also be not tight.  
> **username_2**: I am not convinced that there is anything loose here. $\psi_1$ bounds imply exponential tails, and for a Bernoulli with probability of $1$ equal to $1/n$, the $\psi_1$ norm being $1/\log n$ implies exactly the right probability that the r.v. is $1$. If you look at a binomial r.v. $X$ with constant expectation (so the sum of $n$ Bernoulli, each equal to $1$ w.p. $O(1/n)$), Bernstein's inequality implies $\psi_1$ is constant. This implies $\Pr[X > t] \le \exp(-t)$, which is exactly what Bernstein says for variance this small (the $\exp(-t^2/\sigma^2)$ bound only works for $t\leq \sigma^2$)  
> **username_0**: @SashoNikolov So which version of Bernstein's inequality are you using here? So maybe I am missing something here. I guess you are referring to the Bernstein's inequality for average of bounded random variable, which involves variance and the support size. You are right, this version is tight.  
> **username_0**: @SashoNikolov I am thinking about the Bernstein's inequality involving $\psi_1$-norms of individual random variables, like Proposition 5.16 in this book chapter (http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf). Using this version, since the $\psi_1$-norms of very biased Bernoulli doesn't really reflect the variance, it is loose compared to the aforementioned version that uses variance and support size.  
> **username_2**: I understand now: this inequality is indeed loose in your case. Part of the reason must be that the inequality is true for any subexp. r.v.'s while the classical Bernstein ineq. is only true for bounded r.v.'s. I think you should include the reference to Prop. 5.16. in the monograph in your question, to make it clear what you are getting at. Right now it is confusing because $\psi_1$ norm bounds on the sum are essentially equivalent to exponential concentration bounds.  
> **username_0**: @SashoNikolov Now I see what you mean:) I am curious about a "general" version of Bernstein's inequality that adapts to the two current versions. I am very grateful for your helpful discussion:)  
> **username_3**: See the Kearns-Saul inequality for the optimal subgaussian constant of biased Bernoullis: http://ecp.ejpecp.org/article/view/2359  

---

## 1 answers

### Answer by username_3 on 2015-11-06. Score: 3 | Accepted answer

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


---

