# Questions tagged [measure-concentration]

The measure-concentration tag has no usage guidance.

286
questions

**5**

votes

**0**answers

212 views

+50

### 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 ...

**5**

votes

**1**answer

150 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 ...

**3**

votes

**0**answers

56 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 ...

**1**

vote

**1**answer

39 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 ...

**2**

votes

**1**answer

57 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}....

**0**

votes

**0**answers

21 views

### Covariance concentration bound for randomly sampled positive semi-definite matrices

I saw the following inequality being used in a paper and the given reference was Joel A Tropp et al. An introduction to matrix concentration inequalities. However, I could not find this inequality ...

**4**

votes

**2**answers

122 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 ...

**0**

votes

**1**answer

94 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 ...

**2**

votes

**0**answers

34 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 ...

**3**

votes

**0**answers

39 views

### Eigenvalues of Hadamard product of two Wishart-type matrices

Given two independent Gaussian matrices with i.i.d. entries: $A\in\mathbb{R}^{n\times p}$ and $B\in\mathbb{R}^{n\times q}$, where and $A_{i,j},B_{i,j}\sim\mathcal{N}(0,1)$. Assume that $\max(p,q)<n....

**0**

votes

**0**answers

31 views

### Gaussian maxima, graph connectivity, superconcentration and mean outsourcing : reference request

Consider a sequence (indexed by $n$) of centred multivariate Gaussian arrays $\{X_i\}_{i\le n}$ such that $\operatorname{Var}(X_i)=1$ for all $i$ and $\sum_{i\le n}\mathbb{E}(X_iX_j)=c_n$ for all $j$.
...

**1**

vote

**1**answer

183 views

### High-probability lower bound for norm of least squares solution when both design matrix $X$ and response vector $y$ are random (and independent)

Let $n,d \to \infty$ with $n/d \to \gamma \in (0,\infty)$. Let $X$ be a random $n \times d$ matrix independent rows uniformly distributed on the the unit-sphere in $\mathbb R^d$ and let $y$ be a ...

**2**

votes

**1**answer

156 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. ...

**1**

vote

**1**answer

112 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 ...

**1**

vote

**0**answers

139 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**

vote

**1**answer

64 views

### A result about sub-exponential random variables

I am reading the proof of Theorem 1(a) in the paper that proposed the CLIME method for estimating precision matrix. I am puzzled by an inequality on Page 605 three lines above formula (29). I isolate ...

**2**

votes

**0**answers

69 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 $\...

**2**

votes

**1**answer

374 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 ...

**0**

votes

**0**answers

24 views

### High-probability upper-bound for $\|(G^\top G)^{-1} (1,\ldots,1)\|_2$, where $G$ is gaussian random matrix with iid entries from $\mathcal N(0,1/N)$

Let $G$ be an $N \times n$ random matrix with iid entries from $\mathcal N(0,1/N)$, with $n/N =: \lambda \in (0, 1)$, and let $u=(1,1,\ldots,1) \in \mathbb R^n$.
Question. What is a upper-bound for $\...

**1**

vote

**0**answers

78 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 ...

**0**

votes

**0**answers

32 views

### Lower-bound on smallest singular-value of a certain random kernel matrix

Let $d$ and $k$ be positive integers and let $w_1,\ldots,w_k$ be iid random vectors from $N(0,(1/d)I_d)$. Consider a $k \times k$ matrix $C=(c_{ij})$, defined by
$$
c_{i,j} := \|w_i\|\|w_j\|f(\frac{...

**0**

votes

**0**answers

34 views

### Spectral norm of product of fixed matrix and random semiorthogonal matrix

Suppose I have a fixed matrix $A \in \mathbb{R}^{a \times b}$ and a random matrix $B \in \mathbb{R}^{b \times c}$ with $c < b$ where $B'B = I_c$.
I am hoping to find a concentration inequality for ...

**2**

votes

**1**answer

129 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 ...

**0**

votes

**1**answer

91 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)}{\...

**1**

vote

**0**answers

38 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 ...

**0**

votes

**1**answer

77 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,\...

**3**

votes

**1**answer

91 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&...

**2**

votes

**2**answers

302 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$.
...

**0**

votes

**0**answers

24 views

### Distribution on the inner product of random projections, concentration of measure

For given $d$, $I_d$ denotes the identity matrix.
Let $2d\times 2d$ matrix $P=\begin{pmatrix}
I_d & 0\\
0 & 0
\end{pmatrix}$.
Let us consider
$UPU^{+}=\begin{pmatrix}
A & B\\
C &...

**0**

votes

**0**answers

39 views

### Supremum of Lipschitz Gaussian process on sphere

Let $T:=\mathbb S_{m-1}$ be the unit sphere in $\mathbb R^m$ and consider a real-valued centered Gaussian process $(x_t)_{t \in \mathbb T}$ such that $\mathbb E X_t^2 = t$ for all $t$. consider the ...

**1**

vote

**1**answer

96 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 ...

**4**

votes

**1**answer

84 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 \...

**9**

votes

**1**answer

231 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 ...

**1**

vote

**0**answers

47 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-...

**3**

votes

**2**answers

204 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?
$$...

**0**

votes

**1**answer

69 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)) = \...

**1**

vote

**1**answer

75 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 \...

**1**

vote

**1**answer

48 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 ...

**2**

votes

**1**answer

152 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) ...

**0**

votes

**1**answer

76 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 (...

**0**

votes

**0**answers

57 views

### Anti-concentration of measure: Slud's inequality for finite populations

Suppose that I have Bernoulli trials with unknown bias $p$. I need $\Omega(\frac{\log 1/\delta}{\epsilon^2})$ samples for the average of the samples to estimate $p$ within $\epsilon$ error with ...

**2**

votes

**0**answers

50 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}...

**3**

votes

**1**answer

265 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 ...

**3**

votes

**1**answer

71 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, ...

**1**

vote

**0**answers

36 views

### Chernoff-type Bounds for Continuous-space Markov Chains

Let $X_1, X_2, \dots, X_n$ be $n$ samples from a discrete-time continuous-space Markov Chain.
Are there any good references who have provided a Chernoff-type bound regarding the behaviour of the ...

**5**

votes

**1**answer

187 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)$ ...

**0**

votes

**1**answer

141 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 ...

**3**

votes

**1**answer

142 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/...

**19**

votes

**0**answers

500 views

### A Rademacher 'root 7' anti-concentration inequality

Let $r_1,r_2,r_3,\ldots$ be an IID sequence of Rademacher random variables, so that $\mathbb P(r_n=\pm1)=1/2$, and $a_1,a_2,\ldots$ be a real sequence with $\sum_na_n^2=1$. For $S=\sum_na_nr_n$, does ...

**1**

vote

**0**answers

89 views

### Exponentially suppressed events for bounded difference super-martingales

Let $\{ Z_n \mid n = 0,1,..\}$ be a non-negative super-martingale and assume that it is of bounded difference i.e $\exists ~c_i >0$ s.t $\vert Z_{i+1} - Z_i \vert \leq c_i$. Then we know (Azuma-...