Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
George Lowther's user avatar
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$$ ...
user118866's user avatar
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 $...
komark's user avatar
  • 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 ...
Minkov's user avatar
  • 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$...
Jean Claude's user avatar
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$:...
usul's user avatar
  • 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 ...
πr8's user avatar
  • 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)}...
neverevernever's user avatar
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^\...
Wuchen's user avatar
  • 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}\...
Henry.L's user avatar
  • 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| ...
gappy3000's user avatar
  • 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? $$...
Siam's user avatar
  • 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[...
user2316602's user avatar
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 ...
Kom kom's user avatar
  • 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$. ...
Dan Stahlke's user avatar
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. ...
user2316602's user avatar
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 ...
Fellow4's user avatar
  • 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 ...
ie86's user avatar
  • 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 ...
Cain's user avatar
  • 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. ...
Cuize Han's user avatar
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, ...
squattyroo's user avatar
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 ...
πr8's user avatar
  • 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,...
Gericault's user avatar
  • 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 ...
PThomasCS's user avatar
  • 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 = ...
MathRevenge's user avatar
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{\...
unwissen's user avatar
  • 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 ...
香结丁's user avatar
  • 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 ...
Francesco Solera's user avatar
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-...
Drew Brady's user avatar
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 ...
gappy3000's user avatar
  • 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: ...
neverevernever's user avatar
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_{...
Turbo's user avatar
  • 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 ...
dohmatob's user avatar
  • 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_{\...
dohmatob's user avatar
  • 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 ...
Scriddie's user avatar
  • 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} \...
Govind Gopakumar's user avatar
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 ...
ie86's user avatar
  • 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(\...
Dotman's user avatar
  • 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 ...
πr8's user avatar
  • 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,\...
Betty's user avatar
  • 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$...
Hermi's user avatar
  • 288