All Questions
Tagged with measure-concentration pr.probability
324 questions
4
votes
0
answers
1k
views
Concentration of sum of independent random variables
Let $X_1, ..., X_n$ be i.i.d. sub-Gaussian random variables with mean $0$ and variance $1$. That is, we have $\Pr[|X_i| > t] \leq \exp(1-t^2/K^2)$ for all $t>0$ and a parameter $K$.
Then we can ...
- 1,324
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
1k
views
Concentration of sum of concentrated random variables
I have a sum of positive random variables, they are not identically distributed, but even that case would be interesting. They are not necessarily independent, but I already have a concentration bound ...
- 233
3
votes
1
answer
178
views
Tail probability of random projection
Suppose $v\in R^n$ is a constant unit vector. $P_l$ is a random projection matrix to an $l$ dimensional subspace of $R^n$ which is uniformly sampled from $G(l,R^n)$ which is the collection of all $l$-...
- 1,495
3
votes
3
answers
5k
views
Hoeffding's inequality for vector valued random variables
Is there a version of Hoeffding's inequality for vector valued random variables?
This seems to be hard to find and I wonder why. I suppose it is difficult to show Hoeffding's lemma, since the proof ...
- 619
3
votes
1
answer
158
views
Sub-Gaussian concentration without the sub-Gaussian norm
A random variable $X$ is said to have sub-Gaussian tails with parameter $\sigma>0$ if
$$\Pr[|X|\geq t] \leq 2\exp(-t^2/(2\sigma^2))$$
I am interested if $X_0, X_1$ are independent, and have sub-...
- 2,183
3
votes
1
answer
2k
views
Gaussian concentration inequality
Recently I found a concentration inequality for infinite dimensional Gaussian r.v.s in this paper. Specifically, Lemma 4 on page 307 states (without a proof) that
There exists a universal constant $...
- 185
3
votes
2
answers
731
views
Concentration inequality for sum of iid random variables that involve KL distance
Conider $X \in \mathbb{R}^d$ and $Y \in \{0,1\}$, and a joint distribution $p_{XY}(x,y)$, and a set of $N$ i.i.d. samples $\{(X_i,Y_i)\}_{i=1}^{N}$. Define $p_{X0} = p_{XY}(x,0)$ and $p_{X1} = p_{XY}(...
- 482
3
votes
1
answer
114
views
Lower-bound for $\underset{p \le \gamma_d(A) \le q}{\inf} \gamma(A^\epsilon)$, where $\gamma_d$ is the standard gaussian distribution on $\mathbb R^d$
Let $\gamma_d = \gamma_1 \otimes \ldots \otimes \gamma_1$ be the standard Gaussian distribution on $\mathbb R^d$, where $d$ is a large positive integer. Given $\epsilon \ge 0$ and a measurable $A \...
- 6,853
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
1
answer
88
views
If $X \sim N(0,I_m)$, what is a necessary and sufficient condition on $u_m > 0$ such that $\lim\sup_{m\to \infty} P(\|X\|^2 \ge u_m|X_1|) = 1$
Let $m$ be a large positive integer and $X=(X_1,\ldots,X_m) \sim N(0,I_m)$. I wish to show that the squared norm of $X$ is much much bigger than the absolute value of any of the $X_j$'s. For example, ...
- 6,853
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
2
answers
442
views
What happens to the Gaussian volume of a Borel set when it is translated?
Let $\gamma_n$ be the standard Gaussian measure on $\mathbb R^n$, $A \subseteq \mathbb R^n$ be Borel and $c \in \mathbb R^n$. Define the translate $A_c := c + A := \{c+a \mid a \in A\} = \{x \in \...
- 6,853
3
votes
1
answer
156
views
Concentration of measure on spheres with respect to a unitary of trace approximately zero
Cross-posted from MSE, where it hasn’t received any answer yet:
This question arose out of my attempt to understand how a unitary of trace approximately zero acts on the unit sphere of a $n$-...
- 2,830
3
votes
1
answer
190
views
Example where concentration of measure fails nontrivially
A metric probability space $(X, \mu, \rho)$, i.e., a complete separable metric space with a probability measure on its Borel sets, is said to satisfy (Gaussian) concentration of measure property if ...
- 141
3
votes
1
answer
527
views
Wasserstein-type concentration inequalities for empirical measures on polish spaces
Let $(\mathcal{X},d)$ be a Polish (metric) space and let $\{X_n\}_{n=1}^{\infty}$ be a sequence of i.i.d. $\mathcal{X}$-valued random elements defined on a common complete (standard) probability space ...
- 5,405
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
182
views
How tight is the bound $P(\|X\|^2 \ge t |\langle a,X\rangle|) \ge 1 - t\sqrt{\frac{2}{m-1}}$, where $X \sim N(0, I_m)$ and $\|a\| = 1$?
Let $X$ be a random vector in $\mathbb R^m$ with iid $N(0,1)$ coordinates and let $a$ be a fixed unit vector in $\mathbb R^m$. In another post (SE link here https://math.stackexchange.com/a/3792730/...
- 6,853
3
votes
1
answer
1k
views
Chernoff-type bound for sum of Bernoulli random variables, with outcome-dependent success probabilities
Let $X = (X_1, X_2, \ldots, X_n)$ be a sequence of (not necessarily independent) Bernoulli random variables where for each $i$, the success probability $\Pr[X_i = 1]$ itself is a random variable ...
- 153
3
votes
2
answers
319
views
Concentration inequality of joint event over time of a submartingale
Consider a discrete time submartingale $X_n$ with bounded difference $|X_n-X_{n-1}|\leq c$. With Azuma inequality we have the concentration of a single time event as
$$
P(X_t-X_0 \leq -t) \leq exp\...
- 185
3
votes
1
answer
282
views
Longest runs and concentration of measure
Consider the longest runs $\ell_\sigma(x)$ of the pattern $\sigma$ for $\sigma\in \{0, 1, 01, 10, 001,\dots\}$ etc. in a binary sequence $x=x_1\dots x_n$.
For example, $\ell_{001}(0001110010011001)=2$...
- 24.8k
3
votes
1
answer
745
views
Vector version of concentration of Lipschitz functions on sphere (Levy's Lemma)
Levy's Lemma asserts Lipschitz functions of vectors chosen uniformly from the unit hypersphere concentrate:
Lemma.
Suppose $f:\mathbb{S}^{d-1} \to \mathbb{R}$ is $L$-Lipschitz on the unit hypersphere. ...
- 131
3
votes
1
answer
307
views
Concentration of monochromatic edges in a graph
Let $G$ be a graph of order $n$ with $m$ edges. Color each vertices uniformly at random with $q$ colors. It is easy to see that expected number of monochromatic edges (edge whose end vertices are of ...
3
votes
1
answer
294
views
Concentration inequalities specialized for log-likelihood / log-density functions
Let $P$ be a probability measure and $f$ be some probability density function (not necessarily related to $P$). Consider the function
$$
L(X_1,\ldots,X_n)
=\frac1n\sum_{i=1}^n\log f(X_i),
\quad
X_i\...
- 710
3
votes
1
answer
196
views
Uniform Convergence for Vectors
$\textbf{Problem statement:}$
Let $\mathcal H:\mathcal X \rightarrow \{0,1\}$ be a class of Boolean functions for $\mathcal X \subset \mathbb R^n$, and let the VC Dimension of $\mathcal H$ be $VC_{...
- 197
3
votes
2
answers
394
views
Strictly positive solutions of a random linear system
Suppose $B\in\mathbb{R}^{m\times n}$ is a random binary matrix with i.i.d entries and $c\in \mathbb{R}^m$ is a strictly positive vector, that is $c_i>0$ for $i=1,2,\cdots m$. Also assume $m<n$, ...
- 127
3
votes
2
answers
589
views
Measure concentration for law of large numbers
The classical law of large numbers states that
$$\frac1k\sum_{i=1}^k X_i \rightarrow \mathbb{E} X_1$$
for i.i.d. $X_1, X_2, \ldots$ with finite $L^1$ norm.
I was wondering whether is it possible to ...
- 773
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
130
views
Does a DKW-type inequality hold for the empirical CDF of a random vector on the sphere?
I've begun to study concentration of measure because of its relevance to statistical mechanics. In recent decades concentration inequalities have played a role in elucidating foundational conceptual ...
- 131
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
1
answer
176
views
Gaussian concentration/isoperimetric inequality with correlated Gaussian measure
Famous Gaussian concentration inequality states that:
If $\mathrm{F}$ is 1 -Lip, and $\mathbb{E} F(X)=0,$ and $X=(X_1,...,X_n) \sim N\left(0, I_{n}\right),$ then we have for some absolute constant $C&...
- 519
3
votes
1
answer
189
views
Isoperimetry on $[0, 1]^n$ w.r.t $\ell_p$ distance, with $p \in [1,\infty]$
Let $A$ be a measurable subset of the metric space $\mathcal X = ([0, 1]^n,\ell_p)$ with $1 \le p \le \infty$, and define its $\varepsilon$-blowup by $A^\varepsilon:=\{x \in \mathcal X \mid \|x-a\|_p \...
- 6,853
3
votes
1
answer
460
views
Derive concentration bound for the derivative
It that true to conclude that if a random $f(z)$ is a sub-Gaussian random variable for a constant value of z, its derivative $f'(z)|_{z=k}$ with respect to variable $z$ is also sub-Gaussian?
In ...
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
130
views
A Talagrand inequality for the supremum of partial sums over function classes under dependence. (Reference request)
As a consequence to the Talagrand concentration inequality, it is well known that for a measurable space $(S,\mathcal{S})$ and an i.i.d. sample $X_1,...,X_n$ of $S$-valued random variables, if $\...
- 141
3
votes
0
answers
70
views
Concentration for Hamming balls
It is well known that Lipschitz functions on the Boolean $n$-cube endowed with the Hamming metric satisfy concentration properties. Specifically, most of their values lie in a range of width $O(\sqrt ...
- 2,772
3
votes
0
answers
334
views
Tail bound on trace norm / nuclear norm / Schatten-1 norm of Rademacher matrix
Let $0 < r \leq d$ integers. Let $X$, $Y$ be $d \times r$ matrices of independent Rademacher variables, that is, $X,Y \in \mathbb{R}^{d \times r}$ with entries $\pm1$ with probability $1/2$. I am ...
- 223
3
votes
0
answers
93
views
Explaning why the spectrum of a setting simple structure random matrix is always spiked ($d-1$ eigenvalues close to zero, and $1$ away from zero)
For concreteness, let $m=500$, $d=600$, $N=1000$. Let $W$ be and $d \times m$ matrix with unit-norm rows and let $u$ be a uni-norm vector of length $m$. Given a binary vector $b$ of length $m$, length ...
- 6,853
3
votes
1
answer
373
views
Concentration of very dependent Markov chains
Consider the following simple Markov chain $ X_1\to X_2\to\cdots\to X_n $ where each $X_i$ is $\{-1,1\}$-valued and $X_1\sim\mathrm{Unif}(\{-1,1\})$ (such that the chain is stationary).
The flip ...
- 161
3
votes
0
answers
83
views
Ornstein-Ulhenbeck like semigroup for the orthogonal group with a hypercontractive inequality
I am looking for an Ornstein-Uhlenbeck like semigroup $P_t$ and associated generator $\mathcal{L}$ on $G = \operatorname{SO}(n)$ or $\operatorname{O}(n)$ that has a hypercontractive inequality with a ...
- 941
3
votes
1
answer
379
views
Concentration inequality for norm of solution to nonlinear least-squares problem
Define the piecewise-linear function $\psi(t):=\max(t,0)$ for all $t \in \mathbb R$.
Let $d,n,k \to \infty$ at the same rate (i.e $n \asymp k \asymp d$).
Let $y_1,\ldots,y_n \in \{-1,1\}$ uniformly ...
- 6,853
3
votes
0
answers
103
views
Concentration inequalities for gradient flows induced by random fields
Let $G=(G(x))_{x \in \mathbb R^m}$ be a conservative random field with values in $\mathbb R^m$, for large positive integer $m$. That is, there exists a scalar random field $g=(g(x))_{x \in \mathbb R^m}...
- 6,853
3
votes
0
answers
307
views
Upper-bound for eigenvalues of $E [UU^T]$, where $U$ is uniformly distributed on the unit $n$-sphere
Let $X$ be a $\sigma$-subGaussian random vector on $\mathbb R^n$ (for large $n \ge 3$), meaning that the random variable $X^Tv$ is $\sigma$-subGaussian for every unit vector $v \in \mathbb R^n$. ...
- 6,853
3
votes
0
answers
187
views
Concentration Inequalities for the Exponential of Weighted Bernoulli Sums
I want a concentration inequality for the exponential of a weighted sum of independent Bernoulli random variables around its mean, for one of my research works. I was wondering if there is a well ...
- 123
3
votes
1
answer
826
views
concentration inequality for a weighted sum of independent but not identical binary variables
Let $\alpha\in[0,1]$ be a fixed constant, and let
$w,x\in[0,1]^n$ be two vectors such that $\sum_i w_i x_i=\alpha$.
Define $Y = \sum_i w_i X_i$, where $X_i \sim \operatorname{Bernoulli}(x_i)$, so it ...
- 617
3
votes
0
answers
166
views
Matrix Chernoff sampling with out replacement
I am interested to know if the matrix Chernoff bound (see Theorem 5.1.1 in https://arxiv.org/pdf/1501.01571.pdf) holds if one samples without replacement.
For example, the Bernstein inequality is ...
- 221
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
186
views
Anti-concentration for sum of t-wise independent uniform variables
Let $X_{1},\ldots,X_{n}$ be i.i.d. random variables, each variable is uniform over the set of integers $\{ 0,\ldots,D-1 \}$. Let $S = \sum_{i=1}^{n}X_{i}$.
By ``small ball probability'', we have that ...
- 225
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