Consider a random variable $X$ whose variance is large. As a contrast to Markov's or Chebyshev's inequality, both of which measure the concentration of a probability distribution, is there a measure of how "spread out" a distribution is? more specifically, I would like to have an inequality of the following sort: $$ \Pr[|X-\mu|<r]\leq f(r) $$ where $\mu=\mathbb{E}[X]$ and $f$ is some increasing function. This should be read: the probability of $X$ being close to its expectation is small.

A case of particular interest to me is the following. Let $X=\sum_{i=1}^n X_i$ where $X_1,...,X_n$, are i.i.d. and non-constant. This time let $r$ be fixed, and I would like to have a bound that depends on the number of summands $n$: $$ \Pr[|X-\mu|<r]\leq f(n) $$ where $f$ goes to zero as $n$ goes to infinity.

In fact, it is my intuition that for any fixed $C\in\mathbb{R}$ and $r>0$ it should be true that $$ \Pr[|X-c|<r]\leq f(n) $$ where $f$ goes to zero as $n$ goes to infinity, since as we have more summands, $X$ is more "smoothened out".

  • 1
    $\begingroup$ I think you need to clean-up the formulation of the question. In the inequality you seek is X the sum of $n$ i.i.d. r.v.-s? Is this the only case you are interested? (Otherwise I would not know what to make of $n$.) Do you really mean for any $C,R>0$? The order of quantifiers in a statement is very important. If you expect meaningful answers, you need to ask unambiguous questions. $\endgroup$ – Liviu Nicolaescu Dec 21 '15 at 11:57
  • $\begingroup$ Did you try to play with Young's convolution inequalities with optimal constants, and its relatives - entropy power, Brascamp-Lieb, etc.? I don't know of a fully general answer to your question, but, e.g., if the distribution of $X_1$ has bounded density then one using Young's inequality with the optimal constant I can get the bound $\mathsf{P}\{|X| \le 1\} = O(1/\sqrt n)$. $\endgroup$ – Alexander Shamov Dec 21 '15 at 12:32
  • $\begingroup$ @Alexander Shamov: No. I guess I'm not familiar with those. So: Young's inequality, and what else should I explore? thanks! $\endgroup$ – Snoop Catt Dec 21 '15 at 12:58
  • $\begingroup$ I just posted my calculation as an answer. $\endgroup$ – Alexander Shamov Dec 21 '15 at 12:59

Here is one crude calculation. The claim is that if the distribution of $X$ has bounded density $f$ then $\sup_c \mathsf{P}\{|X - c| \le 1\} = O(1/\sqrt n)$. The assumption is probably far too strong, but the $1/\sqrt{n}$ asymptotics is clearly optimal, by comparing to the Gaussian.

Let $\gamma_{\sigma^2}$ be the Gaussian of variance $\sigma^2$, and denote by $\Vert \cdot \Vert_p$ the $L^p$ norm for $1 \le p \le \infty$. I will use Young's convolution inequality in the form

$$\Vert f_1 \ast \dots \ast f_n \Vert_{q} \le \frac{C_{p_1} \dots C_{p_n}}{C_q} \Vert f_1 \Vert_{p_1} \dots \Vert f_n \Vert_{p_n},$$ $$1/q + n - 1 = 1/p_1 + \dots + 1/p_n$$ where $C_p^2 = \frac{|p|^{1/p}}{|p^\prime|^{1/p^\prime}}$, $1/p + 1/p^\prime = 1$, and in the limiting case $C_\infty = 1$

(see e.g. Gardner "The Brunn-Minkowski inequality")

By this inequality for $p_1 = \dots = p_n = \frac{n}{n-1}, q = \infty$, $$\Vert f^{\ast n} \ast \gamma_1 \Vert_\infty = \Vert (f \ast \gamma_{1/n})^{\ast n} \Vert_\infty \le \frac{C_{\frac{n}{n-1}}^n}{C_\infty} \Vert f \ast \gamma_{1/n} \Vert_{\frac{n}{n-1}}^n$$

By an explicit calculation, $$C_{\frac{n}{n-1}}^n = \left( \frac{\left(1 - \frac{1}{n}\right)^{-(n-1)}}{n} \right)^{1/2} \sim \sqrt{e / n}$$

On the other hand, by Holder, $\Vert f \ast \gamma_{1/n} \Vert_{\frac{n}{n-1}} \le \Vert f \ast \gamma_{1/n} \Vert_\infty^{1/n} \le \Vert f \Vert_\infty^{1/n}$, so if $f$ is bounded then $$\Vert f^{\ast n} \ast \gamma_1 \Vert_\infty = O(1 / \sqrt n) $$

