Questions tagged [measure-concentration]
The measure-concentration tag has no usage guidance.
397 questions
2
votes
1
answer
947
views
Upper-bound for spectral norm of the covariance matrix of a certain Gaussian vector with correlated entries
Let $n$ and $m$ be large positive integers. Let $x=(x_1,\ldots,x_n)$ be a vector of independent random variables from $N(0,1)$. It is clear that the covariance matrix of $x$ is $I_n$, the identity ...
- 6,853
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
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
3
votes
0
answers
372
views
On the precise concentration of permanent of $\pm1$ matrices
Obtain $M\in\{-1,+1\}^{n\times n}$ by unbiased coin flipping.
What is known about the distribution of permanent $\mathsf{Perm}(M)$? It seems to be bimodal.
Given a function $g(n)$ what is the ...
CommunityBot
- 1
5
votes
3
answers
5k
views
Distribution of the individual coordinates of a uniform random vector on a high-dimensional sphere
Let $X=(X_1,\ldots,X_n)$ be a random vector uniformly distributed on the $n$-dimensional sphere of radius $R > 0$. Intuitively, i think that for large $p$ every coordinate $X_i$ is normally ...
- 6,853
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
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
1
answer
223
views
Bound error in approximating $E_x [H(f(x))]$ with random $(1/n) \sum_{i=1}^n \Phi(f(x_i)/h)$ where $H$ is Heaviside function and $\Phi$ is normal CDF
Let $f:\mathbb R^d \to \mathbb R$ be a "sufficiently smooth" function. For simplicity, we may consider $f$ to be an affine function, i.e $f(x) \equiv b-x^\top w$, for some $(w,b) \in \mathbb ...
- 6,853
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
1
vote
1
answer
231
views
For $x_1,...,x_n$ iid random on sphere of radius $\sqrt{d}$ in $R^d$, what is a good upper-bound on min distance of $x_{n}$ from the other $x_i$'s?
Let $n$ and $d$ be large positive integers with $n \le d^\gamma$, for some absolute constant $\gamma>0$; i.e., $n$ is at most polynomial in $d$. Let $x_1,\ldots,x_n,x_{n+1}$ be drawn iid from the ...
- 6,853
14
votes
3
answers
2k
views
Concentration bounds for sums of random variables of permutations
I'm trying to find theorems regarding random variables derived from sampling permutations, specifically concentration bounds.
As an example, let $X_i$ be the $\{0,1\}$-random variable that represents ...
- 1,724
2
votes
0
answers
386
views
What is the concentration of measure for Gaussian random variables which are independent, but are transformed?
This might be a too easy question for Mathoverflow, but Googling led to similar questions and answers here (though not the one I was looking for).
The question is split into two:
I have a matrix $X \...
- 18.7k
4
votes
1
answer
240
views
Uniform inequality of the form $\text{Proba}(\sup_{v \in [-M,M]^k}|p^Tv-\hat{p}_n^Tv| \le \epsilon_n) \ge 1 - \delta$
Let $M > 0$, $k$ be a positive integer, and $\mathcal V:=[-M,M]^k$. Finally, let $p \in \Delta_k$, (where $\Delta_k$ is the $(k-1)$-dimensional probability simplex) and let $\hat{p}_n$ be an ...
- 1
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 (...
- 128k
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
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\...
- 14.2k
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
6
votes
3
answers
447
views
Isoperimetric inequality for $\epsilon$-expansion of a set only along a certain subspace
Let $\gamma_n$ be the standard gaussian distribution on $\mathbb R^n$. Let $V$ be a $k$-dimensional subspace of $\mathbb R^n$. Finally let $A$ be any (nonempty) Borel subset of $A$ with $\gamma_n(A) = ...
- 6,853
2
votes
2
answers
533
views
Lower bound on misclassification rate of Lipschitz functions in terms of Lipschitz constant
Important note
@MateuszKwaśnicki in the comment section has raised a fundamental issue with the current statement of the problem. I'm trying to bugfix it.
Setup
I wish to show that a Lipschitz ...
CommunityBot
- 1
7
votes
3
answers
496
views
Chernoff-type bounds for a stopped sum of independent random variables
Let $Y_1, \ldots, Y_n$ and $X_1, \ldots, X_n$ be i.i.d. $p$-Bernoulli random variables and let $T \in \{0, \ldots, n\}$ be a stopping time for the process. From Wald's equation, we know
$$
E\left[\...
- 183
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 $...
- 128k
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 ...
- 13k
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 ...
- 1,724
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 ...
- 128k
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
6
votes
1
answer
306
views
Weak concentration bounds for averages of independent random variables in Orlicz spaces
Let $\phi$ be an $N$-function, (i.e. $\phi : \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}$ is convex and satisfies $\lim_{t \to 0} \frac{\phi(t)}{t} = 0, \lim_{t\to \infty} \frac{\phi(t)}{t} = \infty$)....
- 128k
1
vote
1
answer
366
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:
...
CommunityBot
- 1
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 ...
- 660
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 ...
- 1,724
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
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
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.
...
- 1,769
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
0
votes
0
answers
86
views
Expected diameter of a random point set
General problem: For a point set $S\subset X$ in a metric space $(X,d)$, let $\text{diam}(S)=\max_{x,y\in S}d(x,y)$. Given a distribution $P$ on $X$ and $m$ i.i.d. points $x_1,\ldots,x_m\sim P$, what ...
- 19
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 ...
- 32.1k
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 ...
- 188k
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 ...
- 128k
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 ...
- 128k
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 ...
- 14.2k
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
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. ...
CommunityBot
- 1
1
vote
0
answers
78
views
Cosine function evaluations are linearly independent? [closed]
Let $\{x_1,\ldots,x_n\}$ be distinct points in $\mathbb{R}^d$, and consider the functions $f_j(x) = cos(w_j^T x + b_j)$ for $w_j \in\mathbb{R}^d$, $b_j\in\mathbb{R}$, $j=1\ldots,m$, and let $m\ge n$. ...
- 51
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
2
votes
1
answer
114
views
Reweighting probability measures by convex potentials, and contraction in transport distance
Let $W: \mathbf{R}^d \to \mathbf{R}$ be a convex function such that $\int \exp(-W) = 1$, and define probability measures $\mu_y$ by
$$\mu_y (dx) = \exp( - W (x - y)) \,dx,$$
i.e. each $\mu_y$ is a ...
- 999
1
vote
0
answers
57
views
Concentration inequality for matrix martingale with dynamic upper bounds
Consider a sequence of stochastic PSD matrices $X_1, X_2, \dots, X_n \in \mathbb{R}^{d\times d}$. Let $\mathcal{F}_k = \sigma(X_1, X_2, \dots, X_{k-1})$ be the natural filtration and $Y_k = \mathbb{E}[...
- 63.9k
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 ...
- 13k
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
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 ...
- 128k
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
2
votes
1
answer
240
views
Lipschitz condition with respect to operator norm of a Gaussian matrix with iid entries. Improved Gaussian Poincare Inequality?
The Gaussian Poincare inequality says that if $q:R^n\to R$ is Lipschitz (for simplicity you may additionally assume smooth with compact support), then $Var[f(X)] \le L^2$
for $X\sim N(0,I_q)$.
Now ...
- 128k