Stack Exchange Network

Stack Exchange network consists of 174 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.

0
votes
0answers
14 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
16 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\in\mathbb{R}$. Define $a_0:= \lim_{\delta\...
1
vote
1answer
52 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
18 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
25 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
45 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
16 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
39 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$. ...
1
vote
0answers
29 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
16 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
0answers
84 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$$...
0
votes
0answers
17 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
22 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
20 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
27 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
12 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
38 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 ...
1
vote
0answers
26 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
17 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
15 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
19 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
27 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
58 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
160 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
45 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 + ...
1
vote
1answer
60 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)$ ...
0
votes
1answer
43 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
102 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
69 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
64 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
30 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
47 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
60 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
25 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
29 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
29 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
17 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 ...
1
vote
0answers
27 views

The Equivalence of Brunn-Minkowski Inequalities

I am trying to make a proof on Brunn-Minkowski inequalities. Specifically, I am trying to prove that given two convex bodies C and D in $\mathbb{R}^n$, then the Brunn-Minkowski inequality $Vol[(\...
1
vote
1answer
41 views

Concentration inequalities for logit-normal variables

I have a random variable $f(x) = \frac{1}{1 + e^{-x}}$ which is a logistic transformation of a Gaussian random variable $x \sim \mathcal{N}(\mu, \sigma^2)$. I want to bound $|f(x) - f(\mu)|$. Are ...
0
votes
0answers
142 views

Constant concentration for chi square variables

I would like to have a certain concentration inequality for chi square variables with $k$ degrees of freedom. As referenced in https://stats.stackexchange.com/questions/4816/what-are-the-sharpest-...
3
votes
0answers
75 views

An alternative to Doob's maximal inequality?

I have a discrete process $X_t,~t\in \mathbb N$ for which I have shown that $$\mathbb E[X_t|\mathcal F_{t-1}] \geq \alpha X_{t-1}^2$$ for some positive constant $\alpha \in (0,0.5)$. Also, $X_t$'s ...
1
vote
0answers
110 views

Study of super-Gaussian or super-Exponential distributions?

the terms may be weird, but they just mean distributions with heavier tail with Gaussian/exponential respectively, in a way that is exactly the opposite of sub-Gaussian and sub-exponential. There's ...
0
votes
1answer
75 views

Sub-gaussianity of product of a bounded random variable and sub-gaussian random variable

Let $Z \sim \mathcal{N}(0,1)$ be a $1$-dimensional standard Gaussian random variable. Let $f(z)=\frac{1}{1+e^{-z}}$ be the logistic sigmoid function. For some $\alpha>0$, I want to show that the ...
1
vote
1answer
95 views

Upper bound on the average of independent Rademacher random variables

Given a sequence of Rademacher random variables $\{X_k\}_{k\geq1}$. The definition of Rademacher random variables can be found in Inequality with Rademacher variables. I was wondering how to prove ...
0
votes
0answers
31 views

measure concentration on sphere (reversed)

I am interested in a (sort of) reverse measure concentration for the sphere. I have learnt that for a set $A \in \mathbb{S}^{n-1}$ with uniform measure $\nu(A) \geq 1/2$, the epsilon neighbourhood $A_{...
1
vote
0answers
70 views

Hoeffding's inequality for dependent random variable

Let $X_1,X_2\in \{-1,+1\}^2$ be dependent random variables with fixed moments $\mathbb{E}[X_1 X_2],\mathbb{E}[X_1],\mathbb{E}[ X_2]\in [-1,+1]$. Given $n$ iid samples we can estimate $\mathbb{E}[X_1],\...
1
vote
0answers
56 views

Books about exponential tilting

Please recommend books about the expoential tilting. My main insterest is about its application on concentration inequalities. Søren Asmussen's Stochastic Simulation: Algorithms and Analysis have ...
1
vote
1answer
82 views

Concentration inequalities on the supremum of average

Let $R_1, R_2, \cdots$ be i.i.d. Rademacher random variables (taking values $-1,+1$ w.p. $0.5$). At time $k$, their average is $\frac{1}{k}\sum_{i=1}^k R_i$. One can imagine after $k\geq n$ for some $...
0
votes
1answer
58 views

To establish an inequality using Chebyshev's probability bound

Let $X$ be a random variable with mean, $E(X)=\mu$ and variance, $E(X-\mu)^2=\sigma^2$. Then Chebyshev's inequality asserts that $$ P\{|X-\mu|\geq k\sigma\} \leq \frac{1}{k^2} $$ Using this ...