# Questions tagged [measure-concentration]

The measure-concentration tag has no usage guidance.

355
questions

0
votes

1
answer

57
views

### Deducing norm concentration from MGF bounds

Suppose that $X$ is a centered, $\mathbf{R}^d$-valued random variable such that for all $t \in \mathbf{R}^d$, there holds the bound $$\log \mathbf{E} \left[ \exp \langle t, X \rangle \right] \leqslant ...

0
votes

0
answers

29
views

### matrix bernstein's inequality: from tail probability to expectation

Let $X_i$ be independent, mean zero, $n\times n$, symmetric random matrices. $\|X_i\|\leq K$ almost sure for $\forall I$.
We have matrix Bernstein's inequality for the tail probability as follows
$$\...

1
vote

1
answer

85
views

### Positivity of linear combination of gaussian variables

Consider a collection of independent standard Gaussian variables $w_i$ for $i = 1, 2, \ldots, N$. Define its linear combination $f:=\sum_{i=1}^Na_iw_i+b_i$, where $a_i=pb_i$ ($p$ is a fixed parameter),...

-1
votes

0
answers

48
views

### Upper bound for the partial sum of weighted binomial coefficients

Suppose $n$ is a natural number and $n_0 = q n$ for some positive $q \in (0, p)$. I am interested in finding a tight upper bound for the following partial summation:
$$
\sum_{x > n_{_0} }^n \...

1
vote

2
answers

141
views

### Anti-concentration of gaussian variable

Let $X$ be $\mathcal{N}(\mu,\sigma^2)$ gaussian. Its expectation $\mu$ is positive. Can we derive a lower bound on
$$\mathbb{P}(X\geq\epsilon)\geq g(\epsilon,\mu,\sigma) \text{ where } \epsilon\leq\mu$...

1
vote

1
answer

57
views

### $L_1$ norm concentration of an empirical distribution

Suppose we have one random variable $X$, whose sample space is $\mathbb{X}=\{x_1,x_2,\dots,x_m\}$, and the size of the sample space is $m$. We have $N$ i.i.d. samples from this distribution, and $x_i$ ...

0
votes

0
answers

101
views

### Anti-concentration for Bernoulli summation

Suppose $\{ Y_i\}_{i = 1}^n$ is i.i.d. Bernoulli distribution with mean $p$. Denote the sample of $\{ Y_i\}_{i = 1}^n$ as $\overline{Y} = \frac{1}{n} \sum_{i = 1}^n Y_i$. I want to know where there ...

1
vote

1
answer

145
views

### concentration of random field to its expectation function

