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 ...
