Skip to main content

Questions tagged [measure-concentration]

Filter by
Sorted by
Tagged with
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| \...

1
4
5
6 7 8