All Questions
Tagged with pr.probability measure-concentration
324 questions
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:
...
CommunityBot
- 1
3
votes
1
answer
526
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
348
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-...
- 420
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
475
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
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
351
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
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. ...
CommunityBot
- 1
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 ...
- 984
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 ...
- 12.9k
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
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}....
- 128k
4
votes
3
answers
345
views
Do subgaussian variables obey the slightly-stronger-than-Chernoff tail bound?
If $X \sim Normal(0,1)$, then we have the tail bound:
$$ (*) \qquad\Pr[X > t] \leq \mathcal{O}\left(\frac{e^{-t^2/2}}{t}\right) .$$
Now for general variables $X$, a nice condition is that $X$ be ...
- 128k
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
2
votes
0
answers
172
views
Asymptotic lower and upper bounds for the eigenvalues of hadamard product $W \circ W$, where $W$ is a large Wishart matrix
Let $n$ and $d$ be large positive integers with $n,d \to \infty$ such that $n/d \to \gamma \in (0,\infty)$. Let $X$ be a random $n \times d$ random matrix with iid copies of log-concave isotropic ...
- 6,853
1
vote
1
answer
144
views
Bounds for the extreme singular-values of random matrix with thresholded entries
Let $n,d,k$ be large positive integers such that $\max(n/d,k/d) =: \lambda < 1$. Let $X$ be a random $n \times d$ matrix with entries drawn iid from $N(0,1/d)$ and let $W$ be a $k \times d$ random ...
- 6,853
1
vote
0
answers
155
views
Relation between the class $\mathcal{M}(m,\sigma)$ and subgaussianity
In this paper, Adamczak defines, for $m>0$ and $\sigma\geq 0$, the class of probability distributions $\mathcal{M}(m,\sigma)$ over $\mathbb{R}$ as those $\mu$ satisfying the tail conditions
$$\nu^+(...
- 1,372
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&...
CommunityBot
- 1
2
votes
0
answers
83
views
Concentration inequalities for sets
Assume that we have a random set $B$ which is constructed by selecting elements from $U = \{ X_1, \dots, X_n \}$ where $X_i$ are independent samples from Gaussians with means $\mu_i$ and variances $\...
- 143
2
votes
1
answer
668
views
Lower-bound for smallest eigenvalue of random $k \times $k matrix $C(W)$ defined by $C(W)_{i,j} := 2(w_i^\top w_j)^2 + \|w_i\|^2\|w_j\|^2$
Let $k$ and $d$ be positive integers such that $d/k:=\lambda > 1$. Let $W$ be $k \times d$ random matrix with rows $w_1,\ldots,w_k \in \mathbb R^d$ drawn iid from $N(0,(1/d)I_d)$, and define the $k ...
- 6,853
1
vote
0
answers
96
views
Concentration for $\sum_{i=1}^n y_i \psi(x_i^\top u)$, for $y_1,\ldots,y_n \sim \{\pm 1\}$ and $x_1,\ldots,x_n$ uniform iid on hypersphere
Let $y_1,\ldots,y_n$ be drawn iid uniformly from $\{\pm 1\}$ and let $x_1,\ldots,x_n$ be drawn iid uniformly from the unit-sphere $(d-1)$-dimensional sphere $\mathbb S_{d-1}$, and independently from ...
- 6,853
4
votes
3
answers
428
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 $\...
CommunityBot
- 1
1
vote
0
answers
68
views
(Anti-)concentration of gap between largest and second largest component of multivariate random gaussian vector
Let $n$ be a large positive integer and let $Y=(Y_1,\ldots,Y_n)$ be a zero-centered random $n$-dmensional real vector with covariance matrix $\Sigma$, an $n$-by-$n$ positive definite matrix with ...
- 6,853
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,\...
- 128k
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$.
...
- 128k
1
vote
1
answer
261
views
Concentration inequality for a function whose parameter depends on input samples
Concentration inequalities can be used to establish results such as sample mean cannot be too far from the actual population mean, and so on. For example, let $X_1 \ldots X_n$ be i.i.d instances of a ...
- 14.2k
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 \...
- 3,946
9
votes
1
answer
350
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 ...
- 128k
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$, ...
- 245
2
votes
1
answer
187
views
Unconditional lower bound for volume of blowup $\mu(B^\epsilon)$ for $\mu(B) \in (0, 1)$ and $\epsilon > 0$ not "too large"
For a Borel subset $B$ of a metric space $X = (X,d)$ and $\epsilon>0$, recall the defintion of the $\epsilon$-blowup of $B$, namely $B^\epsilon = \{x \in X | d(x,B) \le \epsilon\}$. Let $\mu$ be a ...
CommunityBot
- 1
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 \...
CommunityBot
- 1
1
vote
0
answers
57
views
Good lower-bound for $\inf_{x \in \Delta_n} \|Gx\|$ where $G$ is an $N \times n$ random matrix with iid entries from $\mathcal N(0,1/\sqrt{N})$
Let $G$ be an $N \times n$ random matrix with independent entries distributed according to a centered Gaussian with variance $1/\sqrt{N}$ and let $n/N = \lambda \in (0, 1)$. Let $\Delta_n$ be the $(n-...
- 6,853
0
votes
1
answer
806
views
Concentration of $\ell_2$ norm of a vector sampled from a distribution
Let $X=(X_1,\ldots,X_n)$, where $X_i \sim P_{p_i}(0,\frac{1}{\lambda})$ are iid, $P_{p_i}$ is sub gaussian distribution for $i^\text{th}$ element, and 0 and $1/\lambda$ are mean and variance.
I'm ...
- 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?
$$...
- 14.2k
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 \...
- 128k
1
vote
1
answer
141
views
Central limit theorem for chi-squared random field on $\mathbb R^p$
Let $X:x \mapsto X(x)$ be a centered stationary Gaussian process on the $\Omega:=\mathbb R^p$, such that $X(x) \overset{d}{=}X(x')$ for all $x,x' \in \Omega$. Set $\sigma^2 := \mbox{Var}(X(0)) = \...
- 128k
1
vote
1
answer
59
views
Characterization of random variables whose tensor powers have subexponential "small-ball" probabilities
Is there a succinct characterization of all random variables $\zeta$ on $\mathbb R$ with the following properties
1. Symmetry: $\zeta \overset{d}{=} - \zeta$.
2. Small-ball probability: there exists ...
- 6,853
2
votes
1
answer
212
views
Prove / disprove: If $1 \le n < N$ and $A$ is an $N \times n$ matrix with iid from $\mathcal N(0,1)$, then $s_\min(A) \ge c\sqrt{N}$ w.p $1-2e^{-N}$
Let $1 \le n < N$ be integers and $A$ be a random $N\times n$ matrix with iid entries from $\mathcal N(0,1)$. This paper (Rudelson and Vershynin) claims in the paragraph just before formula (3.4) ...
- 6,853
0
votes
1
answer
280
views
Lower-bound on smallest singular-value of rectangular random matrix
Let $X$ be a random $N \times n$ matrix with iid entries from $\mathcal N(0, 1)$ and with $n/N =: \lambda(N,n) \le \lambda_0$, for some $\lambda_0 \in (0, 1)$. That is, $X$ is genuinely rectangular (...
- 128k
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 ...
- 128k
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