Question
Given a random field $X(t)$ where the parameter space $T\subset\mathbb{R}_N$. Is there result regarding the concentration of the random field? For example
$\mathbb{P}\{\|X(t)-\mathbb{E}\{X(t)\...

0
votes

0
answers

25
views

### concentration inequality with matrix coefficient

Let $(X_i)_{i=1}^N$ be mean zero sub-Gaussian random vectors in $\mathbb{R}^n$, i.e., there exists $C>0$ such that for all $u\in \mathbb{R}^n$,
$$
\mathbb{E}\left[e^{u^\top X_i}\right]\le e^{\frac{...

2
votes

0
answers

82
views

### Large deviation principle for product of iid bounded symmetric random variables

Let $n$ and $k$ be positive integers. Let $X$ be the empirical mean of $n$ iid Rademacher random variables. Note that the distribution of $X$ is symmetric about 0, and also $|X| \le 1$ w.p 1. Let $X_1,...

0
votes

1
answer

160
views

### Concentration of a certain simple / well-structured random multilinear polynomial with growing degree

Let $k$ and $N_1$ be positive integers and set $N=kN_1$. Partition $[N] := \{1,2,\ldots,N\}$ $k$ disjoint from $G_1,\ldots,G_k$ of each of size $N_1$, and let $\mathcal T(k,N_1)$ be a transversal of ...

1
vote

1
answer

168
views

### Converse of the Herbst argument?

Background
For a real-valued random variable $X$, define its entropy by $H(X) = E[\phi(X)] - \phi(E[X])$, where $\phi(u) = u \log u$.
It can be shown that, if the entropy satisfies the bound
$$
H(e^{\...

2
votes

1
answer

110
views

### The lower bound of bivariate normal distribution

Suppose $(Z_1, Z_2)$ is the zero-mean bivariate normal distribution with covariance $\left( \begin{matrix} 1 & \rho; \\ \rho & 1\end{matrix} \right)$ with positive $\rho > 0$. What I want ...

4
votes

2
answers

213
views

### Concentration of minimum Hamming distance between $N$ points sampled iid from uniform distribution on $n$-dim hypercube $\{0,1\}^n$

Let $n$ be a large positive integer. Sample $N \ge 2$ points $x_1,\ldots,x_N$ iid from the uniform distribution on the $n$-dimensional hypercube $\{0,1\}^n$. Define the gap $\delta_{N,n} := \min_{i \...

1
vote

0
answers

103
views

### Concentration of a combinatorial sum

Let $X=(x_1,\ldots,x_p)$ be an $p \times n$ random matrix with iid entries from $\{\pm 1\}$, distributed so that $\mathbb P(x_{ij} = 1) \equiv 1/2$, where $x_i=(x_{i1},\ldots,x_{in})$. Let $y$ be a ...

4
votes

2
answers

219
views

### Rate of convergence of sample maximum, $\Big|\max_{j \leq n} |f(U_j)| - \|f\|_\infty\Big|$

Suppose that $f \colon [0, 1] \to \mathbb{R}$ is a $1$-Lipschitz function.
Define the uniform norm $\|f\|_\infty = \sup_{x} |f(x)|$.
Given $\{U_j\}_{j=1}^\infty$ independent and identically ...

4
votes

0
answers

303
views

### Simple proof of sharp constant in DKW inequality

The DKW inequality says that if $F_n$ is the empirical CDF corresponding to real-valued random variables $X_1, \dots, X_n$ distributed identically and independently from a distribution with CDF $F$, ...

1
vote

1
answer

101
views

### Hypothesis to guarantee Lindeberg's condition

Imagine to have a set of random variables $\{ X_i \}_{i=1}^{n}$ independent (Non identically distributed). In these scenario, if the Lindeberg's condition hold we can extend the result of the CLT, i.e....

8
votes

1
answer

469
views

### Concentration bounds for martingales with adaptive Gaussian steps

Consider the following martingale: $X_1 \sim \mathcal{N}(0, 1)$, and for any $n > 1$, $X_n \sim \mathcal{N}(X_{n-1}, X_{n-1}^2)$ (notice, this is a conditional distribution given $X_{n-1}$).
I am ...

1
vote

1
answer

78
views

### Normalized concentration inequality for empirical CDF (iid sum)

Consider the empirical and population CDF,
$$
F_n(t) = \frac{1}{n} \sum_{i=1}^n 1\{X_i \leq t\} \quad \mbox{and} \quad
F(t) = \mathbb{E} [F_n(t)],
$$
where above $X_1, \dots, X_n$ are iid, real-...

0
votes

0
answers

121
views

### Can we prove the following anti-concentration inequality of polynomials of square Gaussian variables?

Following this question Anti-concentration of Gaussian quadratic form. We have the following inequality:
Let $X_1,\dots,X_n$ denote i.i.d. standard Gaussian random variables. For every $\epsilon>0$...

2
votes

2
answers

218
views

### Minimal conditions on random vector $X \in R^n$ to ensure that $\lim_{t\to 0^+}\sup_{\|w\|_p = 1}\sup_{u \in \mathbb R}\mathbb P(|X'w-u| \le t)=0$

Let $X$ be a random variable on $\mathbb R^n$ and let $S_p^n := \{w \in \mathbb R^n \mid \|w\|_p = 1\}$ be the unit-sphere w.r.t to the $\ell_p$-norm in $\mathbb R^n$. We will be particularly ...

5
votes

0
answers

164
views

### Concentration inequalities for random measures

For random variables $X_1,\dots,X_n$ with common mean $\mathbb{E}[X_i]=\mu$ and common bounds $a\leq X_i\leq b$, we have the very useful Hoeffding's inequality:
$$\mathbb{P}\left(\left|\mu -\frac1n\...

0
votes

0
answers

77
views

### Concentration inequality for inner product of two Lipschitz functions

I was reading chapter 5 of the book HDP(Roman Vershynin). There I find theorem 5.1.4 extremely fascinating.
I am curious to discover does this theorem hold to the inner product of two Lipschitz ...

1
vote

1
answer

108
views

### Gaussian width of intersection of cube and ball in high-dimensional euclidean space

Let $d$ be a large positive integer and fix $r \ge 0$. Set $S := B_2^n \cap [-r,r]^d$, where $B_2^d$ is the euclidean unit-ball in $\mathbb R^d$. Finally, let $\omega(S)$ be the Gaussian width of $S$, ...

0
votes

0
answers

12
views

### Hoeffding type bound for functions of eigenvalues of Wigner matrix

Let $X$ be a random $d \times d$ Wigner matrix with entries of variance $1/d$ (that is, entries are i.i.d; for simplicity we can consider a GUE matrix). Is there a concentration bound on functions $f(\...

0
votes

0
answers

101
views

### Concentration compactness lemma and the best Sobolev constant

It is well known that the best Sobolev constant can be achieved on $\mathbf{R}^n$. More precisely, we have the following theorem (A):
Let $\frac{1}{q}=\frac{1}{2}-\frac{1}{n}$, $$S=\inf\limits_{{u\in ...

0
votes

0
answers

78
views

### Anti-concentration of the $\ell_2$ norm of log-concave measures

This question is regarding a special case of this question, for which it is plausible the details are known.
The Carbery-Wright inequality is an "anti-concentration inequality" that states ...

2
votes

0
answers

59
views

### Convex ordering of measures that are obtained by different push-forwards of a same measure

Suppose that we have a probability measure $\rho$ which is supported on $\mathbb{R}^d$ and absolutely continuous w.r.t. the Lebesgue measure. Take two vector fields $F, G : \mathbb{R}^d \rightarrow \...

0
votes

0
answers

41
views

### Limiting value of normalized trace of $A^{-1} e^{-tW} A e^{-tW}$, where $W$ is Wishart matrix and $A$ is deterministic

Let $n$ and $d$ be large positive integers and let $\gamma \in (0,\infty)$.
Let $X$ be an $n \times d$ random matrix with iid entries from $N(0,1/d)$.
Let $A$ be an invertible deterministic $d \times ...

2
votes

0
answers

197
views

### Prove or disprove that $u=0$ a.e. on $\Bbb R^d$

Let $\Omega\subset\Bbb R^d$ be an open set. Let $k:\Bbb R^d\to [0,\infty)$ be measurable such that $0\in \operatorname{supp}k$. This implies that $\Omega\subset \Omega_k=\Omega+\operatorname{supp}k$. ...

3
votes

0
answers

162
views

### Tail bound on trace norm / nuclear norm / Schatten-1 norm of Rademacher matrix

Let $0 < r \leq d$ integers. Let $X$, $Y$ be $d \times r$ matrices of independent Rademacher variables, that is, $X,Y \in \mathbb{R}^{d \times r}$ with entries $\pm1$ with probability $1/2$. I am ...

1
vote

1
answer

182
views

### Vector version of concentration of Lipschitz functions on sphere (Levy's Lemma)

Levy's Lemma asserts Lipschitz functions of vectors chosen uniformly from the unit hypersphere concentrate:
Lemma.
Suppose $f:\mathbb{S}^{d-1} \to \mathbb{R}$ is $L$-Lipschitz on the unit hypersphere. ...

1
vote

1
answer

113
views

### Minimax estimation rate of sparse vector $w_\star$, w.r.t to mixed norm $\|\hat w_n-w_\star\| := \|\hat w_n - w_\star\|_2 + \|\hat w_n-w_\star\|_q$

Let $n,d,s$ be positive integers with $s \le d$, and let $B_0(d,s)$ be the set of all (real) $d$-dimensional vectors with at most $s$ nonzero components. Given an $n \times d$ matrix $X$ with rows $...

2
votes

1
answer

91
views

### DKW inequality for $L^1$-norm

Suppose that $X,X_1,X_2,X_3\dots$ is a sequence of $\mathbb{P}$-i.i.d. random variables supported in the interval $[0,1]$. Let $F$ be the cumulative distribution of $X$, i.e. $F(x):=\mathbb{P}[X \le x]...

0
votes

1
answer

98
views

### On the invertibility of $Z^\top Z$, where $Z$ is a Random matrix with concentrated weakly correlated entries

Let $d$, $n$, and $m$ be large positive integers. Let $X=(x_1,\ldots,x_n) \in \mathbb R^{n \times d}$ be a random matrix iid rows from some distribition $P$ on $\mathbb R^d$ which admits a density. ...

2
votes

1
answer

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

0
votes

0
answers

77
views

### Concentration of $\mathbf{x}^TA\mathbf{x}$, with $\mathbf{x}$ a Rademacher sequence

Let $\mathbf{x}$ be a Rademacher sequence of length $n$, i.e., $\mathbf{x} \in \{-1,1\}^n$ uniformly at random. Let $A \in \mathbb{R}^{n \times n}$ symmetric, with $A_{jj} = 0$, and $|A_{jk}| \leq 1$, ...

2
votes

0
answers

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

1
vote

0
answers

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

2
votes

0
answers

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

2
votes

0
answers

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

0
votes

1
answer

98
views

### VC dimension of a certain derived class of binary functions

Let $X$ be a measurable space and let $P$ be a probability distribution on $X \times \{\pm 1\}$. Let $F$ be a function class on $X$, i.e., a collection of (measurable) functions from $X$ to $\mathbb R$...

0
votes

1
answer

88
views

### Rademacher complexity of function class $\{(x,y) \mapsto 1[|yf(x)-\alpha| \ge \beta]$ in terms of $\alpha$, $\beta$, and Rademacher complexity of $F$

Let $X$ be a measurable space and let $P$ be a probability distribution on $X \times \{\pm 1\}$. Let $F$ be a function class on $X$, i.e., a collection of (measurable) functions from $X$ to $\mathbb R$...

0
votes

0
answers

125
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$, ...

1
vote

1
answer

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

1
vote

1
answer

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

2
votes

1
answer

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

3
votes

0
answers

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

1
vote

0
answers

139
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$, ...