Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [concentration-of-measure]

Use this tag for questions about the principle that a random variable that depends in a Lipschitz way on many independent variables (but not too much on any of them) is essentially constant.

-1
votes
0answers
27 views

Comapring tail bounds

Assume that for random variables $X$ and $Y$, for all real values $a$, we have $E\{\max(X-a, 0)\}\leq E\{\max(Y-a, 0)\}$. Also assume $$\forall t\geq 0 \;\;\; P(|Y|\geq t) \leq k e^{-bt}$$ for some $...
2
votes
1answer
34 views

Relative Entropy and the Wasserstein distance

Can anyone give an informative example of two distributions which have a low Wasserstein distance but high relative entropy (or the other way around)? I find the Wasserstein defined (for some $p$) as ...
3
votes
1answer
82 views

Mean concentration implies median concentration

Exercise 2.14 in Wainwright, "High-Dimensional Statistics", states that if $X$ is such that $$P[|X-\mathbb{E}[X]|\geq t] \leq c_1 e^{-c_2t^2},$$ for $c_1, c_2$ positive constants, $t\geq 0$, then for ...
1
vote
1answer
41 views

Help with an application of Young's inequality

I am reading through a set of notes about concentration of Gaussian measure, and on page 56, they make the following claim that I am failing to see the proof of: Now we estimate the second summand ...
1
vote
0answers
9 views

Product of distributions satisfying log-sobolev inequality

Let $f,g\in C^\infty(\mathbb{R})$ be two smooth positive functions satisfying $\int f = \int g = 1$. Suppose that both $f$ and $g$ satisfy the log-Sobolev inequality (LSI) with constant $C$, so that ...
1
vote
1answer
47 views

Sub-Gaussian and “nearly” sub-Gaussian random variables

Define $\Psi_{X}(\lambda) = \log E e^{\lambda X}$, and suppose that $EX=0$. We say that the random variable $X$ is sub-Gaussian with variance factor $v$ if: $$\Psi_{X}(\lambda) \leq v\lambda^{2}/2$$ ...
1
vote
0answers
41 views

When is the measure of spherical cap large?

It is known that in high dimensions, the measure of the spherical cap is small, due to the measure concentration for the sphere. In particular, we have the following inequality in $n$ dimension: $$ 1-\...
1
vote
0answers
12 views

Gaussian concentration of measure, equivalent definitions

I need some help going between two equivalent definitions. First some notation : $\bullet$ For $A\subseteq \mathcal{X}$ and $r>0$ define what is called the r-blowup of $A$ as \begin{equation} ...
1
vote
2answers
37 views

Wasserstein attains its infimum

let $(\mathcal{X},d)$ be a Polish space. For $p\geq1$ let $\mathcal{P}_p(\mathcal{X})$ be the space of all Borel probability measures $\mu$ on $\mathcal{X}$ such that \begin{equation} \mathbb{E}_\mu\...
4
votes
2answers
62 views

What is the expectation of the rank of a matrix with a 1 at each column?

Say a random square matrix $A\in\mathbb{R}^{n\times n}$, each column of $A$ has exactly one nonzero element being 1, i.e. each column looks like $e_i=\{0,\dots,1,\dots,0\}^\top$. Say for each column, ...
2
votes
0answers
20 views

Wasserstein distance between hyperplane and cube

Let $\mu$ be the uniform measure on the cube $Q = [-1,1]^n$, and $\nu$ be the uniform measure on the surface $$ V = \{(x_1,\dots,x_n)\in Q \mid \sum x_i = 0\}. $$ I am curious about Wasserstein ...
0
votes
1answer
54 views

Bounding sub-Gaussian tail events by Gaussian tail events?

Background I have come across a problem where I want to derive a concentration inequality for sub-gaussian random variables. More precisely, I want to bound the spectrum of a certain empirical ...
2
votes
1answer
66 views

Concentration of the measure of a general covariance-like matrix

I consider a random matrix of the type : $M_n = \frac{1}{n} X_n D_n X_n^\intercal \in \mathbb{R}^{n \times n}$, in which all matrices are square of size $n$. $D_n$ is a deterministic diagonal matrix ...
1
vote
0answers
107 views

