Questions tagged [measure-concentration]
The measure-concentration tag has no usage guidance.
382
questions
-1
votes
1
answer
118
views
On the concentration of Lipschitz functions near its expectation, where the vector has identical but not independent, components
Consider the random vector $X:=(X_1\dots X_1) \in \mathbb{R}^n, X_1 \sim \mathcal{N}(0,1).$ Notice the identical components, they're identically distributed but not independent.
Now, I was wondering ...
- 1,417
3
votes
1
answer
124
views
About concentration of eigenvalues values of a random symmetric matrix in a specific interval
Given a random symmetric matrix $M$ and two numbers $\lambda_\min$ and $\lambda_\max$ how do we calculate the expected or high probability value of the fraction of its eigenvalues which lie in the ...
- 2,146
4
votes
0
answers
105
views
Upper bound $\tau_C := \int_{\|x\| \le 1}(vol(C \cap (x + C))/vol(C))dx$ for a convex body $C \subseteq \mathbb R^n$, by reducing to a ball
Let $C$ be a convex body in $\mathbb R^n$, i.e a bounded convex subset of $\mathbb R^n$ which has nonempty interior, and which is (A) open, or (B) closed (I'm not sure one makes more sense; choose the ...
- 6,726
3
votes
1
answer
952
views
Explicit constant for Carbery–Wright inequality
The Carbery–Wright inequality is a seminal result about the anti-concentration of polynomials of Gaussian random variables.
See e.g. Meka, Nguyen, and Vu - Anti-concentration for polynomials of ...
- 91
0
votes
1
answer
337
views
Concentration of norm of linearly transformed normal random vector as dimension go to infinity
Earlier asked on MSE, but didn't get an answer, so posting here:
Let $X=(X_1 \dots X_n) \in \mathbb{R}^n, X_i\sim N(0,1), iid.$ Let $B: \mathbb{R}^n \to \mathbb{R}^n $ be the diagonal linear map: $...
- 1,417
0
votes
1
answer
54
views
Good upper-bound for $\mathbb E_A[e^{-t\|A\|_2}]$, for $t\ge0$ and random m by n matrix with iid entries with law $N(0,1)$
Let $A$ be a random $m$-by-$n$ matrix with iid $N(0,1)$ entries, $m$ and $n$ large with $n/m \longrightarrow \alpha \in (0, 1)$ . Let $\|A\|_2$ be the largest singular value of $A$ (i.e the spectral ...
- 6,726
3
votes
0
answers
295
views
Upper-bound for eigenvalues of $E [UU^T]$, where $U$ is uniformly distributed on the unit $n$-sphere
Let $X$ be a $\sigma$-subGaussian random vector on $\mathbb R^n$ (for large $n \ge 3$), meaning that the random variable $X^Tv$ is $\sigma$-subGaussian for every unit vector $v \in \mathbb R^n$. ...
- 6,726
2
votes
0
answers
485
views
Comparison of concentrations of different $L^p$-norms of (sub) Gaussian distributions
It's well-known that the Euclidean $2$-norm of subgaussian random vectors concentrates in high dimensions, e.g. when $X \sim \mathcal{N}(0,I_n),$ (or in general $X$ is subgaussian with independent co-...
- 1,417
5
votes
1
answer
160
views
Is there an i.i.d sequence in the unit cube $[-1,1]^d$ with $\mathbb E \left[ \Big \| \sum_{i=1}^N X_N \Big \|_\infty\right] = \sqrt {dN}$?
There are loads of concentration results for sums of scalar-valued independent sums $X_1,X_2,\ldots, X_N$ with $\mathbb E[X_n]=0$. For example Hoeffding's Inequality says if all $|X_1|\le 1$ then $\...
- 1,761
0
votes
1
answer
124
views
Tail bounds for the absolute difference of a coupled pair of sub-Gaussian random variables
Let $P$ and $Q$ are sub-Gaussian distributions on $\mathbb R$, and $(X,X')$ be a coupling of $P$ and $Q$, i.e $(X,X') \sim \pi$ for some distribution on $\mathbb R^2$ with marginals $P$ and $Q$.
...
- 6,726
1
vote
1
answer
73
views
Use $\mathbb{P}(\vert \hat{s}_n-s\vert > x)\leq a(n,x)$ and $\mathbb{P}(\vert \hat{s}_n-s_n\vert > x)\leq b(n,x)$ to bound $\vert s_n - s\vert$
Let $s, s_n\in\mathbb{R}$ and $\hat{s}_n$ be a random variable.
I have two concentration inequalities:
$$\mathbb{P}(\vert \hat{s}_n-s\vert > x)\leq a(n,x)$$ for all $n\geq1$ and $x>0$;
and
$$\...
- 11
2
votes
0
answers
57
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
1
answer
977
views
Chernoff-type bound for sum of Bernoulli random variables, with outcome-dependent success probabilities
Let $X = (X_1, X_2, \ldots, X_n)$ be a sequence of (not necessarily independent) Bernoulli random variables where for each $i$, the success probability $\Pr[X_i = 1]$ itself is a random variable ...
- 153
0
votes
1
answer
251
views
Sum of sequences of random variables, with variable success probabilities
Consider two sequences of (not necessarily independent) Bernoulli random variables $X_1, X_2, \ldots, X_n$ and $Y_1, Y_2, \ldots, Y_n$. Suppose that for any $i$, we have $\Pr[X_i = 1] = \Pr[Y_i = 1] = ...
- 153
7
votes
3
answers
388
views
Chernoff-type bounds for a stopped sum of independent random variables
Let $Y_1, \ldots, Y_n$ and $X_1, \ldots, X_n$ be i.i.d. $p$-Bernoulli random variables and let $T \in \{0, \ldots, n\}$ be a stopping time for the process. From Wald's equation, we know
$$
E\left[\...
- 153
2
votes
1
answer
175
views
Concentration in Markov chains
Consider a discrete state space $\mathcal{X}$. The expander Chernoff inequality gives subgaussian concentration for the sample mean $\frac1n \sum_{t=1}^n f(X_t)$ for some function $f : \mathcal{X} \to ...
- 287
3
votes
1
answer
1k
views
Gaussian concentration inequality
Recently I found a concentration inequality for infinite dimensional Gaussian r.v.s in this paper. Specifically, Lemma 4 on page 307 states (without a proof) that
There exists a universal constant $...
- 185
3
votes
2
answers
1k
views
Concentration of sum of concentrated random variables
I have a sum of positive random variables, they are not identically distributed, but even that case would be interesting. They are not necessarily independent, but I already have a concentration bound ...
- 223
1
vote
0
answers
273
views
Strong data-processing inequality ? Upper bound on a certain modified total-variation metric
Let $\mathcal X=(\mathcal X,d)$ be a Polish space equipped with the Borel sigma-algebra. Let $p\ge 1$ and $P_1,P_2$ be probability distributions on $\mathcal X$ such that $\max_{k=1,2}\int d(x,x_0)^...
- 6,726
0
votes
0
answers
186
views
Distance between two sample quantiles
Let $X_1,\dots X_n$ be i.i.d. samples from an unknown distribution. We know the distribution has uniformly bounded probability density function $f(x)$. Let $1>\tau_1>\tau_2>0$ be two quantile ...
- 323
0
votes
1
answer
115
views
Compute lower bound on $\min_{E} \mathcal N(0,\sigma^2 I_n)(E)$ subject to $vol(E \cap H_n(r)) / vol(H_n(r)) \ge p$ where $H_n(r)$ is $n$-hemisphere
Let $n \ge 2$ be an integer, which may be assumed to be very large. For $r > 0$, consider the hemi-sphere $H_n(r) := S_n(r) \cap (\mathbb R^+ \times \mathbb R^{n-1})$, where
$$
S_n(r):= \{x \in \...
- 6,726
2
votes
2
answers
401
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}...
- 151
1
vote
1
answer
2k
views
Tail bound regime for Binomial distribution in concentration paper
In paper 'Concentration Inequalities and Martingale Inequalities:A Survey' gives the following inequality:
My question is whether the inequality holds in regime $\lambda$ being $o(\sqrt n)$ (say $\...
- 1,816
4
votes
3
answers
359
views
Maximum of independent, unit-variance Gaussians with non-zero means
Suppose $X_1,\dots,X_n$ are independent Gaussians, where $X_k \sim N(\mu_k,1)$. I am interested in
$$
Z \stackrel{\rm def}{=} \max_{1\leq k\leq n} X_k
$$
and specifically on the asymptotics of $\...
- 1,342
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,726
3
votes
1
answer
301
views
Concentration of monochromatic edges in a graph
Let $G$ be a graph of order $n$ with $m$ edges. Color each vertices uniformly at random with $q$ colors. It is easy to see that expected number of monochromatic edges (edge whose end vertices are of ...
2
votes
2
answers
496
views
Chaining tail bound for centered sub-Gaussian process?
On page 5 of a recent manuscript by Lugosi-Mendelson, a claim equivalent to the following statement is made:
Suppose $Z$ is a centered, $\mathbf{R}^d$-valued random variable with $\mathbf{E} e^{\...
- 342
1
vote
0
answers
192
views
Concentration inequalities for beta random variables
Let $X$ be a random variable having a beta distribution $$f(x)=\frac{\Gamma(\alpha)\Gamma(\beta)}{\Gamma(\alpha+\beta)}x^{\alpha-1}(1-x)^{\beta-1}$$with mean $\mu=\frac{\alpha}{\alpha+\beta}$, and ...
- 11
2
votes
1
answer
97
views
Concentration of measure on finite powers of $S^\infty$
I am wondering about a natural generalization of theorem 1.4 in the article Dvoretzky's theorem — Thirty years later by Milman. My first thought was to look at Milman's paper that he cites for the ...
- 10.3k
4
votes
1
answer
412
views
Central limit theorem for resampling
This is a cross-post from stats.stackexchange.com. No answer has appeared there. Since this is a theoretical question, mathoverflow.net seems to be a more appropriate venue for it.
What is the analog ...
- 2,169
4
votes
1
answer
405
views
Concentration inequality for the law of iterated logarithm
The following question arose in one of my research projects. Before stating it, let me give a short background. We all know the law of iterated logarithm. It states that if $X_1,\ldots,X_n$ are i.i.d. ...
- 123
1
vote
0
answers
146
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,726
3
votes
0
answers
169
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
1
vote
1
answer
364
views
Sketching Frobenius norm of a tensor with a rank-1 random tensor
Let $A\in\mathbb{R}^{n^k}$ be a $k$-dimensional tensor with $n$ elements along each dimension. Moreover suppose $u_1,u_2,\dots,u_k\sim\text{Unif}(\pm1)^n$ are $n$ dimensional vectors with each of ...
- 175
1
vote
1
answer
244
views
(Novel?) notion of concentration/dispersion
Consider the measurable space $(\Omega,\mathscr{B})$ endowed with two positive measures: a "volume $\nu$" and a probability measure $\mu$. For example, one might take $\Omega=\mathbb{R}^n$ (with the ...
- 6,061
1
vote
0
answers
130
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
2
votes
1
answer
251
views
Bernstein Inequality for continous local martingale
I'm looking for a simple proof of the following fact, which is somehow Bernstein inequality in continuous time.
Let $(M_t)_{t\geq 0}$ be a continuous local martingale. Then :
$$P\left(\sup_{t\in [0,...
- 245
4
votes
0
answers
131
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,761
3
votes
1
answer
184
views
Isoperimetry on $[0, 1]^n$ w.r.t $\ell_p$ distance, with $p \in [1,\infty]$
Let $A$ be a measurable subset of the metric space $\mathcal X = ([0, 1]^n,\ell_p)$ with $1 \le p \le \infty$, and define its $\varepsilon$-blowup by $A^\varepsilon:=\{x \in \mathcal X \mid \|x-a\|_p \...
- 6,726
6
votes
1
answer
198
views
Good upper-bound for $\mathbb E[|X-np|^r]$ where $X \sim \text{Binomial}(n,p)$ and $r \ge 1$
Disclaimer. Question moved from SE.
Setup
Let $X \sim \text{Binomial}(p, n)$, and $r \ge 1$.
Question
What is a good upper-bound for $\mathbb E[|X-np|^r]$ ?
Solution for small $r$
If $r=2$, then ...
- 6,726
7
votes
1
answer
360
views
Do i.i.d. sums concentrate any faster than martingales?
Suppose $X_1,X_2, \ldots, X_N \in \mathbb R^d$ are random variables with each $\|X_n\|_2 \le 1/2$ (this choice of the constant simplifies later formulae).
The simplest concentration inequality I know ...
- 1,761
5
votes
0
answers
542
views
Concentration inequality for max component of a multivariate Gaussian in the general case
I am looking to bound the variance of the maximum component of a vector distributed multivariate Gaussian in the general case where the Gaussian distribution has arbitrary mean and full covariance ...
- 271
1
vote
0
answers
75
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
1
vote
2
answers
230
views
Finite-sample deviation bound of empirical distribution from true distribution
Let $P=(p_1,\ldots,p_k) \in \Delta_k$ be distribution supported on set of size $k$ and let $\hat{P}_n$ be an empirical version of $P$ based on an iid sample of size $n$.
Question
What's a good non-...
- 6,726
4
votes
1
answer
231
views
Uniform inequality of the form $\text{Proba}(\sup_{v \in [-M,M]^k}|p^Tv-\hat{p}_n^Tv| \le \epsilon_n) \ge 1 - \delta$
Let $M > 0$, $k$ be a positive integer, and $\mathcal V:=[-M,M]^k$. Finally, let $p \in \Delta_k$, (where $\Delta_k$ is the $(k-1)$-dimensional probability simplex) and let $\hat{p}_n$ be an ...
- 6,726
1
vote
0
answers
77
views
Concentration inequality for Lipschitz functions with orthogonal gradients
Let $f_j:\mathbb{R}^n\to\mathbb{R}$ be a set of 1-Lipschitz functions for $1\leq j\leq M$. From Gaussian isoperimetry or a log-Sobolev inequality, it can be shown that
$$
\mathbf{Pr}(|f_j(X)-\mathbf{...
- 337
1
vote
0
answers
113
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,726
1
vote
1
answer
291
views
Bounds on difference between "logsumexp" and variance?
Let $Z$ be a random variable with finite moment-generating function $M_Z(\theta):=E[e^{\frac{1}{\theta}Z}]<\infty$ for all $\theta > 0$, and for $\delta \in (0,1]$, define
$C_Z^\delta := \inf_{\...
- 6,726
1
vote
0
answers
153
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. ...
- 389
3
votes
0
answers
148
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