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