Concentration inequality for median

$\xi_1,\xi_2,\ldots,\xi_n$ are iid sub-Gaussian random variables (i.e, $P(\xi_1>t)\leq e^{-t^2/2}$ for $t>0$) with mean $0$ and $a_1,a_2,\ldots a_n$ are some real numbers. Define $a_0:= \lim_{...
1
vote
1answer
59 views

Know the concentration estimate expectation?

Here is the problem: let $X$ be a random variable such that: $$P\{X > c(m+t) \}<2e^{-t^2} \ \ \ \forall t >0$$ where $c>0,m>0$ are constant. Then I was asked to prove that : $$ \...
1
vote
1answer
20 views

Help on application of Marton's transportation method (Bucheron-Lugosi-Massart)

I was trying to apply Marton's transportation inequality in the following exercise from Bucheron, Lugosi, Massart's text on concentration inequalities: Exercise 8.1. Use Marton's transportation ...
0
votes
0answers
57 views

Upper bound of moment generating function for a non-negative random variable

Let $X_{1}, X_{2}, \cdots, X_{N}$ be non-negative independent random variables with continuous distributions. Assume that the densities of $X_{i}$ are uniformly bounded by 1. Problem: show that the ...
0
votes
0answers
55 views

Sum of variables of a martingale

I have the sequence $X_1, X_2,...X_n$ as a martingale, each of which is bounded. Now I want to explore some upper bound for the sum $S_n=X_1+X_2+...+X_n$, e.g., the format like Hoeffding inequality or ...
0
votes
0answers
21 views

Calculating expectations of concentrated random variables of bounded-differences type

Is there a nice general way of calculating the expectation variable for which I can derive concentration bounds using the method of bounded differences? I have seen quite a few application of the ...
0
votes
1answer
41 views

Confidence interval of a biased estimator that's asymptotiacally unbiased.

Suppose I have an estimator $\hat{\theta}_n$ of $\theta$ where $\mathbb{E}[\hat{\theta}_n] \neq \theta$, but I do know that $\displaystyle\lim_{n \to \infty} \mathbb{E}[\hat{\theta}_n] = \theta$. ...
2
votes
0answers
34 views

$X^TXw$ is normal?

I'm reading a paper in which it claims that if the matrix $X \in \mathbb{R}^{n \times n}$ has elements which are normal and independent, then for an arbitrary vector $w$, $X^TXw$ is distributed as $\...
1
vote
0answers
26 views

Concentration of Gaussian random matrices

I know that if $X$ be a random matrix distributed as $N(0,I_n)$, then $\frac{1}{n}X^TX$ is concentrated around the identity matrix. Does any body know the probability of $P(||\frac{1}{n}X^TX-I||<\...
4
votes
1answer
148 views

Variance of the Euclidean norm under finite moment assumptions

Let $X = (X_1,X_2 \cdots X_n)$ be random vector in $R^n$ with independent coordinate $X_i$ that satisfy $E[X_i^2]=1$ and $E[X_i^4] \leq K^4$. Then show that $$\operatorname{Var}(\| X\|_2) \leq CK^4$$...
1
vote
0answers
117 views

Convergence of Expectation of norm of sub-gaussian random vector

1.We know that if $X=(X_1,...,X_n)$ be a random vector with independent sub-gaussian coordinates $X_i$ that satisfy $EX_i^2=1$, then $$||||X||_2-\sqrt{n}||_{\psi_2}\leq CK^2$$ where $K=max||X_i||_{\...
0
votes
0answers
25 views

Concentration/Tail Bounds for a vector of Poisson r.v.

Let $X$ be $n$-dimensional s.t. $X_j\sim Poiss(\lambda_j)$. The components are independent, but the rates are different. I am interested in bounds for $\Pr(||X-\lambda||\geq y)$, where $\lambda$ is ...
0
votes
0answers
22 views

Estimate CDF Given a Concentration Bound

Let $X_1,...,X_n$ be random variables, such that $0\le X_i \le 1$ for $i=1,...,n$. Let $p=E[X_i]$ and $p<\epsilon<1$, we have a concentration bound $[-\epsilon,\epsilon]$ with confidence $\sigma$...
0
votes
1answer
73 views

Understanding the Definition of Hoeffding Bound

As defined in the text of CMU statistics notes. The Hoeffding's inequality is defined as: $$P(|\bar{X}-\mu|\geq t)\leq 2 \exp\left(\frac{2n^2t^2}{\sum_{i=1}^n{(b_i -a_i)^2}}\right)$$ where $\mu=E[X_i]$...
1
vote
0answers
21 views

Concentration of a quotient between two sample means

How can I obtain a concentration bound (concentration inequality) of a random variable $Z$, which is a ratio of $X$ to $Y$, when both $X$ and $Y$ are the sums of IID random variables $X_1,...,X_{N_1}$ ...
1
vote
0answers
65 views

Concentration of Bernoulli random variables normalized by expectation

Let $X_i \sim \mathrm{Bernoulli}(p_i)$, let $Y_i = X_i / \mathbf{E} X_i$, and let $S_N = \sum_{i=1}^N Y_i$. ($X_i$ are independent.) Clearly we have $\mathbf{E}[S_N] = N$. Hoeffding's inequality ...
2
votes
0answers
50 views

Why isn't a uniform distribution on a bounded set subgaussian?

On High Dimensional Probability, by Vershynin, there is an exercise that asks to prove that the uniform distribution on the $l_1$ ball of radius $n$, $X \sim {Unif} \{x \in \mathbb{R}^n : ||x||_1 <=...
0
votes
0answers
28 views

Concentration inequality for sum of Bernoulli-Chi-Square products

Suppose that $p_i \in (0, 1]$, $g_i \sim N(0, 1)$, and $b_i \sim \mathrm{Ber}(p_i)$ for all $i = 1, \dots, n$. Suppose also that $g_i$ and $b_i$ are independent. Let $X_k = g_k^2 b_k/p_k$ and define ...
1
vote
1answer
16 views

Supremum characterisation of entropy

Why is it true that for $ g: \mathbb{R}^{n} \rightarrow \mathbb{R}_{+} $ and any measure $\mu$ $$ \int_{}^{}g \cdot \log(g) d\mu - \int_{}^{}g d\mu \cdot \log(\int_{}^{}g d\mu) = sup_{f: \int_{}^{}e^{...
1
vote
0answers
24 views

Tail Bound for normal random variable.

I want to show that if $g \ \sim N(0,1)$, for all $t>0$ we have $P(g\geq t)\leq e^{-t^2/2}$. My solution: Let $\lambda>0$. $P(g\geq t)=P(e^{\lambda g}\geq e^{\lambda t})\leq \frac{E[e^{\lambda ...
0
votes
0answers
40 views

Talagrand's concentration inequality without an almost sure bound?

Does Talagrand's Lipschitz concentration inequality (for example, see Theorem 9, here) hold if instead of $|X_i| < K$ almost surely, one has that there is $K$ such that for all $j$, $P(X_j > K + ...
3
votes
0answers
61 views

Tail probability of sum of order statistics of distance from point to a set

Let $P$ be a distribution on a metric space $(\mathcal X, d)$. For a point $x \in \mathcal X$ and a Borel $B \subseteq \mathcal X$, let $d(x,B) := \inf_{y \in B}d(x,y)$ be the distance of $x$ from $B$....
2
votes
3answers
170 views

If $E e^{\theta ^{2} X^{2}} \leq e^{c\theta^2}$ for every $\theta$, then $X$ is almost surely bounded

The original problem states as below: Suppose some random variable $X$ satisfies $\DeclareMathOperator*{\E}{\mathbb{E}} \E e^{\theta ^{2} X^{2}} \leq e^{c\theta^2}$ for some constant $c$ and $\...
1
vote
1answer
46 views

Does Averaging Always Increase Concentration?

Let $X_1,X_2,\ldots$ be i.i.d zero-mean real random variables and $\epsilon>0$. Is there a simple argument that shows $$\mathbb{P}(|X_1 + X_2 + \dots + X_n| > n\epsilon) \geq \mathbb{P}(|X_1 + ...
2
votes
1answer
127 views

Bounding the degree of very sparse random graph

I am confused with how to manipulating with big O notation ,here is a problem from section 2.4(Exercise 2.4.3) high dimensional probability by Roman Vershynin Consider a random graph $G \sim G(n,p)$ ...
1
vote
1answer
73 views

Reference Request: Concentration inequalities/concentration of measure phenomenon

Is there a good source for concentration inequalities? I've seen the standard ones (Bernstein, Hoeffding, Chernoff, etc.), but I'm hoping to get two things: A ton of exercises. (Still haven't really ...
7
votes
1answer
121 views

Convergence of sample mean using CLT

Assume $X_i$s are i.i.d. random variables with mean $\mu$ and variance $\sigma^2$. Prove: $$\lim_{n\to\infty}n^2\mathbb{P}\left(\left|\frac{\sum_{i=1}^{n} X_i}{n}-\mu\right|>n^{-1/4}\right)=0. \...
3
votes
0answers
77 views

Concentration for Second Maximum of Random Variables

Using Hoeffding's inequality we know that for iid bounded random variables \begin{align} \mathbb{P}(|\hat{\mu} -\mu| > \epsilon) \leq 2\exp(-2\epsilon^2n) \end{align} where $\hat{\mu}$ is the ...
1
vote
1answer
73 views

Isoperimetric inequality for non-spherical multivariate Gaussian

Disclaimer: Sorry in advance, if the question is not very reasonable. Recently (like a few days ago...), I've started studying isoperimetric inequalities, and my thoughts on the subject are rather ...
0
votes
1answer
31 views

Probability Whole Sample Below Expectation

Let $X_1,X_2,\ldots,X_n$ be i.i.d real-valued random variables with finite variance $\sigma^2>0$. Can we non-trivially upper bound the probability $$ \mathbb{P}\bigl(\max_{1\leq i\leq n} X_i < \...
1
vote
1answer
56 views

Rate of convergence of the product of two random variable sequences

Given that $$\forall \epsilon_1\ \exists \delta_{\epsilon_1}>0, N_{\epsilon_1}>0,\text{ s.t. } \Pr\{ n^\alpha |X_n| \ge \delta_{\epsilon_1} \}<\epsilon_1\ \forall n>N_{\epsilon_1}$$ $$\...
2
votes
0answers
84 views

A Maximal Version of Empirical Bernstein Inequality

Bernstein inequality is a very powerful concentration inequality, and can obtain a sharper bound than Hoeffding providing the variance is sufficiently small. The following statements exactly show this ...
0
votes
0answers
27 views

Concentration inequalities for covariances in linear dynamical systems

I have a stable linear dynamical system $x_t \in \mathbb{R}^d, 1\leq t \leq T$ such that $$ x_t = A x_{t-1}+N_t, \quad N_t \sim \mathcal{N}(0,I_d), x_0=0. $$ Define $\hat{\Gamma}_t=\frac{1}{n}\sum_i ...
0
votes
0answers
30 views

non-uniform inequality in Borovkov's 1974 paper

In the paper On the rate of convergence for the invariance principle Borovkov states (p 211) If we use the nonuniform estimate $$|F_{\zeta_j/\sqrt{\Delta_j}}(u)-\Phi(u)|\leqq\frac{c}{1+|u|^s}\frac{...
2
votes
1answer
31 views

Concentration property after conditioning on the sum

Let $X_1, \cdots, X_n$ be i.i.d. (positive) random variables with mean $1$ and density $f(x)$ (we can add conditions like sub-gaussian, sub-gamma later). Now I was interested in the following ...
1
vote
0answers
13 views

Lower bound for binomial random variable

I'm looking for a lower bound for binomial random variable $X$~ $B(n,p)$, where $p=(1+\epsilon)/2$ for $\epsilon >0$. I want to bound $Pr(X> n/2)$. I know Suld's inequality, but it is good ...
1
vote
1answer
22 views

Deviation in $\sup$-norm of simple fixed design NW-regression estimator

For some unknown $(H,\alpha)$-Hölder function $f:[0,1]\rightarrow\mathbb{R}$, we observe $$Y_i=f(x_i)+\varepsilon_i,$$ where $x_i=i/n$, $n\in\mathbb{N}$, $i\in\{1,2,\ldots,n\}$, with iid centered ...