Questions tagged [measure-concentration]
The measure-concentration tag has no usage guidance.
397 questions
5
votes
1
answer
248
views
General distributions with the "transportation-cost inequality" property to piece log-concave distributions
It is now known [Otto et Villani 2000; Cordero et al 2006; etc.] that on an $n$-dimensional smooth Riemannian manifold $X$ and a probability measure $\mu$ on $X$ with density $d\mu \propto e^{-V}dvol$ ...
- 6,853
2
votes
0
answers
58
views
An upper bound on $\mathbb{E}\bigg[\bigg(\sum_{i=1}^{k}(X^{\top}A_{i}X)^{2}\bigg)^{q}\bigg]$
Let $X\in\mathbb{R}^{d}$ have independent, mean zero subgaussian entries, and $A_{1},\ldots,A_{k}$ be fixed $d\times d$ matrices that have zeros on the diagonal. I would like to upper bound the ...
- 129
3
votes
0
answers
187
views
Concentration Inequalities for the Exponential of Weighted Bernoulli Sums
I want a concentration inequality for the exponential of a weighted sum of independent Bernoulli random variables around its mean, for one of my research works. I was wondering if there is a well ...
- 123
2
votes
0
answers
386
views
What is the concentration of measure for Gaussian random variables which are independent, but are transformed?
This might be a too easy question for Mathoverflow, but Googling led to similar questions and answers here (though not the one I was looking for).
The question is split into two:
I have a matrix $X \...
- 131
1
vote
0
answers
136
views
Linearly independent functions evaluated at random points create full rank matrices
Assume $f_1, f_2,...,f_n: \mathbb{R}^d\mapsto\mathbb{R}^d$ are linearly independent functions. Now let $w_1,w_2,..,w_k\in\mathbb{R}^d$ be i.i.d. Gaussian random vectors distributed as $\mathcal{N}(0,\...
- 859
4
votes
1
answer
207
views
Inner product of sorted Gaussian vector
Suppose $X_1,\ldots,X_n$ are i.i.d. standard normal. I'm wondering how to analyze the following quantity:
$$\left|\frac{X_{(1)}X_{(n)}+X_{(2)}X_{(n-1)}+\cdots+X_{(n)}X_{(1)}}{n}\right|$$
where $X_{(1)}...
- 1,495
0
votes
1
answer
254
views
Does log-concave approximable distribution satisfy transportation-cost inequality?
Definition: Recall that a distribution $\mu$ on $\mathbb R^d$ is said to be log-convave with constant $c > 0$, if density $d\nu \propto e^{-V}dvol$ satisfying the curvature condition
$$
\...
- 6,853
4
votes
0
answers
143
views
For a martingale $f_0,f_1,\ldots $ how can we bound $P(\frac{1}{n} \|f_n\| \le 1$ for all $ n \ge N)$?
Suppose $f_0,f_1, \ldots$ is a martingale (or i.i.d sequence) in $\mathbb R^d$ with $f_0=0$ and all $\|f_n - f_{n-1}\| \le L$ say. There are many concentration results for the initial segment of the ...
- 1,955
2
votes
1
answer
326
views
What is the Wiener measure of the curves with Hölder index $\frac 1 2$?
One may show that the Wiener measure (for curves in $\mathbb R^n$) is concentrated on the Hölder-continuous curves of Hölder index $< \frac 1 2$. What happens to the curves of Hölder index ...
- 5,407
1
vote
0
answers
176
views
Rate of convergence of empirical distribution with respect to Wasserstein distance induced by binary cost function
Let $\mathcal X=(\mathcal X, d)$ be a Polish space (i.e complete metric space), and let $\Omega$ be a non-empty subset. Consider the binary cost function $c_\Omega$ on $\mathcal X^2$ defined by $c_\...
- 6,853
0
votes
0
answers
1k
views
Upper-bound KL divergence between sub-gaussian variables with same variance
A random variable $X$ is said to be sub-gaussian with mean $\mu$ and pseudo-variance $\sigma^2$ iff
$$\mathbb \log(E[\exp(t(X-\mu))]) \le \frac{t^2}{2\sigma^2},\;\forall t \in \mathbb R.
$$
It's a ...
- 6,853
10
votes
2
answers
849
views
Minimum separation among $m$ random points on an $n$-dimensional unit sphere
Consider $m$ points $v_1, \ldots, v_m \in R^{n}$, which are uniformly distributed on the $n$-dimensional unit sphere $S^{n-1} = \{v:\|v\|_2 = 1\}$. Let the minimum separation be
$$
\rho = \min_{i,j\in{...
- 1,127
1
vote
1
answer
146
views
Concentration properties of inner-products in high-dimension
Let $S^K$ be the unit sphere embedded in $R^{K+1}$.
$v \in S^K$ is randomly chosen from a uniform distribution over $S^K$.
$A \subseteq S^K$ is a $d$-dimensional sub-manifold ($d \leq K$). Think of ...
- 615
1
vote
1
answer
91
views
A distribution which is Wasserstein-close to a compactly supported distribution is almost compactly supported
I wonder whether this is true: If a distribution is very close (in the Wassertein sense) to another distribution with compact support, then the former must put only tiny amount of mass outside a ...
- 6,853
3
votes
1
answer
305
views
Concentration of measure in graph theory
I am looking for elementary statements in graph theory that illustrate the concentration of measure phenomenon.
(Say, something bit more interesting than most of graphs have diameter 2.)
- 45k
3
votes
0
answers
160
views
Does there exist a compactly supported integrable function with infinite Coulomb energy?
The title of the question pretty much says it all. I am looking for a function $f\in L^1(\Omega)$, where $\Omega \subset \mathbb{R}^3$ is a bounded domain, such that
$$
E[f] = \iint\limits_{\Omega\...
- 401
1
vote
1
answer
138
views
Approximate $\log \mathbb E_P[\exp(th(x)]$ for a function $h$ which is lipschitz and has finite moments of order 1 and 2 w.r.t $P$
Let $P$ be a probability measure on a space $\mathcal X$ and $h: \mathcal X \rightarrow \mathbb R$ is measurable function with finite moments of order 1 and 2. I'm interested in approximating the ...
- 6,853
0
votes
0
answers
58
views
Bounds on $\inf_{x,x' \in \mathbb B_X}TV(P+x,Q+x')$, where $P$ and $Q$ are distributions with density on the space $X=(\mathbb R^n,\ell_p)$
Let $n \ge 1$ be an integer, $p \in [1,\infty]$, and $P$ and $Q$ be two (probability) measures on the metric space space $X=(\mathbb R^n,\ell_p)$ which have densities w.r.t the Lebesgue measure on $X$,...
- 6,853
1
vote
0
answers
166
views
What exactly is and is not a concentration inequality?
Hoeffding's inequality is surely a concentration inequality. It can be written in the form:
$\Pr(\bar X + f(n,\delta) \geq \mu) \geq 1-\delta,$
for some function $f$, where $X$ is a set of i.i.d. ...
- 399
0
votes
1
answer
239
views
Anti-concentration: upper bound for $P(\sup_{a \in \mathbb S_{n-1}}\sum_{i=1}^na_i^2Z_i^2 \ge \epsilon)$
Let $\mathbb S_{n-1}$ be the unit sphere in $\mathbb R^n$ and $z_1,\ldots,z_n$ be a i.i.d sample from $\mathcal N(0, 1)$.
Question
Given $\epsilon > 0$ (may be assumed to be very small), what is ...
- 6,853
3
votes
1
answer
196
views
Uniform Convergence for Vectors
$\textbf{Problem statement:}$
Let $\mathcal H:\mathcal X \rightarrow \{0,1\}$ be a class of Boolean functions for $\mathcal X \subset \mathbb R^n$, and let the VC Dimension of $\mathcal H$ be $VC_{...
- 197
2
votes
1
answer
181
views
Generalization of Komlós–Major–Tusnády Approximation
The Komlós–Major–Tusnády Approximation (see Wikipedia) considers the sum of uniform variables in $(0,1)$. There are also version where instead the sum of equiprobable $0/1$ variables is used ($p=1/2$)....
- 23
2
votes
2
answers
1k
views
Lower bound on number of samples for an epsilon delta approximation matching the Chernoff bound
So we have two biased coins, one comes out head w.p. $1/2+\epsilon$ and the other w.p. $1/2-\epsilon$. How many times should we flip these two coins to be able to tell them apart w.p. at least $\delta$...
3
votes
1
answer
165
views
Non-asymptotic tail bounds for $D_{\text{Hellinger}}(P\|\hat{P}_N)$
Let P be a distribution on a finite set of size $k$ and let $\hat{P}_N=(N_1/N,\ldots,N_k/N)$ be the empirical distribution (frequencies) from a samples of size $N$. Consider the Hellinger distance ...
- 6,853
8
votes
2
answers
1k
views
Does Multiplicative Version of Azuma's Inequality Hold?
It is known that there are multiplicative version concentration inequalities for
sums of independent random variables. For example, the following
multiplicative version Chernoff bound.
Chernoff bound:...
- 175
4
votes
0
answers
183
views
Regularity of optimal transport of Gaussian mixtures
In one of the problems that I am working on, I came across the topic of smoothness of optimal transport for Gaussian mixtures. In particular, let $P=P_\theta=\sum_{i=1}^k \frac{1}{k}\mathcal{N}(x| \...
- 161
3
votes
2
answers
395
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$, ...
- 127
1
vote
0
answers
676
views
Are Outer Products of Sub-Gaussian Vectors Sub-Exponential?
$\newcommand\xx{\mathbf{x}}\newcommand\yy{\mathbf{y}}\newcommand\A{\mathbf{A}}\newcommand\aalpha{\boldsymbol{\alpha}}\newcommand\bbeta{\boldsymbol{\beta}}\newcommand\E{\mathbb{E}}\newcommand\inner[1]{\...
- 153
8
votes
2
answers
487
views
concentration inequality for entropy from sample
Consider a measure $\mu$ on a finite set, and let $x_1, \ldots, x_n$ be i.i.d samples from $\mu$. Then the expression $S_n = -\frac{1}{n} \sum_{i=1}^n \log \mu(x_i)$ converges by a.s. to the entropy $...
- 83
10
votes
1
answer
846
views
A Johnson-Lindenstrauss lemma for finite fields?
Given $m$ points in $\mathbb{R}^N$, the Johnson-Lindenstrauss lemma guarantees the existence of a linear operator $\mathbb{R}^N\rightarrow\mathbb{R}^n$ that nearly preserves pairwise distances between ...
- 7,633
5
votes
1
answer
372
views
What are some of results in low dimensional statistics that do not hold in high dimensions?
This question is partially inspired by the following MO post: What are some of the surprising results of finite sample statistical estimation? and current heated research front of high dimensional ...
- 8,071
1
vote
0
answers
123
views
Sanov-type finite-sample bound on $KL(P\|\hat{P}_n)$
Let $P$ be a distribution on an alphabet of size $k$ and let $\hat{P}_n$ be an empirical version of $P$ via $n$ i.i.d samples $a_1,\ldots,a_n \sim P$, i.e $\hat{P}_n := (1/n)\sum_{i=1}^n\delta_{a_i}$.
...
- 6,853
1
vote
0
answers
79
views
Showing that additive Gaussian noise never increases sparsity
Let $\mathbf{1}\in\mathbb{R}^d$ be the $d$-dimensional all-ones vector and let $n\sim\mathcal{N}(0, \sigma^2 I_{d\times d})$, show that
$$ \frac{\| \mathbf{1} + n \|_1}{\|\mathbf{1} + n \|_2} \ge c \...
- 392
5
votes
0
answers
543
views
Vector martingale concentration
Let $\varepsilon_1, \dots, \varepsilon_N$ be a martingale difference sequence in $R^d$ with $\|\varepsilon_n\| \le B_n, a.s.$ for each $n=1,\dots,N$. Do we have some Azuma-type concentration ...
- 719
7
votes
2
answers
606
views
Uniform Concentration Bounds on Weighted Sum of i.i.d. Bernoulli Random Variables
Let $\delta_1,...,\delta_n$ be $n$ independent identically distributed Bernoulli random variables with $\mathbb{P}(\delta_1=1)=p$. We consider a set $\Omega = \{\mathbf{a}:=(a_1,...,a_n)~|~a_i\in [0,c/...
- 71
3
votes
1
answer
294
views
Concentration inequalities specialized for log-likelihood / log-density functions
Let $P$ be a probability measure and $f$ be some probability density function (not necessarily related to $P$). Consider the function
$$
L(X_1,\ldots,X_n)
=\frac1n\sum_{i=1}^n\log f(X_i),
\quad
X_i\...
- 710
1
vote
1
answer
118
views
What is the order of the left tail of a mixture of non-central chi-square?
Let $\mu\sim N(0,1)$, $Z\sim N(\mu,1)$. Then $Z$ can be viewed as a mixture of Gaussians. It can also be viewed as a Gaussian but there is a prior for the mean.
Let $X\sim\exp(\lambda)$ where the ...
- 1,495
1
vote
0
answers
175
views
Matrix Bernstein for spherical random variables
Theorem 4.1 in Tropp's Matrix Concentration Inequalities provides an exponential concentration inequality for the spectral norm of a matrix $Z = \sum_i \gamma_i B_i $, where $\gamma_i$ are an i.i.d. ...
- 111
9
votes
1
answer
1k
views
Doob Martingale: Where is the catch?
I am working on a research problem in uncertainty propagation that involves sums of possibly dependent random variables with bounded sets of support.
I am attempting to use the method of bounded ...
- 219
1
vote
0
answers
105
views
Gaussian isoperimetry for $\ell_p$ norms
Let $\gamma_n$ be the standard Gaussian measure on $\mathbb R^n$. It is well-known (e.g see Proposition 1) that for a given Gaussian volume content, half-spaces $H=\{x \in \mathbb R^n | a^Tx \le b\}$ ...
- 6,853
4
votes
0
answers
162
views
Are sums extremal for subgaussian concentration?
Bobkov and Houdre https://projecteuclid.org/euclid.bj/1178291721
showed that among all $f:R^n\to R$ that are $1$-Lipschitz
with respect to the $\ell_1$ metric,
the variance is maximized by sums. ...
- 6,541
3
votes
0
answers
166
views
Matrix Chernoff sampling with out replacement
I am interested to know if the matrix Chernoff bound (see Theorem 5.1.1 in https://arxiv.org/pdf/1501.01571.pdf) holds if one samples without replacement.
For example, the Bernstein inequality is ...
- 221
1
vote
0
answers
173
views
Upper bound for $\sup_{W_d(Q, P) \le \epsilon} Q(A)$, where $W_d$ is the Wasserstein metric
Let $X=(X,d)$ be a metric space and let $W_d$ denote the Wasserstein metric induced by this metric, on the space of probability distributions on $X$. Let $\epsilon \ge 0$, $A$ be a Borel subset of $X$...
- 6,853
5
votes
1
answer
295
views
Constructive Central Limit Theorem
Background: Let $\{a_i\}_{i=1}^n$ be i.i.d. random variables with zero-mean and unit variance, on a probability space $\Omega$. Define $$s_n=\frac{1}{\sqrt{n}}\sum_{i\leq n} a_i$$
Central limit ...
- 159
1
vote
1
answer
249
views
On concentration of a sum random variable
Take a random variable defined as
$$r=u_{11}v_{1}v_{1}+u_{12}v_{1}v_{2}+\dots+u_{n,n-1}v_{n}v_{n-1}+u_{nn}v_{n}v_{n}$$ where $v_{i}$ are independent uniform random variables from $\{0,\dots,b\}$, $u_{...
- 13.9k
4
votes
0
answers
116
views
$\ell_p$ geodesic distance on smooth Riemannian manifold and Logarithmic Sobolev Inequalities
Bear with me, I'm not a professional geometer. Recently, I've been studying Logarithmic Sobolev Inequalities (LSI) for probability distributions on manifolds (e.g as done in works of Bobkvo et al. ...
- 6,853
18
votes
1
answer
1k
views
How fast can extreme eigenvalues of the average of random matrices converge to their expectation?
Suppose that $X_1,X_2,\ldots,X_m$ are independent $d\times d$ random matrices and let $\overline{X} := \frac{1}{m}\sum_{i=1}^m X_i$. One of the questions studied under the theory of random matrices is ...
- 181
4
votes
1
answer
681
views
Tail bound for product of normal distribution
Let $U, V$ be two standard normal random variables with covariance $cov(U,V) = \beta \in [0,1)$. Let $W = UV$ be the product of two RV's, and $W_1, W_2, \ldots, W_n$ be n i.i.d copies of $W$, what's ...
- 515
4
votes
1
answer
229
views
Product of estimates of mean values - Concentration of measure inequality
Let $X_{1},...,X_{d} \in \{-1,1\}^d$ be random variables, with $E[X_j]=\mu_j$. Having $n$ i.i.d. samples $x^{(i)}_1,x^{(i)}_2,....,x^{(i)}_d$, $i=1,...,n $, let $\hat{\mu}_{j}=\frac{1}{n}\sum^{n}_{i=1}...
- 107
2
votes
1
answer
167
views
Concentration of emperical conditional probability
Assume sequence $(X_1,X_2, X_3, \ldots)$ is a first-order Markov sequence of real random variables where $X_i \in \mathcal{X}$ for some alphabet $\mathcal{X}$ of finite size $k$. Define emperical ...
- 33