13
votes

Accepted

### Violating the Lebesgue density theorem

It is a theorem of Besicovitch that measures on $\mathbb R^d$ do satisfy the density theorem.
Fremlin, Measure Theory, Chap. 47
added
Besicovitch, around 1930, extended his density ...

- 38.8k

13
votes

Accepted

### What is (approximately) the expected value of $X\log{ X}$ where $X$ is binomial (or Poisson)?

$\newcommand{\ep}{\varepsilon}
$
Let $X$ be any nonnegative random variable (r.v.) with finite mean $\mu>0$ and variance $\sigma^2<\infty$. For any real $u>0$, we have $\ln\frac xu\le\frac xu-...

- 90.3k

11
votes

Accepted

### Concentration bounds for martingales with adaptive Gaussian steps

Observe that $X_n=X_{n-1}(1+Z_n)$ where $\{Z_k\}_{k \ge 1}$ are i.i.d. standard normal. Hence to analyze the asymptotic distribution of $|X_n|$, pass to logarithms, to get $$\log(|X_n|)= \log(|X_1|) +\...

- 13.5k

9
votes

### Adaptive version of the Azuma–Hoeffding inequality

This inequality cannot be true. Let us rewrite it in the more common form
$$P(R_n\ge x)\le e^{-x^2/2} \tag{1}
$$
for $x\ge0$, where $R_n:=S_n/b_n$, $S_n:=\sum_1^n c_iB_i$, $b_n:=\sqrt{\sum_1^n c_i^2}$...

- 90.3k

9
votes

Accepted

### Lower-bound for smallest eigenvalue of random $k \times $k matrix $C(W)$ defined by $C(W)_{i,j} := 2(w_i^\top w_j)^2 + \|w_i\|^2\|w_j\|^2$

We have
$$ C(W) = 2 A \circ A + v v^\top$$
where $v$ is the vector with entries $\|w_i\|^2$, $A$ is the Wishart matrix with entries $w_i^\top w_j$, and $\circ$ is the Hadamard product. From the Schur ...

- 95.1k

8
votes

Accepted

### Can we do better than Azuma-Hoeffding when the variance is small?

Exponential inequalities for sums of independent random variables (r.v.'s) can be extended to martingales in a standard and completely general manner; see Theorem 8.5 or Theorem 8.1 for real-valued ...

- 90.3k

7
votes

Accepted

### Prove an anti-concentration inequality for a martingale

Basically, the proof goes along the following lines:
(1) Take a small $\varepsilon>0$ and show that the expected exit time from the interval $[-\varepsilon\sqrt{vl},\varepsilon\sqrt{vl}]$ is less ...

- 1,827

7
votes

Accepted

### Maximal inequality for the average of i.i.d. random variables

I streamlined my proof a bit so it is postable now :-)
First, a disclaimer. I have no doubt that there is some slick theorem dating back to 1980's that immediately implies what you want and all one ...

- 55.5k

7
votes

Accepted

### Is there an i.i.d sequence in the unit cube $[-1,1]^d$ with $\mathbb E \left[ \Big \| \sum_{i=1}^N X_N \Big \|_\infty\right] = \sqrt {dN}$?

Let $X_i=(X_{i,1},\dots,X_{i,d})$, $S:=(S_1,\dots,S_d)$, $S_j:=\sum_{i=1}^d X_{i,j}/\sqrt n$. Then, by Hoeffding's inequality, for $s\ge0$
$$P(|S_j|\ge s)\le2e^{-s^2/2},$$
whence
$$E\|S\|_\infty=\...

- 90.3k

7
votes

Accepted

### Concentration inequalities for very rare events on a multiplicative scale

Let $n:=N$. Let us show that for all natural $n$ and all $p\in(0,1)$
$$P(A_n>\sqrt p)\le\frac{\sqrt p+p}{1+p},\tag{1}$$
so that $P(A_n>\sqrt p)\to0$ whenever $p\downarrow0$.
Consider first the ...

- 90.3k

6
votes

### How fast can extreme eigenvalues of the average of random matrices converge to their expectation?

