14
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-...
- 128k
11
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 ...
- 114k
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|) +\...
- 14.2k
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 ...
- 128k
7
votes
Why sum of samples without replacement is more concentrated than with replacement?
the variance of $Y$ is smaller than the variance of $X$ by a factor $\sqrt{1-\frac{n-1}{N-1}}$; for a derivation, see for example section 1.2 of these notes.
- 188k
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,897
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 ...
- 61.9k
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=\...
- 128k
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 ...
- 128k
7
votes
Accepted
Weak concentration bounds for averages of independent random variables in Orlicz spaces
In general, the answer is no. Moreover, the answer is no even if
\begin{equation}
\phi(t)=t\ln(1+t). \tag{1}
\end{equation}
Indeed, suppose that $P(Z_i=0)=1-2p$ and $P(Z_i=b)=p=P(Z_i=-b)$ for all $...
- 128k
7
votes
Accepted
Lower tail of random rank one sums?
Warning: This is not a proper answer, just a dump of the thoughts I have had about this problem so far. Also, I'm not an expert in random matrix theory, so some bounds I'll be using may cry for ...
- 61.9k
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 ...
- 128k
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 [...
- 8,071
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 $...
- 61.9k
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$-...
- 128k
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+\...
- 128k
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 ...
- 128k
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})...
- 128k
6
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 ...
- 61.9k
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\...
- 128k
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
Polynomial Markov versus Chernoff Bound for random variables
Let $b$ denote the LHS. Expanding $e^{\lambda X}$ in a power series you can deduce that
$$E(e^{\lambda X}) \ge \sum_{k \ge 0} \frac {b \lambda^k \delta^k}{k!}=b e^{\lambda \delta} \,.$$
- 14.2k
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 ...
- 128k
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 ...
- 29.7k
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:=...
- 128k
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,514
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) = \...
- 29.7k
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 $\...
- 128k
5
votes
Accepted
Gaussian concentration inequality
This inequality is false. E.g., consider the random vector $X_n:=(Z_1,\dots,Z_n)/\sqrt n$ in $\mathbb R^n$ with the Euclidean norm $\|\cdot\|$, where $Z_1,Z_2,\dots$ are independent standard normal ...
- 128k
5
votes
Accepted
Concentration inequality for the supremum of $L_2$ norm of a vector-valued Gaussian process with iid components
Consider the real-valued centered Gaussian process $(X_{t,a}\colon(t,a)\in T\times B_k)$, where
$$X_{t,a}:=\sum_{j\in[k]}a_j f_j(t),$$
$T:=\Omega$, $B_k$ is the unit ball in $\mathbb R^k$, and $[k]:=\{...
- 128k
Only top scored, non community-wiki answers of a minimum length are eligible