Questions tagged [measure-concentration]
The measure-concentration tag has no usage guidance.
397 questions
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
530
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
2
votes
0
answers
184
views
Sudakov's lower bound type inequality for supremum of Chi-squared random variables
Let $\varepsilon$ be $n$-dimensional standard Gaussian veector, i.e., $\varepsilon \sim N_n(0, I_n)$. Let $\mathcal{P}$ be a subset of symmetric projection matrices in $\mathbb{R}^{n \times n}$ with $|...
- 399
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
2
votes
2
answers
468
views
Concentration bound on maximum subset sum of standard Gaussians
Let $X_1, \dots, X_n$ be standard Gaussians. Let $\mathcal{S} \subseteq \{A \in 2^{\{1, \dots, n\}} : |A| = k\} $ be a family of subsets of $\{1,\dots, n\}$ with fixed size $k$. [Note that $\mathcal{S}...
- 151
2
votes
1
answer
165
views
Existence of preferred direction for a random vector with arbitrary distribution on sphere, under a condition on its covariance matrix
Let $X$ be random vector on the unit-sphere $S_{n-1}$ in $\mathbb R^n$. We don't assume that the distribution of $X$ is uniform on $S_{n-1}$
I'm interested in proving the existence of a (...
- 6,853
15
votes
4
answers
2k
views
More than $n$ approximately orthonormal vectors in $R^n$
This question was asked at math.stackexchange, where it got several upvotes but no answers.
It is impossible to find $n+1$ mutually orthonormal vectors in $R^n$.
However, it is well established that ...
- 1,160
0
votes
0
answers
195
views
Upper-bound for bracketing number in terms of VC-dimension
Let $P$ be a probability distribution on a measurable space $\mathcal X$ (e.g;, some euclidean $\mathbb R^m$) and let $F$ be a class of funciton $f:\mathcal X \to \mathbb R$. Given, $f_1,f_2 \in F$, ...
- 6,853
2
votes
0
answers
132
views
Concentration of sample covariance for dependent data
Let $X_1, \ldots, X_T$ are sub-Gaussian random vectors in $\mathbb{R}^d$ coming from a common distribution with population covariance $\Sigma$. If they are independent, it is known that the sample ...
- 399
1
vote
0
answers
143
views
$\newcommand\v{\operatorname{vol}_d(C}$Compact subsets of $ℝ^d$ which maximize $\inf_{|v|\le1}\dfrac{\v\cap(𝜀v+C))}{\v)}$ for fixed $\v)$ and $𝜀>0$
Let $\operatorname{vol}_d$ be the volume measure on $\mathbb R^d$ and let $B_d$ be the unit-ball. For $\varepsilon \ge 0$ and a compact subset $C$ of $\mathbb R^d$ with $\operatorname{vol}_d(C)>0$, ...
- 6,853
5
votes
2
answers
397
views
Why sum of samples without replacement is more concentrated than with replacement?
Set $n\le N$.
Suppose $x_1,...,x_n$ are uniformly random variables taking value in $[N]$
In addition, let ${y_1,...,y_n}$ be an $n-$subset of $[N]$ that is chosen uniformly random among all $N \choose ...
- 550
1
vote
1
answer
508
views
Polynomial Markov versus Chernoff Bound for random variables
Suppose that $X\geq0$, and that the moment generating function of $X$ exists in an interval around 0. Given some $\delta>0$ and integer $k=1,2,...$, show that
$$\inf_{k=0,1,...}\frac{E(|X|^k)}{\...
- 100
2
votes
2
answers
690
views
Concentration and anti-concentration of gap between largest and second largest value in Gaussian iid sample
Let $n \ge 3$ be an integer and let $X=(X_1,\ldots,X_n)$ be random vector with iid coordinates from $N(0,1)$. For $1 \le k \le n$, let $X_{(k)}$ be the value of the $k$th largest coordinate of $X$.
...
- 6,853
1
vote
1
answer
409
views
The problems of global asymptotic freeness
Let $X_{N}\in\mathcal{M}_{N}\big(L^{\infty-}(\Omega,\mathbb{P})\big)$ be a $N\times N$ random complex matrix such its entries $(x_{ij}, 1\leq i, j\leq N)$ be $i.i.d.$, centred with variance $1$. $X_{...
- 137
1
vote
0
answers
351
views
Tail bounds for random Gaussian chaos?
Let $g = (g_1, \dots, g_d)$ be a sequence of independent standard Normal random variables, and suppose $\Sigma$ is a $d \times d$ (deterministic), real, symmetric, positive definite matrix. The Hanson-...
- 380
1
vote
2
answers
112
views
Concentration bound for sum of indicators of maximum value of k combinations
Let $X_1, \dots, X_n$ be i.i.d. random variables distributed as $\mathrm{Exp}(\lambda)$ for some $\lambda > 0$ and let $t > 0$. For every combination $J$ of $k$ of these variables, we define $...
- 143
1
vote
0
answers
371
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
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
1
vote
1
answer
476
views
Convergence of quadratic form $y^T Q y$ where $y$ is a random iid sequence of length $n$ and $Q$ is an $n \times n$ random matrix independent of $y$
For each positive integer, let $Q_n=(q_{i,j})_{i,j \in [n]}$ be a random $n \times n$ psd matrix. In the limit $n \to \infty$, suppose the eigenvalues of this sequence of matrices are uniformly ...
- 6,853
2
votes
1
answer
99
views
Concentration Inequality for Bounding Lipschitz Empirical Lass
Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, $(X_n:\Omega\rightarrow \mathbb{R}^m)_n$ be a sequence of i.i.d. random variables and let $L:\mathbb{R}^m\rightarrow [0,\infty)$ be ...
- 77
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
0
votes
2
answers
204
views
What is the limiting marginal distribution of a fixed number of coordinates of a random point drawn uniformly on large-dimensional sphere?
Let $X=(X_1,\ldots,X_d)$ be uniformly-distributed on the sphere of radius $\sqrt{d}$ in $\mathbb R^d$. It is well-known that in the limit $d \to \infty$, the marginal distribution of $X_1$ converges ...
- 6,853
9
votes
1
answer
351
views
Concentration inequalities for very rare events on a multiplicative scale
Let $E_1, \dots, E_N$ be independent events, each of probability $p$, where $p$ is very close to $0$. Let $A_N = \frac{1}{N} ( 1_{E_1} + \dots + 1_{E_N} )$ be the proportion of the events $E_i$ that ...
- 323
9
votes
2
answers
4k
views
What is (approximately) the expected value of $X\log{ X}$ where $X$ is binomial (or Poisson)?
Let $X$ follow a binomial distribution with parameters $n$ and $p$. Are there any known bounds for the expected value of $X\log{X}$, for large $n$ and small (but fixed) $p$? A Poisson approximation ...
- 383
2
votes
1
answer
187
views
Compute the limit of trace of inverse of square of rank-1 perturbation of Wishart matrix
Let $a \ge 0$, $b,c>0$ be fixed constants, and let $X$ be an $m \times d$ random matrix with entries drawn iid from $N(0,1/d)$. Consider the random psd matrix $S := a 1_m 1_m^\top + b XX^\top + c ...
- 6,853
3
votes
1
answer
436
views
Use statistical physics ideas ("replica trick") to compute asymptotic value of $\inf_{\|w\| \le r} (1/n)\|Xw-y\|^2$ for random $X$ and $y$
I'm trying to get my head around the "replica trick" and it's mathematically rigorous formulations (due to Talagrand, Parchenko, etc.). I was wondering to myself that a solution or insight ...
- 6,853
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
4
votes
2
answers
175
views
Almost independence of $x^\top a$ and $x^\top b$ for $x$ uniform on the sphere in $\mathbb R^d$ and $a,b \in \mathbb R^d$ with $a^\top b = 0$
Let $d$ be a large positive integer. Let $x$ be uniformly distributed on the unit-sphere in $\mathbb R^d$ and let $a$ and $b$ be perpendicular vectors in $\mathbb R^d$, i.e such that $a^\top b=0$. Let ...
- 6,853
1
vote
1
answer
104
views
Limiting value of $\dfrac{1_n^\top B^{-1} A B^{-1} 1_n}{d}$, where $A=WW^\top + a I_n$, $B = WW^\top + b I_n$, and $W \sim N(0,\Sigma_d)$
Let $n$ and $d$ be positive integers with
$$
n,d \to \infty, \quad n/d \to \rho \in (0,\infty).
$$
Let $\Sigma_d$ be a psd matrix such that
$\mbox{trace}(\Sigma_d) = 1$.
$\|\Sigma_d\|_{op} = \mathcal ...
- 6,853
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
3
votes
1
answer
555
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
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
3
votes
2
answers
637
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
6
votes
0
answers
273
views
Question about size-biased couplings and concentration of the number of collisions
Edit/Update: I was indeed missing something quite obvious. I assumed the notion of collision used was the one I am used to (number of pairwise collisions, so if a bin received $k$ balls then this ...
- 1,372
2
votes
0
answers
131
views
Eigenvalues of Witten Laplacian induced by log-concave probability measure on manifold
Let $M$ be a closed $n$-dimensional Riemannian manifold and let $\mu=e^{-V}d\mathrm{vol}_M$ be a log-concave probability measure on $M$, such that the pair $(M,\mu)$ verifies the so-called Bakry-Emery ...
- 6,853
2
votes
1
answer
302
views
Concentration on discrete probability estimator
Let $t>1$ and $X_1,..., X_t$ a set of real random variables from a discrete distribution, whose pmf is $p(x)$, supported on the points $1,...,k$.
Let $N_t(x) = \sum_{i = 1}^t \mathbb{1}_{X_i =\, x}....
- 245
8
votes
0
answers
168
views
Do compact universal covers have concentration of measure phenomenon?
$\DeclareMathOperator\vol{vol}\DeclareMathOperator\diam{diam}$I have a sequence of compact Riemannian manifolds $M_n$ with $\diam (M_n) \to 0$ and finite fundamental groups $\pi_1 (M_n)$ so that their ...
- 686
12
votes
2
answers
2k
views
Can we do better than Azuma-Hoeffding when the variance is small?
The Azuma-Hoeffding Inequality says that if $X_1,X_2, \ldots$ is a martingale and the differences are bounded by constants, $\|X_i - X_{i-1}\| \le 1$ say, then we should not expect the difference $\|...
- 1,955
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
2
votes
1
answer
116
views
A question on the applicability Chebyshev inequality for sequence of random quantities
Let $(X_n)_n$ and $(Y_n)_n$ be two mutually independent sequences of random tensors (i.e scalars, vectors, matrices, etc.) defined on the same probability space, and let $f$ be a measurable function.
...
- 6,853
2
votes
1
answer
90
views
Asymptotics of $w^\top G^2 w$, where $w$ is a unit-vector, $G:=X^T(XX^T+t I_n)^{-1}X$, $t > 0$, and $X$ is an $n\times d$ gaussian random matrix
Let $X$ be an random $n \times d$ matrix with entries drawn iid from $N(0,1/d)$ and let $w$ be a unit-vector in $\mathbb R^d$. With $\lambda>0$, and define $G:=X^\top(XX^\top + \lambda I_n)^{-1}X$. ...
- 6,853
5
votes
1
answer
273
views
Chernoff-style concentration inequality for k-tuples
I'm looking for a seemingly natural generalization of a Chernoff bound.
In many scenarios, we have a distribution $D$ with support $\mathsf{Supp}(D)$, and some event $E \subset \mathsf{Supp}(D)$ ...
- 161
2
votes
1
answer
3k
views
Tail bound regime for Binomial distribution in concentration paper
In paper 'Concentration Inequalities and Martingale Inequalities:A Survey' gives the following inequality:
My question is whether the inequality holds in regime $\lambda$ being $o(\sqrt n)$ (say $\...
- 1,836
1
vote
1
answer
352
views
Anti-concentration of inner product of a uniform unit norm vector with another vector
I have a question, which is necessary at one step of my research. Suppose that $X$ is a uniform random vector on the unit sphere $$S^{d-1} := \{x \in \mathbb{R}^d: \|x\|_2 = 1\}~.$$ Is there any ...
- 241
1
vote
1
answer
343
views
Concentration inequality for the supremum of $L_2$ norm of a vector-valued Gaussian process with iid components
Let $\Omega$ be a compact subset of $\mathbb R^p$ and let $f_1,\ldots,f_k$ be zero mean identically distrubuted Gaussian processes on $\Omega$ such that $f_1(x),\ldots,f_k(x)$ are independent $x \in \...
- 6,853
3
votes
2
answers
404
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
1
vote
1
answer
178
views
Tail bound on the RKHS norm of a zero-mean Gaussian process
Let $f \sim \mathcal{GP}(0, K)$ be a zero-mean Gaussian process defined on a compact set $\mathcal{D} \subset \mathbb{R}^d$, where $K \colon \mathcal{D} \times \mathcal{D} \rightarrow \mathbb{R} $ is ...
- 1,127
2
votes
0
answers
51
views
Spectral approximation of $(XX^\top/d)\circ(X\Sigma_dX^\top/d)$ where $X$ is an $n \times d$ random matrix with iid rows from $N(0,\Sigma_d)$
Let $X \in \mathbb R^{n \times d}$ be a random matrix with iid rows from $N(0,\Sigma_d)$ where $\Sigma_d$ is a $d \times d$ psd matrix verifying w.h.p,
$\mbox{trace}(\Sigma_d/d)= 1$.
$\|\Sigma_d\|_{...
- 6,853
4
votes
3
answers
431
views
Maximum of independent, unit-variance Gaussians with non-zero means
Suppose $X_1,\dots,X_n$ are independent Gaussians, where $X_k \sim N(\mu_k,1)$. I am interested in
$$
Z \stackrel{\rm def}{=} \max_{1\leq k\leq n} X_k
$$
and specifically on the asymptotics of $\...
- 1,372
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