All Questions
41 questions
24
votes
1
answer
1k
views
A Rademacher ‘root 7’ anti-concentration inequality
Let $r_1,r_2,r_3,\dotsc$ be an IID sequence of Rademacher random variables, so that $\mathbb P(r_n=\pm1)=1/2$, and $a_1,a_2,\dotsc$ be a real sequence with $\sum_na_n^2=1$. For $S=\sum_na_nr_n$, does ...
- 17.1k
10
votes
3
answers
4k
views
Extension of the Azuma-Hoeffding inequality (when the differences are bounded with large probability)
Let $(X_i)$ be a super-martingale and suppose their differences are bounded ''with high probability'', that is
$$\mathbb{P}(\exists\,i=1,\dots,n\text{ s.t. }|X_i-X_{i-1}|>c_i) \,\leq\, \epsilon$$
...
- 223
8
votes
2
answers
486
views
concentration inequality for entropy from sample
Consider a measure $\mu$ on a finite set, and let $x_1, \ldots, x_n$ be i.i.d samples from $\mu$. Then the expression $S_n = -\frac{1}{n} \sum_{i=1}^n \log \mu(x_i)$ converges by a.s. to the entropy $...
- 83
5
votes
1
answer
225
views
Anti-concentration of Gaussian when conditioning on event
Let $v$ be a given vector with $\|v\|_{\Sigma^{-1}} \leq 1$, where $\Sigma$ is a positive semi-definite matrix and $\|v\|_{\Sigma^{-1}} = \sqrt{v^\top\Sigma v}$. Meanwhile, let $u$ be a random vector ...
- 1,127
4
votes
1
answer
1k
views
Does variants of Bernstein and Freedman concentration inequalities exist with NO uniform bound on the range of RV or martingale differences
A classic formulation of the Bernstein inequality (from Wikipedia) is as follow:
Let $X_1, \ldots, X_n$ be independent zero-mean random variables. Suppose that $|X_i|\leq M$ almost surely, for all $i$...
- 53
4
votes
1
answer
474
views
Concentration inequalities in $\ell_{\infty}$ for sums of iid random ("nice") functions?
I'm looking for "tail-bound-like" inequalities that look like this (I state a specific setting but more general settings are interesting):
Let $D$ be a distribution on a set of "nice" functions $g$:...
- 4,529
4
votes
1
answer
320
views
Sub-Gaussian random variables and convex ordering
Suppose that $X$ is a $1$-sub-Gaussian real-valued random variable, i.e. for all $t \in \mathbf{R}$, it holds that $\log \mathbf{E} \exp \left( t X \right) \leqslant \frac{1}{2} t^2 $.
Does there ...
- 801
4
votes
1
answer
206
views
Inner product of sorted Gaussian vector
Suppose $X_1,\ldots,X_n$ are i.i.d. standard normal. I'm wondering how to analyze the following quantity:
$$\left|\frac{X_{(1)}X_{(n)}+X_{(2)}X_{(n-1)}+\cdots+X_{(n)}X_{(1)}}{n}\right|$$
where $X_{(1)}...
- 1,495
4
votes
1
answer
347
views
Concentration of functional of Gaussian random variable
Suppose I have two Gaussian distributions
$p(x) = \frac{1}{(2\pi)^{d/2}|\Sigma_p|^{1/2}}\exp(-\frac{1}{2}x^\top \Sigma_p^{-1} x)$ and $q(x) = \frac{1}{(2\pi)^{d/2}|\Sigma_q|^{1/2}}\exp(-\frac{1}{2}x^\...
- 515
4
votes
0
answers
141
views
Is there an example that both Berry-Essen bound and DKW bound are attained?
The Berry-Essen bound stated that
$$\sup _{{x\in {\mathbb R}}}\left|\widehat{F_{n}(x)}-\Phi (x)\right|\leq C_{0}\cdot \psi _{0}$$
where $\psi _{0}(n)={\Big (}{\textstyle \sum \limits _{{i=1}}^{n}\...
- 8,071
3
votes
1
answer
1k
views
concentration inequality for averages of dependent random variables
Let $X \in R^n$ be a random vector such that
$$P(|X_i| > \epsilon) > e^{-\epsilon^2}$$
What is a tight bound on
$$P(\sum_{i=1}^n |X_i| > \epsilon)$$
and on
$$P(\max_{1\le i\le n} |X_i| ...
- 461
3
votes
2
answers
636
views
Exponential inequality for the sum of martingale differences $X_1, \dots, X_n$ when $\sum_{i=1}^{n} \operatorname{Var}(X_i) \leq B^2$
Let $X_1, X_2, \dots, X_n$ be a martingale difference sequence such that
$$
X_i \leq y \quad \text{and} \quad \sum_{i=1}^{n} \operatorname{Var}(X_i) \leq B^2.
$$
Question 1: Does the following hold?
$$...
- 33
3
votes
2
answers
402
views
Something between the Chernoff and Hoeffding bounds
Suppose I have $n$ independent 0-1 random variables $X_1, \cdots, X_n$ and I want to show a concentration of $X = \sum_i X_i$.
I can use either the Chernoff bound or the Hoeffding bound.
Suppose $E[...
- 233
3
votes
1
answer
1k
views
Extension of Bernstein’s Inequality when the random variable is bounded with large probability
Bernstein’s Inequality can be stated as follows : Let $x_1, x_2, \dots, x_n$ be independent bounded random variables such that $\mathbb{E}[x_i] = 0$ and $|x_i| \leq \zeta$ with probability $1$ and let ...
- 33
3
votes
1
answer
1k
views
Chernoff-Hoeffding bound for complex values
Consider the Chernoff-Hoeffding bound, stated as follows: Let $X_1, \dots, X_K$ be i.i.d. real-valued random variables with expectation value
$\mu$ and satisfying $|X_i| \le b$.
Let $\epsilon > 0$. ...
- 298
3
votes
1
answer
553
views
How did the story of Kim-Vu type inequalities continue?
I am interested in the concentration of polynomials of random variables. I have been reading Boucheron, Lugosi, and Massart's "Concentration inequalities" and they give some references. ...
- 233
3
votes
0
answers
92
views
Tighter Freedman's inequality for a special martingale difference sequence
Let $X_{1}, \ldots, X_{T} \in \{0, 1\}$ be a sequence of Boolean random variables with
$$
\mathbb{E}[X_{t} | X_{1}, \dots, X_{t - 1}] = p_{t}.
$$
Consider the sequence $Y_{t} := X_{t} - p_{t}$ (which ...
- 41
3
votes
0
answers
77
views
A concentration problem of product of matrices
Let $A$ be an $n \times m$ matrix with non-negative entries and $B \in \mathbb{R^{n\times n}_{\geq 0}}, C \in \mathbb{R^{m\times m}_{\geq 0}}$ be random matrices where B and C are both symmetric and ...
- 195
3
votes
0
answers
125
views
Concentration of sums of random matrices around the mean, in the Loewner order
Recently, I have found myself interested in concentration properties of random matrices.
Specifically I would like to answer questions of the following sort
Let $\{X_i\}_{i=1}^n$ be i.i.d. copies ...
- 393
3
votes
0
answers
451
views
concentration bounds on weighted multinomial sum
Consider i.i.d random vectors $Y_{1},..,Y_{n}$ and they are chosen uniformly at random from $\{e_{1},..,e_{L}\}$ where $e_{i}$ is a $L\times 1$ vector with $i$th component be 1 and the others be 0. ...
- 31
3
votes
1
answer
247
views
Concentration and Correlation for Magnitudes of Gaussian Vectors
Suppose we have a large collection of standard normal random variables $a_i\in\mathbb{R}^n$. We know by standard concentration results that if we take $m \geq C\left(t/\epsilon\right)^2n$ samples, ...
- 205
2
votes
3
answers
184
views
Existence and sharpness of Bernstein-type bounds on the moment-generating function
Let $X$ be a centred random variable with variance $\sigma^2$, and whose moment-generating function exists in an open neighbourhood of the origin.
Say that $X$ satisfies a 'Bernstein-type' MGF bound ...
- 801
2
votes
1
answer
287
views
Bernstein Inequality for continous local martingale
I'm looking for a simple proof of the following fact, which is somehow Bernstein inequality in continuous time.
Let $(M_t)_{t\geq 0}$ be a continuous local martingale. Then :
$$P\left(\sup_{t\in [0,...
- 245
2
votes
1
answer
172
views
Symmetry of concentration bounds on mean
Question summary:
If I have a two-sided bound, can I immediately get a one-sided bound with tighter constants?
Question details:
Let $\mathbf X = X_1,...,X_n$ be $n$ i.i.d. real-valued random ...
- 399
2
votes
1
answer
386
views
A maximal inequality
Let $\{X_i\}_{i\in\mathbb{N}}$ be i.i.d. symmetric random variables, with $-1\leq X_i\leq 1$, $\mathbb{E}(X_i) =0$, $\mathbb{E}(X_i^2) = 1$. We have that:
$$
P\left(\bigcap_{k = 1}^{n}\frac{|\sum_{i = ...
- 63
2
votes
1
answer
119
views
Simultaneous Concentration of $\sum_{i = 1}^{n} X_i^2$ and $\sum_{i = 1}^{n} X_i$ with $X_i$ iid. Poisson
Consider $n$ independent Poisson(1)-distributed random variables $(X_i)_{1 \leq i \leq n}$.
This is a (hopefully more interesting) follow-up question to Super-exponential concentration for $\frac{\...
- 578
2
votes
1
answer
335
views
The lower bound of bivariate normal distribution
Suppose $(Z_1, Z_2)$ is the zero-mean bivariate normal distribution with covariance $\left( \begin{matrix} 1 & \rho; \\ \rho & 1\end{matrix} \right)$ with positive $\rho > 0$. What I want ...
- 331
2
votes
1
answer
271
views
How to compute bounding coefficients for McDiarmid's inequality?
I am trying to understand the proof in Sec. A2 of Gretton et al.. To make the question self-contained, I summarize below the key ingredients. At the end of the post, I state my question.
Given a ...
2
votes
1
answer
150
views
Normalized concentration inequality for empirical CDF (iid sum)
Consider the empirical and population CDF,
$$
F_n(t) = \frac{1}{n} \sum_{i=1}^n 1\{X_i \leq t\} \quad \mbox{and} \quad
F(t) = \mathbb{E} [F_n(t)],
$$
where above $X_1, \dots, X_n$ are iid, real-...
- 420
2
votes
0
answers
124
views
Intuitive (?) inequality extremal inequality
Consider $N$ pairs of random variables $(X_i, Y_i)$. $X_i$ are iid, with $EX_i=0$ and $EX_i^2=1$. The same conditions hold for $Y_i$. Moreover all $X_i$ are independent of all $Y_j$. It seems very ...
- 461
1
vote
1
answer
365
views
Lower-bound probability of non-centered quadratic form
Let $X\sim N(\mu,\sigma^2I)\in \mathbb{R}^n$ be a non-centered ($\mu\neq 0$) Gaussian vector with independent coordinates. I'm wondering if there is any sharp lower bound of the following probability:
...
- 1,495
1
vote
1
answer
249
views
On concentration of a sum random variable
Take a random variable defined as
$$r=u_{11}v_{1}v_{1}+u_{12}v_{1}v_{2}+\dots+u_{n,n-1}v_{n}v_{n-1}+u_{nn}v_{n}v_{n}$$ where $v_{i}$ are independent uniform random variables from $\{0,\dots,b\}$, $u_{...
- 13.9k
1
vote
1
answer
67
views
Lower-bound for $\mathbb E[e^{-b(v^\top X - c)^2}]$, when $X$ is log-concave in high-dimensions
Let $d$ be a large positive integer. Fix a unit-vector $v \in \mathbb R^d$, and scalars $b,c \in \mathbb R$ with $b > 0$. Let $X$ be a log-concave random vector in $\mathbb R^d$ normalized so that ...
- 6,853
1
vote
1
answer
313
views
Bounds on difference between "logsumexp" and variance?
Let $Z$ be a random variable with finite moment-generating function $M_Z(\theta):=E[e^{\frac{1}{\theta}Z}]<\infty$ for all $\theta > 0$, and for $\delta \in (0,1]$, define
$C_Z^\delta := \inf_{\...
- 6,853
1
vote
0
answers
370
views
Lower bound on the sum of the product of random variables
Let $X_i$ be the $i$-th element of the vector $X=(X_1, ..., X_m)$ of i.i.d. random variables.
I am looking for a lower bound for the expression
$\mathbb{P}((\sum^n_{i=1}\prod^{m_i}_{j=1}(X_j))^2 \geq ...
- 129
1
vote
0
answers
376
views
Anti-concentration bounds for folded normal and inverse of gaussian variables
Are there any easy to use bounds on sums of the following kind :
$$
\sum_{i = 1}^{i = N} |a_i| \geq P \\
a_i \sim \mathcal{N}(0, 1) \\
$$
and also for sums of the form :
$$
\sum_{i = 1}^{i = M} \...
- 111
1
vote
0
answers
110
views
Tail bound without independence
Suppose $X_i , X_j\in \mathbb{R}^d$ are gaussian vectors and $A$ is an $n\times n$ symmetric PSD matrix where $A_{ij} = f(\|X_i-X_j\|_2), \quad i,j\in 1,\ldots,n\;$ for some non-negative Lipschitz ...
- 195
0
votes
2
answers
280
views
Bounds tighter than the additive Chernoff
Additive Chernoff
Suppose $X_1, \ldots, X_n$ are i.i.d. random variables, taking values in $\{0,1\}$. Let $p=\mathrm{E}\left[X_i\right]$ and $\varepsilon>0$.
\begin{gather*}
\operatorname{Pr}\left(\...
- 105
0
votes
1
answer
182
views
Deducing norm concentration from MGF bounds
Suppose that $X$ is a centered, $\mathbf{R}^d$-valued random variable such that for all $t \in \mathbf{R}^d$, there holds the bound $$\log \mathbf{E} \left[ \exp \langle t, X \rangle \right] \leqslant ...
- 801
0
votes
1
answer
966
views
Bound the norm of sum of random vector that generated from standard basis
I have a question like this:
Consider $N$ samples $X_1, X_2, ..., X_N$ that uniformly random generated from standard basis $\{e_i, i=1,2,...,d\}$, i.e. $(1,0,0,\cdots,0),(0,1,0,\cdots,0),(0,0,1,0,\...
- 25
0
votes
0
answers
293
views
Can we prove the following anti-concentration inequality of polynomials of square Gaussian variables?
Following this question Anti-concentration of Gaussian quadratic form. We have the following inequality:
Let $X_1,\dots,X_n$ denote i.i.d. standard Gaussian random variables. For every $\epsilon>0$...
- 288