Questions tagged [measure-concentration]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
5
votes
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
2answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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-...

1
2 3 4 5 6