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-...
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}$...
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 ...
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 ...
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=\...
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 ...
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 ...
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$-...
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+\...
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 ...
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})...
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\...
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 ...
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 ...
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 ...
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 ...
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:=...
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) = \...
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 $\...
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