# A measure of how “spread out” a probability measure is

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

• 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. – Liviu Nicolaescu Dec 21 '15 at 11:57
• 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)$. – Alexander Shamov Dec 21 '15 at 12:32
• @Alexander Shamov: No. I guess I'm not familiar with those. So: Young's inequality, and what else should I explore? thanks! – Chipotle Dec 21 '15 at 12:58
• I just posted my calculation as an answer. – 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)$.

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

• I have added a simpler but less precise bound. – Iosif Pinelis Dec 21 '15 at 17:59
• 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) – Chipotle Dec 22 '15 at 14:35
• 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? – Chipotle Dec 22 '15 at 16:28
• 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$. – Iosif Pinelis Dec 22 '15 at 18:24