In particular, on bounded intervals the mass of $f^{\ast n}$ is at most $O(1/\sqrt n)$.

| cite | improve this answer | |

What you need is a standard inequality for the concentration function for sums of independent random variables; see e.g. [Petrov], Ch. III, Section 2, Theorem 3 (due to Esseen), which implies the following.

For a random variable (r.v.) $X$ and real $c>0$, let $$Q(X;c):=\sup_{x\in\mathbb R} P(x\le X\le x+c). $$ Let $S_n:=X_1+\dots+X_n$, where $X,X_1,\dots,X_n$ are any independent identically distributed r.v.'s. Then for any real $c>0$ $$Q(S_n;c)\le \frac A{\sqrt{n D(\tilde X;c)}}, $$ where $A$ is a universal constant, $\tilde X:=X-X_1$,
$$D(\tilde X;c):=\frac1{c^2}\,E\,\tilde X^2\,I\{|\tilde X|<c\}+P(|\tilde X|\ge c)=E\Big(1\wedge\frac{\tilde X^2}{c^2}\Big), $$ and $I\{\cdot\}$ is the indicator function. Note that, for any real $c>0$, one has $D(\tilde X;c)=0$ iff $P(\tilde X=0)=1$ iff the r.v. $X$ is degenerate (i.e., $P(X=a)=1$ for some real $a$). Hence, if $X$ is non-degenerate, then $D(\tilde X;c)\in(0,\infty)$.

A simpler but a bit less precise bound is due to [Rogozin]: $$Q(S_n;c)\le \frac A{\sqrt{n(1-Q(X;c))}}. $$

Addendum: If you only care about the concentration of $S_n$ around its expectation, you may want to use a Berry--Esseen type of bound (see e.g. Theorem 7 in [3] ), which implies $$P\Big(\Big|\frac{S_n-n\mu}{\sigma}\Big|\le c\Big)\le P\Big(|Z|\le\frac c{\sqrt n}\Big)+A\frac{\beta}{\sigma^3\sqrt n} \le\frac C{\sqrt n}, $$ where $\mu:=EX_1$, $\sigma:=\sqrt{E(X_1-\mu)^2}$, $\beta:=E|X_1-\mu|^3$, $c\in[0,\infty)$, $Z$ is a standard normal r.v.,
$C:=\frac{2c}{\sqrt{2\pi}}+A\frac{\beta}{\sigma^3}$, and $A\in(0,96/100)$ is a universal constant. Similar but more direct and a bit more general bounds on the concentration are given e.g. in Proposition 6.1 in [4] and Proposition 2.1 in [5].

All these bounds are of the optimal order $O(1/\sqrt n)$ in $n$. It cannot be improved in general even for the concentration of $S_n$ around its expectation. E.g., let $P(X_i=\pm1)=1/2$. Then, by Stirling's formula, $P(S_{2n}=0)>A/\sqrt n$ for some universal constant $A>0$.

| cite | improve this answer | |
  • 1
    $\begingroup$ I have added a simpler but less precise bound. $\endgroup$ – Iosif Pinelis Dec 21 '15 at 17:59
  • $\begingroup$ Thanks! that is very helpful. A follow up question: suppose I only care about the concentration around the expectation. Can I get a better bound, say O(1/n^2)? (n is the number of summands) $\endgroup$ – Snoop Catt Dec 22 '15 at 14:35
  • 1
    $\begingroup$ I have added an addendum to address your further questions. $\endgroup$ – Iosif Pinelis Dec 22 '15 at 15:56
  • $\begingroup$ Thanks! another and last question: consider a random variable $X$ (not a sum, just a random variable). I want to say that something like: if the variance of X is large, then $\Pr [ |X-\mu|<1]$ is small. By $\mu$ I mean the expectation of $X$. Is there such an inequality? $\endgroup$ – Snoop Catt Dec 22 '15 at 16:28
  • 2
    $\begingroup$ I do not think that such an inequality could hold. E.g., for $n\ge2$ let $X$ take values $-n,0,n$ with probabilities $1/n,1-2/n,1/n$, respectively, and let $n\to\infty$. Then $Var\,X=2n\to\infty$, whereas $P(|X-\mu|<1)\ge P(X=0)=1-2/n\to1$. $\endgroup$ – Iosif Pinelis Dec 22 '15 at 18:24

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.