Questions tagged [measure-concentration]
The measure-concentration tag has no usage guidance.
397 questions
4
votes
0
answers
643
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-...
5
votes
1
answer
166
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 $\...
0
votes
1
answer
140
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$.
...
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 ...
3
votes
1
answer
1k
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 ...
0
votes
1
answer
273
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] = ...
3
votes
1
answer
2k
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 $...
2
votes
1
answer
637
views
Azuma's Inequality when the conditions hold with high probability?
In Azuma's Inequality, is the statement true when $|X_k - X_{k-1}| < c_k$ almost surely rather than with probability 1? If not, is there another result which gives strong concentration when the ...
2
votes
1
answer
194
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 ...
1
vote
0
answers
334
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)^...
0
votes
0
answers
223
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 ...
0
votes
1
answer
116
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 \...
2
votes
1
answer
3k
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 $\...
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$,...
3
votes
1
answer
308
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
543
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^{\...
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 ...
2
votes
0
answers
222
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 ...
4
votes
1
answer
431
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 ...
7
votes
1
answer
409
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
votes
2
answers
614
views
Bounded difference functions and sub-Gaussian random variables
We have the following standard theorem : Let $X$ be some set and $g : X^n \rightarrow \mathbb{R}$ be a measurable function such that it satisfies the ``bounded difference property" i.e $\exists$ $\{...
1
vote
1
answer
391
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 ...
2
votes
1
answer
287
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,...
4
votes
1
answer
431
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. ...
5
votes
2
answers
565
views
Concentration of U-statistics for exchangable distributions (and the unbounded case)
Consider the following so-called $U$-statistic of order 2: $$U = \frac1{\binom{m}{2}} \sum_{i < j} h(w_i,w_j)$$ where $w_1,\dots,w_m$ are IID from some distribution and $h$ is symmetric. If $|h(w_1,...
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_\...
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 ...
1
vote
1
answer
249
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 ...
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,\...
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 ...
6
votes
1
answer
203
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 ...
5
votes
0
answers
714
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 ...
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 \...
1
vote
2
answers
250
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-...
1
vote
0
answers
109
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{...
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}$.
...
1
vote
1
answer
313
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_{\...
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. ...
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\...
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\}$ ...
3
votes
1
answer
827
views
concentration inequality for a weighted sum of independent but not identical binary variables
Let $\alpha\in[0,1]$ be a fixed constant, and let
$w,x\in[0,1]^n$ be two vectors such that $\sum_i w_i x_i=\alpha$.
Define $Y = \sum_i w_i X_i$, where $X_i \sim \operatorname{Bernoulli}(x_i)$, so it ...
7
votes
1
answer
976
views
Prove an anti-concentration inequality for a martingale
My problem can be described easily:
I have a sequence $(X_l)_{l \in \mathbb{N}}$ of r.v. adapted to some filtration $(\mathcal{F}_l)_{l \in \mathbb{N}}$, such that
$\left|X_{l+1}-X_l\right|\le R$ a. ...
2
votes
1
answer
850
views
Concentration inequality for quadratic form of Gaussian variables with non-idempotent matrix
Given $y \sim N(0,\sigma^2 I)$, and $M$ that is a symmetric matrix (not necessarily idempotent)
what is the distribution of ${y^T M y}$?
is there a high probability bound on $|{y^T M y}|$?
Most ...
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_{...
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 ...
12
votes
2
answers
2k
views
Can we do better than Azuma-Hoeffding when the variance is small?
The Azuma-Hoeffding Inequality says that if $X_1,X_2, \ldots$ is a martingale and the differences are bounded by constants, $\|X_i - X_{i-1}\| \le 1$ say, then we should not expect the difference $\|...
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:...
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 ...
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)}...
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| \...