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
8 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
17 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
18 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
17 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
10 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
30 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 ...
0
votes
0answers
16 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
13 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 ...
0
votes
1answer
13 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
17 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
18 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
56 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
145 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
44 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
51 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
0answers
27 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
95 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
66 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
57 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
46 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}$$ $$\...
1
vote
0answers
45 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
28 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
16 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
24 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
37 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
106 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
73 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
89 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
68 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
77 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
19 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
44 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
50 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
72 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
47 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 ...
0
votes
1answer
27 views

A problem of proving that a certain concentration inequality cannot be improved

Consider the following concentration inequality. The problem is : The inequalities are easily proven with the help of Markov's inequality. But I cannot find a strategy to construct an example to ...
1
vote
0answers
50 views

Concentration inequalities for supremum of moving average

I am looking for a concentration inequality for supremum of a moving average. I think that a situation I assume below occurs naturally, and there exists a concentration inequality for that. However, I ...
1
vote
1answer
43 views

On the 1/2 assumption on concentration of measure on continuous cube

The concentration of measure on $ [0, 1]^n $ equiped with normalized uniform measure $\mu_{\infty}$, states for any $A \subset [0, 1]^n $ with $ \mu_{\infty}(A) \geq \frac{1}{2} $, we have: $$ 1 - \...
4
votes
1answer
98 views

A simple proof of McDiarmid's inequality?

$\newcommand{\Ex}{\mathrm{E}} \newcommand{\Pr}{\mathrm{Pr}} \newcommand{\Ind}{\mathbf{1}} \newcommand{\implies}{\Rightarrow}$ Let $f(x_1, \ldots, x_n)$ be a real valued function of $n$ variables, with ...
1
vote
0answers
238 views

Concentration of the norm (sub-gaussianity)

I'm trying to solve the following problem (exercise 3.1.4 of these notes) Suppose $X = (X_1, \dots, X_n) \in \mathbf{R}^n$ is a random vector with independent, sub-gaussian coordinates $X_i$, each ...
1
vote
0answers
42 views

Improved Bennet Inequality for Vector-Valued RV

I have come across this equation (Lemma 1) in this paper: $$P\left(\left\lVert \frac{1}{m}\sum_{i=1}^{m}(Z_i-E[Z_i])\right\rVert>\epsilon\right) = 2 \exp\left(-\frac{m\epsilon}{2M}\log\left(1+\...
0
votes
0answers
118 views

Proof of Hoeffding's inequality for sum of bounded random variables

Prove $P(\sum_{i=1}^N(X_i-E X_i)\ge t)\le e^{-\frac{2t^2}{\sum_{i=1}^N(M_i-m_i)^2}}$. \begin{align*}P(\sum_{i=1}^N(X_i-E X_i)\ge t)&=P(e^{\lambda\sum_{i=1}^NX_i}\ge e^{\lambda(t+\sum_{i=1}^NE X_i)}...
3
votes
1answer
87 views

Concentration inequality for i.i.d. negative multinomial variables

Let $\mathbf p=(p_0,p_1,\cdots,p_m)$ be a probability vector, such that $p_0+p_1+\cdots+p_m=1$. Let $X_1,X_2,\cdots$ be i.i.d. random variables distributed according to the categorical distribution ...
2
votes
0answers
53 views

Concentration inequity with Random Gaussian Matrix

The rows of $X_{n\times p}$ are $\it{i.i.d}\:\:\: p$ variate Gaussian vectors with distribution $\mathcal{N}_p(0,\Omega)$. Let $\varepsilon$ be another $n$-variate normal random variable independent ...
1
vote
0answers
59 views

McDiarmid's Inequality for random vectors

Let $\boldsymbol{X}\in\mathbb{R}^d$ be a random vector and $\boldsymbol{X}^{(1)},\boldsymbol{X}^{(2)},...,\boldsymbol{X}^{(n)}$ are $n$ independent observations. Also $f: \mathbb{R}^{d\times n} \...
1
vote
0answers
86 views

Johnson Lindenstrauss Lemma proof

Just trying to understand the text below. Question 1: What exactly is the argument below (1)? "This is enough because applying (1) to $v=x-y$ for $x,y\in\mathbb{R}^n$, we get $f(x,y)=f(x)-f(y)$, and ...