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.
297
questions
1
vote
1answer
31 views
Corollary of Hoeffding’s Inequality
Question
I am not from a statistics background I came across the following corollary of Hoeffding’s Inequality and couldn't find the derivation or proof for it so that could anyone please share some ...
5
votes
0answers
46 views
Correct measure in concentration inequalities or hypothesis testing
In most discussions of concentration inequalities or calculations of rejection region in hypothesis testing, the measure used is left vague. For example, for independent random variables $X_1, \ldots, ...
0
votes
1answer
18 views
Concentration of empirical measure under Prokhorov distance
For any two probability measures $\mu,\nu$ over $\mathbb{R}^d$, the Prokhorov distance is defined to be
$$d_P(\mu,\nu)=\inf\{\epsilon:\mu(A)\le \nu(A^{\epsilon})+\epsilon\text{ and }\nu(A)\le\mu(A^{\...
0
votes
0answers
17 views
A question regarding “approximate” hypergeometric distribution
We all are aware of Hypergeometric distribution. Let me first briefly discuss what it is.
Suppose we have an urn containing $N$ balls, $M$ of which are red, rest are blue. We draw $n$ balls from the ...
0
votes
0answers
31 views
Inverse of Fenchel conjugate function
Here is one lemma I encounterd in the book "Concentration Inequalities
A Nonasymptotic Theory of Independence
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart".
Lemma 2.4 Let $\psi$ be ...
1
vote
0answers
15 views
Concentration of $\|v\|^2 vv^\top$, where $v$ is a multivariate random vector with covariance matrix $C$
Let $v \in \mathbb R^n$ be a random vector from $N(0,C)$, where $C$ is an a psd matrix of size $n$ such that $\lim_{n \to \infty} \mbox{tr}(C) = s \in [0, \infty)$. Consider the $d \times d$ psd ...
1
vote
1answer
29 views
Concentration / convergence of a gaussian random multivariate polynomial: computing mean and variance
Let $m,d \to \infty$ with $m/d \to \rho \in (0,\infty)$. Let $z_1,\ldots,z_m$ be iid from $N(0,I_d)$ and let $A$ and $B$ be $d \times d$ be deterministic psd matrices. Define the random variable $S \...
1
vote
0answers
18 views
Sum of Squares of Binomial Distributions?
The $\chi^2$ distribution describes the sum of squares of independent normal random variables. Is there an analogous distribution for the discrete case of sum of squares of independent (identical) ...
0
votes
0answers
15 views
Confidence Interval for least squares estimator
I had asked this question in another forum and I hope this would not cause a problem.
There was a paper by Yasin-Abbasi-Yadkori https://arxiv.org/pdf/1102.2670.pdf titled Online Least Squares ...
1
vote
1answer
37 views
Poisson and Normal Tail
For concentration inequalities, there are two types of tail probability,
Normal tail, for example Hoeffding's inequality gives for sum of independent random variables taking values in $[a,b]$, for ...
2
votes
1answer
38 views
Lower bound for expectation of maximum absolute value of standard normal random variables
I am looking for the simplest possible proof to show that for iid $X_i \sim \mathcal{N}(0,1)$, there is a $c > 0$ such that:
$$\mathbb{E}\left( \max_{1 \leq i \leq n} |X_i| \right) \geq c \sqrt{\...
1
vote
0answers
37 views
Tighter large deviation/reverse Chernoff bound
The method of types tells us that for $0/1$ random variables $X_1, \dots, X_n$ with $\text{Pr}[X_i = 1] = p$, for every $\epsilon > 0$, $$\text{Pr}[\sum_{i=1}^n X_i \ge (p + \epsilon) n] \ge \frac{...
1
vote
0answers
37 views
Poincaré Inequality on Gaussian Measures
So I have a working idea on Gaussian-Poincaré Inequality. Namely through the Ornstein-Ullenbeck Generator and Gaussian Integration by parts.
Recently I have stumbled across Sobolev Spaces and have ...
0
votes
0answers
13 views
Extending the Herbst concentration inequality to complex valued Lipschitz functions
I am currently looking at the Herbst concentration inequality, which states that for a probability measure $\mu$ on $(\mathbb{R}^d,\mathcal{B}(\mathbb{R}^d))$ satisfying the Logarithmic Sobolev ...
1
vote
0answers
38 views
Let $X$ be a random variable with a finite mean $\mu$ and $E[|X−\mu|^n] < ∞$. Find $a$ s.t $P(X ≥ \mu + c) ≤ \frac{E[|X − \mu|^n]}{a}$ ($c > 0,n > 0$)
I am trying to apply Markov inequality here.
$P(X ≥ \mu + c) = P(X - \mu ≥ c) ≤ \frac{E[X − \mu]}{c}$,
but I cannot figure out where does $E[|X − \mu|^n$ come from.
Since there is an absolute value, I ...
1
vote
1answer
51 views
Lower bounds on the MGF for a mean zero random variable with variance $\sigma^2$
Let $X$ be mean-zero with variance $\sigma^2$. Is there a lower bound on the MGF for $X$ (or even simpler, $E e^X$) in terms of $\sigma^2$: $E[e^X] \ge f(\sigma^2)$?
What about the general case where ...
1
vote
0answers
30 views
Sum of sub-gaussian random variables whose correlation coefficient is known
1 - If $X$ is $\sigma_1$-subgaussian, $Y$ is $\sigma_2$-subgaussian and their correlation coefficient is $\rho$, then is it true that $X+Y$ is ($\sigma_1+\sigma_2+2\rho \sigma_1 \sigma_2$)-subgaussian?...
1
vote
0answers
24 views
Concentration of sum of median-centred independent variables, $\sum_i (X_i - m_{X_i})$
Sub-Gaussian style concentration inequalities exist for the median, i.e. if $X$ is a random variable, then there exist positive constants $c_1, c_2$ such that
$$ \Pr( |X - m_X | \ge t) \le c_1 e^{-c_2 ...
2
votes
1answer
47 views
Concentration without first moment
The weakest concentration inequality I know of is markov's inequality:
$$\mathbb P (X \geq t) \leq \frac{\mathbb E X}{t}$$
where $X$ is a nonnegative random variable with first moment $\mathbb E X$ ...
1
vote
0answers
17 views
Convergence rate of statistical estimator
Let's say we have a series of coin flips where there is some unknown bias $p$.
How fast does our estimate of the bias converge to $p$?
An approach: concentration of measure
A typical estimate for $p$ ...
1
vote
0answers
51 views
What is a Kolmogorov inequality, and why?
I encountered a problem while reading a classic paper.
The random variable $V \sim exp(1)$, $(v_{(1)},v_{(2)},...,v_{(n)})$ are ordered. The paper said, for any $\epsilon$, based on the Kolmogorov ...
2
votes
1answer
51 views
Bounding rows of random matrices
Consider i.i.d. random variables $\delta_{ij}\sim\text{Ber}(p)$, where $i,j\in[n]$. Assuming that $pn\geq \log(n)$, show that $$\mathbb{E}\max_{i\in[n]}\sum_{j=1}^n(\delta_{ij}-p)^2 \leq Cpn.$$
This ...
0
votes
0answers
9 views
reference/proof request: Covariance concentration bound for randomly sampled positive semi-definite matrices
I saw the following inequality being used in a paper and the given reference was Joel A Tropp et al. An introduction to matrix concentration inequalities. However, I could not find this inequality ...
0
votes
0answers
23 views
For a stationary Gaussian process, how to show $\max_{1 \leq j \leq n} |X_{j}(\omega)| \leq c(\omega)\log(n)$
Let $X_{k}$ be a stationary Gaussian process, I want to prove that for almost every $\omega$, we have that there exists a constant $c(\omega)$ such that
$\max_{1 \leq j \leq n} |X_{j}(\omega)| \leq c(\...
1
vote
1answer
23 views
Upper bound for Explore-then-commit Bandit algorithm
Background: From the blog,
"The explore-then-commit strategy is characterized by a natural number m, which is the number of times each arm will be explored before committing. Thus the algorithm ...
1
vote
0answers
29 views
Concentration Inequality for the Negative Binomial Distribution
I was wondering if there is any well-known concentration inequality for the Negative Binomial distribution with parameters $r$ and $p$. This random variable is defined as the number of independent ...
1
vote
0answers
8 views
Invertibiity of random matrix with correlated entries
Let $X$ be a random $n \times d$ with independent whose distributions have densities (w.r.t Lesbegue) and let $W$ be a random $d \times k$ marix with independent entries whose distributions also have ...
0
votes
2answers
57 views
(Sub-)Gaussian Norm Concentration Inequality
I am looking for a proof of the following: Let $X_1 \dots, X_n $ be i.i.d. $N(\mu, \Sigma)$, then
$$
\mathbb{P} \left ( \|\bar{X}_n-\mu \|_{2} > \sqrt{\frac{\text{Tr}\Sigma}{n}}+\sqrt{\frac{2 \| \...
2
votes
0answers
66 views
Concentration inequality for of sum of iid Geometric random variables taken to some power
I am interested in techniques for showing the concentration of sum of $n$ iid geometric random variables $X_1, X_2, \cdots, X_n$, say with success probability $p = 1/2$, taken to some power $d$. Let $...
0
votes
0answers
17 views
Question about X concentrates to its mean
Suppose for a statistic $X$ of a size-n sample, $E|X-EX|\le f(n)$ for some decreasing function $f(n)$. Can we say $X$ concentrates to its mean at a rate of $f(n)$?
I understand concentration rate is ...
6
votes
1answer
107 views
Concentration of the $\ell_2$ error of the empirical distribution
Let $X$ be a random variable that takes values only in the set $\{1,2, \dots, m\}$ such that $\Pr(X = i) = p_i$ for all $i = 1,2, \dots, m$. Let $S = \{X_1, X_2, \dots, X_n\}$ be a set of $n$ i.i.d. ...
1
vote
0answers
20 views
Non-asymptotic tail bounds for the gap between the largest and the second largest value in iid sample from $N(0,1)$
Let $n$ be a positive integer and consider the probability density $f_n$ on $\mathbb R_+$ given by $f_n(z):=\int J_n(u,u+z)du$, where $J$ is a probability density on $\mathbb R^2$ given by $J_n(u,v):=\...
2
votes
1answer
30 views
Does this property of Radon-Nykodym derivatives exist
Suppose I have $\pi \ll \lambda$ so that
$$
f = \frac{d \pi}{d\lambda}
$$
and $\lambda \ll \eta$ so that
$$
g = \frac{d \lambda}{d \eta}
$$
Can we say that
$$
\frac{d \pi}{d\lambda} \frac{d \lambda}{d\...
0
votes
0answers
24 views
Concentration of Least Squares Estimate
We know that if the unknown model satisfies a linearity assumption i.e.
$y = x^T\theta + \epsilon$, where $\epsilon$ is Gaussian Noise, we have the least squares estimate $\hat{\theta}$, to be a good ...
1
vote
0answers
34 views
Proof check: Using Hanson-Wright inequality to concentrate a quadratic form $y^\top A y$ where both $y$ and $A$ are random but independent
Disclaimer. I don't know if this is the right venue to ask this. I'm working out a bigger proof, in a critical step, I'ved used an argument I'm not quite sure about.
Let $n$ be a large positive ...
0
votes
0answers
21 views
Bounds for extreme singular-values of matrix $c_{ij} := \psi(x_i^\top w_j)$ where $x_1,\ldots,x_n,w_1,\ldots,x_k \sim N(0,(1/d)I_d)$ iid
Let $n,d,k$ be large positive integers such that $\max(n/d,k/d) =: \lambda < 1$. Let $X$ be a random $n \times d$ matrix with entries drawn iid from $N(0,1/d)$ and let $W$ be a $k \times d$ random ...
1
vote
0answers
37 views
Lower-bound on $\mathbb E[\|A^{-1}x\|]$ when $A$ is a positive-definite matrix with eigenvalues in $[a,b]$ and $x=(x_1,\ldots,x_n)$ is iid Rademacher
Let $A$ a positive-definite $n \times n$ matrix with eigenvalues in the interval $[a, b]$ and let $x=(x_1,\ldots,x_n)$ be a random vector with iid components distributed uniformly in $\{\pm 1\}$.
...
3
votes
0answers
31 views
concentration inequality question
Suppose that $g_1,\dots,g_m$ are i.i.d. $N(0,I_n)$ vectors. Let
$$
X = \sum_{i\neq j} (\langle g_i,g_j \rangle^2 - n)
$$
It is known that when $m\to \infty$, $n\to\infty$, $m/n\to 0$,
$$
\frac{1}{2mn}...
1
vote
0answers
38 views
Proof check: Concentration of maximum of a certain empirical process
Let $x_1,\ldots,x_n$ be iid uniformly distributed on the unit-sphere in $\mathbb R^d$ and let $y_1,\ldots,y_n$ be iid uniformly distributed on $\{\pm 1\}$, and independent of the $x_i$'s. Define $Z_n:=...
3
votes
1answer
114 views
MGF bound for non-centered random variables?
So I was trying to prove the following fact: if $|X| \leq 1$ is a random variable with mean $\mu$, then $\mathbb{E} e^{t (X - \mu)} \leq e^{t^2/2}$, for any real $t$.
I can show this in the special ...
1
vote
0answers
18 views
How can a measure concentrate in multiple, distinct subsets simultaneously?
I am currently reading the following lecture notes: http://www-math.mit.edu/~goemans/18409-2006/lec6.pdf. They prove the following:
Lemma 4: Consider a function $f: S_{n-1}\rightarrow\mathbb{R}$ which ...
0
votes
1answer
73 views
Why does a concentration inequality imply equivalence of moments and exponential integrability of the square?
I have the following basic question about a concentration inequality:
Let $X$ be a random variable, denote by $m$ a median and assume that for every $t>0$ one has
$$
P \left( \left| X - m \right| &...
2
votes
1answer
117 views
The sum of mutually singular measures
I have been trying to make an exercise related to mutually singular measures. Namely the following:
Exercise Let $\mu$ be a positive measure and $\nu_1, \nu_2$ be arbitrary measures all defined on ...
0
votes
2answers
70 views
Upper bound for $|\mathbb E[f(X)] - f(0)|$ when $X \sim N(0,\sigma^2)$ and $f:\mathbb R \to \mathbb R$ is piecewise-linear with $\|f'\|_\infty \le 1$.
Let $f:\mathbb R \to \mathbb R$ be a piecewise linear function such that $f(0)=0$ and $\|f'\|_\infty \le 1$ and let $X$ be a Guassian random variable with mean $0$ and variance $\sigma^2$. What is an ...
1
vote
1answer
84 views
One mysterious step in proof of Lemma 3 Devroye 83
Can someone help me with one step of the following proof of a multinomial concentration inequality taken from Lemma 3 of "The equivalence of weak, strong and complete convergence in l1 for kernel ...
0
votes
1answer
43 views
tail bound of the deviation from sum of functions of random variables to its expectation value
I am struggling at an error propagation recently and I do not know what tools can be used in this problem. Explicitly my problem can be represented as following:
I have expression
$$\varepsilon=\frac{...
0
votes
0answers
101 views
Levy's measure concentration lemma generalized for a product measure?
I am looking for a product measure concentration inequality on n-sphere. I think is is a generalization of the Levy's lemma.
In my understanding, the lemma by Levy ensure that the measure ...
2
votes
1answer
177 views
Absolute value of sub-gaussian
Let $\eta_1 , \eta_2, \cdots, \eta_t$ be 1-subgaussian independent random variables with mean 0(but not necessarily identical).
Now we know several nice equations about $|\sum_{s=1}^t \eta_s|$.
How ...
2
votes
2answers
87 views
Good concentration inequality for $\max_{i,j} X_j- X_i$ where $X_1,\ldots,X_n \overset{iid}{\sim} N(0,1)$.
Let $n$ be a large positive integer and define $\Delta:\mathbb R^n \to \mathbb R$ by $\Delta(x) := \max_{i,j} x_j - x_i$. Let $X_1,\ldots,X_n$ be iid from $N(0,1)$
Question. What is a good ...
2
votes
1answer
483 views
Concentration of coordinatewise Lipschitz function
Let $f:\mathbb R^n \to \mathbb R$ be coordinatewise $1$-Lipschitz, i.e $|f(x')-f(x)| \le |x'_k-x_k|$ whenever $x=(x_1,\ldots,x_n)$ and $x' = (x'_1,\ldots,x_n')$ are two vectors in $\mathbb R^n$ which ...
