Questions tagged [measure-concentration]
The measure-concentration tag has no usage guidance.
397 questions
3
votes
2
answers
442
views
What happens to the Gaussian volume of a Borel set when it is translated?
Let $\gamma_n$ be the standard Gaussian measure on $\mathbb R^n$, $A \subseteq \mathbb R^n$ be Borel and $c \in \mathbb R^n$. Define the translate $A_c := c + A := \{c+a \mid a \in A\} = \{x \in \...
- 6,853
0
votes
2
answers
282
views
Bounds tighter than the additive Chernoff
Additive Chernoff
Suppose $X_1, \ldots, X_n$ are i.i.d. random variables, taking values in $\{0,1\}$. Let $p=\mathrm{E}\left[X_i\right]$ and $\varepsilon>0$.
\begin{gather*}
\operatorname{Pr}\left(\...
- 484
2
votes
1
answer
250
views
A concentration inequality related to suprema of sub-Gaussian processes
Let $x_1,\dots,x_n$ be deterministic points in some space $X$ and consider a class of real-valued functions $\mathcal G$ on $X$. We further assume that for any $g \in \mathcal G$,
$$
\Bigl(\frac1n \...
- 1,741
1
vote
0
answers
57
views
Limiting value of expectation of trace of truncated Gram matrix
Let $n$ and $d$ be large positive integers such that $d/n = a \in (0,1)$, fixed. Let $x_1,\ldots,x_n$ be iid random vectors from $N(0,I_d)$. Fix $b \in (0,1]$ and a unit-vector $v \in \mathbb R^d$, ...
- 6,853
2
votes
0
answers
70
views
A lemma in the application of Lions's concentration compactness pricnciple in Hardy-Littlewood-Sobolev inequality
I'm encountering some problems when reading Lions' paper "the concentration-compactness principle in the calculus of variations. The limit case, Part 2".
The Hardy-Littlewood-Sobolev (HLS) ...
- 121
4
votes
1
answer
321
views
Sub-Gaussian random variables and convex ordering
Suppose that $X$ is a $1$-sub-Gaussian real-valued random variable, i.e. for all $t \in \mathbf{R}$, it holds that $\log \mathbf{E} \exp \left( t X \right) \leqslant \frac{1}{2} t^2 $.
Does there ...
- 1,724
2
votes
1
answer
238
views
Simplified upper bounds for moment-generating function of symmetrised random variable
Let $X$ be a nonnegative random variable such that $\mathbf{E} \left[ \exp X \right] < \infty$. For $\theta \leqslant 1$, an appropriate application of Jensen's inequality, yields that
\begin{align}...
- 128k
1
vote
1
answer
144
views
Lipschitz-type inequalities for Markov kernels
Let $K(\cdot\mid\cdot)$ be a Markov kernel. For a measure probability $\mu$, denote by $\mu K$ the probability measure induced by $K$ and $\mu$, i.e. $(\mu K)(A):=\int_\Omega \mu(d\omega)K(A\mid\omega)...
1
vote
1
answer
191
views
Concentration inequality for square roots
Given a sequence of (not-necessarily-iid) real-valued random variables $X_n$ that converge to $a\in\mathbb{R}$ in probability, suppose we have an exponential concentration inequality of the form
$$
P(|...
- 128k
1
vote
0
answers
131
views
Large-deviation inequalities for a class of simple random multivariate polynomials
Let $N$ be a large positive integer and let $[N] := \{1,2,\ldots,N\}$. For any $k$, let $K_{N,k}$ denote the collection of $k$-element subsets of $[N]$. Let $x=(x_1,\ldots,x_N)$ be a uniformly random ...
- 63.9k
1
vote
1
answer
108
views
Asymptotic scaling of mean and variance for the norm of random vector (non gaussian components)
The norm of a vector whoose components $X_i$ are normally distributed follows the Non-central chi distribution and it can be shown that, increasing the number of components $k$ (i.e. the dimension of ...
- 188k
2
votes
1
answer
150
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-...
CommunityBot
- 1
2
votes
2
answers
269
views
Asymptotic scaling of mean and variance for non-central chi distribution
Define $Y \equiv \sqrt{\sum_{i=1}^k(\frac{ X_i}{\sigma_i})^2}$, with $X_i \sim \mathcal{N}(\mu_i, \sigma_i^2)$ and independents.
It is known that $Y$ is distributed as a non-central chi (Noncentral ...
- 128k
1
vote
0
answers
121
views
Composing an Orlicz norm related to Bernstein's inequality?
This is related to my previous question, but is hopefully more precise.
I would like to reason about tail-bounds for polynomial products of concentrated random variables in $R:=\mathbb{R}[x]/(x^n-1)$.
...
- 2,183
0
votes
1
answer
124
views
Is the product of sub-Gaussian polynomials in $\mathbb{R}[x]/(x^n-1)$ sub-Gaussian?
Let $\psi_\alpha(x) := \exp(x^\alpha)-1$.
It is well-known that for $\alpha\geq 1$ that
$$\lVert X\rVert_{\psi_\alpha} = \inf\{k>0\mid \mathbb{E}[\psi_\alpha(|X|/k)] \leq 1\}$$
defines an Orlicz ...
- 2,183
5
votes
1
answer
402
views
Lower tail of random rank one sums?
Let $\{x_i\}_{i\geq 1}$ be iid random elements of the sequence space $\ell^2(\mathbb{N})$;
assume that $\|x_i\|_2 \leq 1$ almost surely. Let $\Sigma = \mathbb{E}[x_1 \otimes x_1]$.
Define
$$
\Sigma_n =...
- 380
3
votes
0
answers
70
views
Concentration for Hamming balls
It is well known that Lipschitz functions on the Boolean $n$-cube endowed with the Hamming metric satisfy concentration properties. Specifically, most of their values lie in a range of width $O(\sqrt ...
- 2,772
1
vote
1
answer
195
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 ...
- 63.9k
1
vote
0
answers
129
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 ...
- 63.9k
1
vote
1
answer
207
views
Anti-concentration inequality for the eigenvalue of Gaussian matrix
Let $f(x) = f(x_1, . . . , x_n)$ be a polynomial of degree $d$ and $\text{Var}[f] = 1$. One result by Carbery and Wright shows that for any $t\in\mathbb{R}$ and $ε > 0$,
$$
\text{Pr}_{x\sim N^n}[|f(...
- 1,724
0
votes
1
answer
182
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 ...
- 2,183
0
votes
1
answer
110
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),...
- 49
1
vote
2
answers
338
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$...
- 128k
1
vote
1
answer
308
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$ ...
- 4,529
0
votes
0
answers
195
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 ...
- 331
1
vote
1
answer
191
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)\...
- 128k
2
votes
0
answers
131
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,...
- 6,853
2
votes
1
answer
467
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^{\...
- 163
5
votes
1
answer
282
views
What is the spectral norm of a random projection times a diagonal?
Take $n\ll N$. Let $P$ be an $n\times N$ matrix of iid $\mathcal{N}(0,1)$ random variables, and let $D$ be an $N\times N$ diagonal matrix.
What can be said about the distribution of the largest ...
- 2,821
4
votes
2
answers
308
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 \...
- 10.4k
2
votes
1
answer
336
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 ...
- 128k
4
votes
2
answers
434
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 ...
- 128k
1
vote
1
answer
234
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....
- 128k
2
votes
2
answers
468
views
Concentration bound on maximum subset sum of standard Gaussians
Let $X_1, \dots, X_n$ be standard Gaussians. Let $\mathcal{S} \subseteq \{A \in 2^{\{1, \dots, n\}} : |A| = k\} $ be a family of subsets of $\{1,\dots, n\}$ with fixed size $k$. [Note that $\mathcal{S}...
- 6,853
0
votes
0
answers
142
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,183
8
votes
1
answer
534
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 ...
0
votes
0
answers
293
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$...
- 288
5
votes
0
answers
266
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\...
- 101
2
votes
2
answers
228
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,474
2
votes
1
answer
304
views
An approximation problem w.r.t marginal distribution of coordinates of uniform random vector on high-dimensional unit-sphere
Let $X=(X_1,\ldots,X_d)$ be uniformly distributed on the sphere of radius $\sqrt{d}$ in $\mathbb R^d$. Fix a "sufficiently integrable" function $h:\mathbb R \to \mathbb R$, and define ...
CommunityBot
- 1
1
vote
1
answer
229
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$, ...
- 6,853
0
votes
0
answers
152
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 ...
- 705
3
votes
1
answer
746
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. ...
- 52.4k
2
votes
0
answers
166
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 \...
- 21
2
votes
0
answers
202
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$. ...
- 1,101
3
votes
3
answers
5k
views
Hoeffding's inequality for vector valued random variables
Is there a version of Hoeffding's inequality for vector valued random variables?
This seems to be hard to find and I wonder why. I suppose it is difficult to show Hoeffding's lemma, since the proof ...
- 111
3
votes
0
answers
335
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 ...
- 223
4
votes
2
answers
343
views
Concentration of $k$-th pairwise distance of random points in a unit square
For $1\leq i \leq n$, let $X_i\sim \text{Uniform}(0,1)$, $Y_i \sim \text{Uniform}(0,1)$ be $n$ points chosen uniformly in the unit square. Denote the $k$-th smallest pairwise distances across the $n$ ...
- 662
2
votes
1
answer
143
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]...
- 14.2k
0
votes
1
answer
108
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. ...
- 1,724