A possible relevant post What kind of random matrices have rapidly decaying singular values?. In that post I discussed the distribution of maximal eigenvalue of a random matrix based on the result [...

- 7,613

6
votes

Accepted

### Concentration bounds on weighted sum of i.i.d. Bernoulli random variables

An almost complete answer. First of all, indeed the $\lVert \alpha\rVert_2$-based bound mentioned in the question can be shown to be tight for many "simple" $\alpha$'s, such as balanced, or uniform/...

- 1,262

6
votes

Accepted

### On the 1/2 assumption on concentration of measure for continuous cube

By the Tsirel’son--Ibragimov--Sudakov argument, reviewed on the first page in Bobkov,
pushing the measure forward from the cube to the canonical Gaussian on $\mathbb R^n$ and using the Gaussian ...

- 90.3k

6
votes

Accepted

### Variance modulo 1

On the one hand, the proof is very cheap. Let $Z_j=e^{2\pi iX_j}$. $X=\sum_j X_j$, $Z=e^{2\pi i X}$. Note that $\operatorname{Var}_{\mathbb R/\mathbb Z}X\approx 1-|EZ|$ and similarly for $X_j$ and $...

- 55.5k

6
votes

Accepted

### Tail probability of random projection

$\newcommand{\R}{\mathbb{R}}
\renewcommand{\P}{\operatorname{\mathsf P}}
\newcommand{\Ga}{\Gamma}
\newcommand{\de}{\delta}$
In view of the spherical symmetry of the distribution of the $l$-...

- 90.3k

6
votes

Accepted

### Distribution of the individual coordinates of a uniform random vector on a high-dimensional sphere

Without loss of generality, $R=1$.
Let $Z_1,\ldots,Z_n$ be iid standard normal random variables (r.v.'s). Then
\begin{equation}
\sqrt n\, X_1\overset{\text{D}}=\frac{\sqrt n\,Z_1}{\sqrt{Z_1^2+\...

- 90.3k

6
votes

### Concentration inequality for the law of iterated logarithm

As was noted in the comments by Yuval and Kevin, even if $X_1$ is bounded, the best upper bound on the probability in question is a negative power of $\ln n$. To get such a bound (and even an ...

- 90.3k

6
votes

Accepted

### Central limit theorem for resampling

First, we need to fix the notation a bit. Let $X_1,X_2,\dots$ be iid zero-mean unit-variance random variables (r.v.'s). For each natural $n$, let the $n$-tuple $(J_1,\dots,J_n):=(J_{n,1},\dots,J_{n,n})...

- 90.3k

6
votes

Accepted

### Chernoff-type bounds for a stopped sum of independent random variables

The desired statement will not hold. E.g., suppose that $n\ge2$; $X_1,\dots,X_n,Y_1,\dots,Y_n$ are independent; $p=1/2$; $T=1_{X_1\ne Y_1}+n1_{X_1=Y_1}$; and $\delta=1/2$. Then $\mu:=p\,ET>n/4\to\...

- 90.3k

6
votes

Accepted

### A Rademacher ‘root 7’ anti-concentration inequality

Addressed in Theorem 1.3 in Dvořák and Klein - Probability mass of Rademacher sums beyond one standard deviation (not yet peer reviewed). It describes a computer program that verifies $\Pr[\lvert S\...

- 176

6
votes

Accepted

### Concentration Inequality for Bounding Lipschitz Empirical Lass

Your inequality is trivial and useless as written. On its left-hand side we have a probability which is $\le1$ and goes to $0$ as $t\to\infty$, whereas on the right-hand side we have an expression ...

- 90.3k

5
votes

### concentration inequality for entropy from sample

Here's a step that seems nice enough to point out. It still leaves a parameter to pick, and I'm not sure it's ever better than applying Bernstein, but it does something different.
We can get a ...

- 4,220

5
votes

Accepted

### concentration inequality for entropy from sample

Actually, Bernstein's inequality does not really require boundedness of the i.i.d. random summands; a finite exponential moment of the absolute value of a random summand will suffice. However, here we ...

- 90.3k

5
votes

Accepted

### Minimum separation among $m$ random points on an $n$-dimensional unit sphere

The preprint "Random Point Sets on the Sphere --- Hole Radii, Covering, and Separation" by Johann S. Brauchart, Edward B. Saff, Ian H. Sloan, Yu Guang Wang, and Robert S. Womersley gives the following ...

- 5,868

5
votes

### Large deviation/concentration inequality for submartingale

This looks like a weak law of large numbers, and in fact a strong law holds: I claim that $\liminf_{t \to \infty} \frac{S_t}{t} \ge \Delta$ almost surely, which implies the desired result.
The key is ...

- 28.1k

5
votes

### Martingale version of Bernstein-type inequality for (slightly) heavy-tailed distributions?

This is worked out in some detail in the paper of Fan, Grama and Liu,
J. Math Anal. Appl. 448 (2017), 538-566 (see in particular Theorem 2.1 there, and the references). Unfortunately I do not have an ...

- 7,184

5
votes

Accepted

### Does variants of Bernstein and Freedman concentration inequalities exist with NO uniform bound on the range of RV or martingale differences

It appears you want to have the following:
Let $X_1,\dots,X_n$ be independent zero-mean random variables (r.v.'s ) (or, more generally, martingale-differences) with $S_n:=X_1+\dots+X_n$, $B^2:=...

- 90.3k

5
votes

### A distribution which is Wasserstein-close to a compactly supported distribution is almost compactly supported

The claimed inequality is not true. The simplest possible counterexample works: let $x,y \in \mathbb{R}^n$ with $|x-y| = \epsilon$, and take $\mu = \delta_x$, $\nu = \delta_y$. Then $W_1(\mu,\nu) = \...

- 28.1k

5
votes

Accepted

### Good upper-bound for $\mathbb E[|X-np|^r]$ where $X \sim \text{Binomial}(n,p)$ and $r \ge 1$

By the main result of the paper Exact Rosenthal-type bounds, we have
$$E|X-np|^r\le c^r E|\Pi_\lambda-\lambda|^r
$$
for real $r\in(2,\infty)\setminus(3,4)\setminus(4,5)$, where real $c>0$ and $\...

- 90.3k

5
votes

Accepted

### Concentration of sum of concentrated random variables

There is a bad news and a good news. The bad one is that if you have no information other than that the probability of the $\varepsilon$-deviation is at most $p$ for each variable, then you can hardly ...

- 55.5k

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

measure-concentration × 340pr.probability × 281

st.statistics × 85

probability-distributions × 58

random-matrices × 58

inequalities × 38

stochastic-processes × 31

geometric-probability × 27

reference-request × 25

gaussian × 24

measure-theory × 23

fa.functional-analysis × 17

martingales × 17

convex-geometry × 13

asymptotics × 10

limits-and-convergence × 10

co.combinatorics × 9

mg.metric-geometry × 9

geometric-measure-theory × 9

linear-algebra × 8

optimal-transportation × 8

isoperimetric-problems × 8

large-deviations × 8

lower-bounds × 7

learning-theory × 7