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.

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5 6