# Questions tagged [measure-concentration]

The measure-concentration tag has no usage guidance.

381
questions

-1
votes

0
answers

44
views

### Super-exponential concentration for $\frac{\sum_{i = 1}^{n} X_i}{\sum_{i = 1}^{n} X_i^2}$ with $X_i$ iid. Poisson

Consider $n$ independent Poisson(1)-distributed random variables $(X_i)_{1 \leq i \leq n}$.
Is it true, that $$P\left(\frac{\sum_{i = 1}^{n} X_i}{\sum_{i = 1}^{n} X_i^2} \leq \epsilon \right) \leq \...

2
votes

0
answers

84
views

### Concentration inequalities for functions of random binary strings

Let $(X_1,\ldots,X_n)$ be a vector in $\{0,1\}^n$ drawn uniformly at random among all vectors with exactly $k$ $1'$s. I am interested in inequalities for tail probabilities for the random variables $X,...

3
votes

1
answer

119
views

### Concentration of measure on spheres with respect to a unitary of trace approximately zero

Cross-posted from MSE, where it hasn’t received any answer yet:
This question arose out of my attempt to understand how a unitary of trace approximately zero acts on the unit sphere of a $n$-...

2
votes

0
answers

49
views

### Concentration result for self-normalized empirical process

In Theorem 1.1 of this paper by Bercu, Gassiat and Rio, a concentration result is derived for the 'self-normalized' empirical process. Specifically, suppose that $(X,X_n)_{n \ge 1}$ is a sequence of i....

1
vote

2
answers

157
views

### Inner product of the spherical cap and Gaussian

Let $d\in \mathbb{N}$ and $\eta \sim N(0,I_d)$ where $N(0,I_d)$ is the gaussian distribution with the covariance matrix of $I_d$. Also, define a spherical cap as follows. Fix $v \in \mathbb{S}^{(d-1)}$...

0
votes

0
answers

46
views

### Concentration inequalities for leave-one-out sum

Let $X_1,...,X_n$ be iid random variables. Consider $f:\mathbb{R}\times\mathbb{R}^{n-1}\to\mathbb{R}$ such that $f$ is symmetric in the last $n-1$ variables. Our goal is to show that $\sum_{i=1}^n f(...

1
vote

1
answer

55
views

### How does Chernoff-Hoeffding bound with limited independence reduce to the usual generic CH bound with complete independence

As the title might suggest, I am referring to this paper https://www.cs.umd.edu/~srin/PDF/ch-bounds.pdf , titled : Chernoff-Hoeffding Bounds for Application with Limited Independence.
The theorem in ...

0
votes

0
answers

73
views

### Concentration bounds for sum of weighted sampling without replacement

Let $X$ be a collection of $2l$ non-negative numbers $X_1,X_2,\ldots,X_{2l}$. We draw $l$ weighted (proportional to values) samples without replacement from $X$. Let $S$ denote this set of $l$ samples....

0
votes

0
answers

50
views

### Tight Chernoff Concentration for Bernoulli(p) RV

I remember seeing a research paper on tight concentration of Bernoulli(p) random variable in terms of $p$.
What I mean is that they used a stronger upper bound for the MGF than $E[e^{s(X-p)
}]\leq e^{...

0
votes

1
answer

180
views

### Concentration inequalities for random sampling without replacement

Let a population $C$ consist of $N$ values $c_1, c_2, \cdots, c_N$, with $c_i\in \{0,1\}$. Let $X_1, X_2, \cdots, X_n$ denote a random sample without replacement from $C$ and let $Y_1, Y_2, \cdots, ...

2
votes

1
answer

156
views

### Small deviations of real log-concave random variable

I am working with a log-concave real random variable, that has a density $f(x) = \exp(-\varphi(x))$ with $\varphi$ convex. Assuming that $X$ is centered and has unit variance ($\mathbb{E}X=0$, $\...

4
votes

1
answer

182
views

### Sign of error in the central limit theorem

Let $X_n$ and $Y_n$ be independent copies of two random variables $X$ and $Y$ with domain $\{-1,0,1\}$ for $n\in \mathbb{N}$. For a given $k\in \mathbb{N}$, I would like to find conditions on $X$ and $...

17
votes

0
answers

387
views

### Talagrand's "Creating convexity" conjecture

We say a subset $A$ of $\mathbb{R}^N$ is balanced if
\begin{equation}
x \in A, \lambda \in [-1,1] \implies \lambda x \in A.
\end{equation}
Given a subset $A$ of $\mathbb{R}^N$, we write
\begin{...

2
votes

1
answer

135
views

### A concentration inequality related to suprema of sub-Gaussian processes

Let $x_1,\dots,x_n$ be deterministic points in some space $X$ and consider a class of real-valued functions $\mathcal G$ on $X$. We further assume that for any $g \in \mathcal G$,
$$
\Bigl(\frac1n \...

0
votes

2
answers

213
views

### Bounds tighter than the additive Chernoff

Additive Chernoff
Suppose $X_1, \ldots, X_n$ are i.i.d. random variables, taking values in $\{0,1\}$. Let $p=\mathrm{E}\left[X_i\right]$ and $\varepsilon>0$.
\begin{gather*}
\operatorname{Pr}\left(\...

1
vote

0
answers

55
views

### Limiting value of expectation of trace of truncated Gram matrix

Let $n$ and $d$ be large positive integers such that $d/n = a \in (0,1)$, fixed. Let $x_1,\ldots,x_n$ be iid random vectors from $N(0,I_d)$. Fix $b \in (0,1]$ and a unit-vector $v \in \mathbb R^d$, ...

2
votes

0
answers

62
views

### A lemma in the application of Lions's concentration compactness pricnciple in Hardy-Littlewood-Sobolev inequality

I'm encountering some problems when reading Lions' paper "the concentration-compactness principle in the calculus of variations. The limit case, Part 2".
The Hardy-Littlewood-Sobolev (HLS) ...

1
vote

2
answers

202
views

### Beating the $1/\sqrt n$ rate of uniform-convergence over a linear function class

Let $P$ be a probability distribution on $\mathbb R^d \times \mathbb R$, and let $(x_1,y_1), \ldots, (x_n,y_n)$ be an iid sample of size $n$ from $P$. Fix $\epsilon,t\gt 0$. For any unit-vector $w \in ...

3
votes

1
answer

236
views

### Sub-Gaussian random variables and convex ordering

Suppose that $X$ is a $1$-sub-Gaussian real-valued random variable, i.e. for all $t \in \mathbf{R}$, it holds that $\log \mathbf{E} \exp \left( t X \right) \leqslant \frac{1}{2} t^2 $.
Does there ...

2
votes

1
answer

115
views

### Simplified upper bounds for moment-generating function of symmetrised random variable

Let $X$ be a nonnegative random variable such that $\mathbf{E} \left[ \exp X \right] < \infty$. For $\theta \leqslant 1$, an appropriate application of Jensen's inequality, yields that
\begin{align}...

1
vote

1
answer

114
views

### Lipschitz-type inequalities for Markov kernels

Let $K(\cdot\mid\cdot)$ be a Markov kernel. For a measure probability $\mu$, denote by $\mu K$ the probability measure induced by $K$ and $\mu$, i.e. $(\mu K)(A):=\int_\Omega \mu(d\omega)K(A\mid\omega)...

1
vote

1
answer

164
views

### Concentration inequality for square roots

Given a sequence of (not-necessarily-iid) real-valued random variables $X_n$ that converge to $a\in\mathbb{R}$ in probability, suppose we have an exponential concentration inequality of the form
$$
P(|...

1
vote

0
answers

127
views

### Large-deviation inequalities for a class of simple random multivariate polynomials

Let $N$ be a large positive integer and let $[N] := \{1,2,\ldots,N\}$. For any $k$, let $K_{N,k}$ denote the collection of $k$-element subsets of $[N]$. Let $x=(x_1,\ldots,x_N)$ be a uniformly random ...

1
vote

1
answer

81
views

### Asymptotic scaling of mean and variance for the norm of random vector (non gaussian components)

The norm of a vector whoose components $X_i$ are normally distributed follows the Non-central chi distribution and it can be shown that, increasing the number of components $k$ (i.e. the dimension of ...

2
votes

2
answers

211
views

### Asymptotic scaling of mean and variance for non-central chi distribution

Define $Y \equiv \sqrt{\sum_{i=1}^k(\frac{ X_i}{\sigma_i})^2}$, with $X_i \sim \mathcal{N}(\mu_i, \sigma_i^2)$ and independents.
It is known that $Y$ is distributed as a non-central chi (Noncentral ...

1
vote

1
answer

210
views

### Rate of convergence to uniform distribution

Let $p=(p(1),\ldots,p(N))$ be a discrete distribution on $[N]:=\{1,2,\ldots,N\}$ with full support (i.e all the $p(i)$'s are strictly positive and sum to $1$). Let $i_1,i_2,\ldots,i_T$ be an iid ...

1
vote

0
answers

78
views

### Composing an Orlicz norm related to Bernstein's inequality?

This is related to my previous question, but is hopefully more precise.
I would like to reason about tail-bounds for polynomial products of concentrated random variables in $R:=\mathbb{R}[x]/(x^n-1)$.
...

0
votes

1
answer

86
views

### Is the product of sub-Gaussian polynomials in $\mathbb{R}[x]/(x^n-1)$ sub-Gaussian?

Let $\psi_\alpha(x) := \exp(x^\alpha)-1$.
It is well-known that for $\alpha\geq 1$ that
$$\lVert X\rVert_{\psi_\alpha} = \inf\{k>0\mid \mathbb{E}[\psi_\alpha(|X|/k)] \leq 1\}$$
defines an Orlicz ...

1
vote

1
answer

290
views

### Optimal transport between two matrices

I'm investigating the use of optimal transport to define a distance between non-negative matrices that satisfy the condition $\mathbf e^\top\mathbf M\mathbf e = 1$ (i.e., the sum of all elements in ...

3
votes

0
answers

56
views

### Concentration for Hamming balls

It is well known that Lipschitz functions on the Boolean $n$-cube endowed with the Hamming metric satisfy concentration properties. Specifically, most of their values lie in a range of width $O(\sqrt ...

5
votes

1
answer

389
views

### Lower tail of random rank one sums?

Let $\{x_i\}_{i\geq 1}$ be iid random elements of the sequence space $\ell^2(\mathbb{N})$;
assume that $\|x_i\|_2 \leq 1$ almost surely. Let $\Sigma = \mathbb{E}[x_1 \otimes x_1]$.
Define
$$
\Sigma_n =...

1
vote

1
answer

146
views

### Anti-concentration inequality for the eigenvalue of Gaussian matrix

Let $f(x) = f(x_1, . . . , x_n)$ be a polynomial of degree $d$ and $\text{Var}[f] = 1$. One result by Carbery and Wright shows that for any $t\in\mathbb{R}$ and $ε > 0$,
$$
\text{Pr}_{x\sim N^n}[|f(...

0
votes

1
answer

130
views

### Deducing norm concentration from MGF bounds

Suppose that $X$ is a centered, $\mathbf{R}^d$-valued random variable such that for all $t \in \mathbf{R}^d$, there holds the bound $$\log \mathbf{E} \left[ \exp \langle t, X \rangle \right] \leqslant ...

1
vote

1
answer

186
views

### matrix bernstein's inequality: from tail probability to expectation

Let $X_i$ be independent, mean zero, $n\times n$, symmetric random matrices. $\|X_i\|\leq K$ almost sure for $\forall I$.
We have matrix Bernstein's inequality for the tail probability as follows
$$\...

0
votes

1
answer

101
views

### Positivity of linear combination of gaussian variables

Consider a collection of independent standard Gaussian variables $w_i$ for $i = 1, 2, \ldots, N$. Define its linear combination $f:=\sum_{i=1}^Na_iw_i+b_i$, where $a_i=pb_i$ ($p$ is a fixed parameter),...

1
vote

2
answers

218
views

### Anti-concentration of gaussian variable

Let $X$ be $\mathcal{N}(\mu,\sigma^2)$ gaussian. Its expectation $\mu$ is positive. Can we derive a lower bound on
$$\mathbb{P}(X\geq\epsilon)\geq g(\epsilon,\mu,\sigma) \text{ where } \epsilon\leq\mu$...

1
vote

1
answer

187
views

### $L_1$ norm concentration of an empirical distribution

Suppose we have one random variable $X$, whose sample space is $\mathbb{X}=\{x_1,x_2,\dots,x_m\}$, and the size of the sample space is $m$. We have $N$ i.i.d. samples from this distribution, and $x_i$ ...

0
votes

0
answers

150
views

### Anti-concentration for Bernoulli summation

Suppose $\{ Y_i\}_{i = 1}^n$ is i.i.d. Bernoulli distribution with mean $p$. Denote the sample of $\{ Y_i\}_{i = 1}^n$ as $\overline{Y} = \frac{1}{n} \sum_{i = 1}^n Y_i$. I want to know where there ...

1
vote

1
answer

168
views

### concentration of random field to its expectation function

Question
Given a random field $X(t)$ where the parameter space $T\subset\mathbb{R}_N$. Is there result regarding the concentration of the random field? For example
$\mathbb{P}\{\|X(t)-\mathbb{E}\{X(t)\...

0
votes

0
answers

35
views

### concentration inequality with matrix coefficient

Let $(X_i)_{i=1}^N$ be mean zero sub-Gaussian random vectors in $\mathbb{R}^n$, i.e., there exists $C>0$ such that for all $u\in \mathbb{R}^n$,
$$
\mathbb{E}\left[e^{u^\top X_i}\right]\le e^{\frac{...

2
votes

0
answers

107
views

### Large deviation principle for product of iid bounded symmetric random variables

Let $n$ and $k$ be positive integers. Let $X$ be the empirical mean of $n$ iid Rademacher random variables. Note that the distribution of $X$ is symmetric about 0, and also $|X| \le 1$ w.p 1. Let $X_1,...

1
vote

1
answer

190
views

### Concentration of a certain simple / well-structured random multilinear polynomial with growing degree

Let $k$ and $N_1$ be positive integers and set $N=kN_1$. Partition $[N] := \{1,2,\ldots,N\}$ $k$ disjoint from $G_1,\ldots,G_k$ of each of size $N_1$, and let $\mathcal T(k,N_1)$ be a transversal of ...

2
votes

1
answer

305
views

### Converse of the Herbst argument?

Background
For a real-valued random variable $X$, define its entropy by $H(X) = E[\phi(X)] - \phi(E[X])$, where $\phi(u) = u \log u$.
It can be shown that, if the entropy satisfies the bound
$$
H(e^{\...

2
votes

1
answer

249
views

### The lower bound of bivariate normal distribution

Suppose $(Z_1, Z_2)$ is the zero-mean bivariate normal distribution with covariance $\left( \begin{matrix} 1 & \rho; \\ \rho & 1\end{matrix} \right)$ with positive $\rho > 0$. What I want ...

4
votes

2
answers

243
views

### Concentration of minimum Hamming distance between $N$ points sampled iid from uniform distribution on $n$-dim hypercube $\{0,1\}^n$

Let $n$ be a large positive integer. Sample $N \ge 2$ points $x_1,\ldots,x_N$ iid from the uniform distribution on the $n$-dimensional hypercube $\{0,1\}^n$. Define the gap $\delta_{N,n} := \min_{i \...

1
vote

0
answers

126
views

### Concentration of a combinatorial sum

Let $X=(x_1,\ldots,x_p)$ be an $p \times n$ random matrix with iid entries from $\{\pm 1\}$, distributed so that $\mathbb P(x_{ij} = 1) \equiv 1/2$, where $x_i=(x_{i1},\ldots,x_{in})$. Let $y$ be a ...

4
votes

2
answers

330
views

### Rate of convergence of sample maximum, $\Big|\max_{j \leq n} |f(U_j)| - \|f\|_\infty\Big|$

Suppose that $f \colon [0, 1] \to \mathbb{R}$ is a $1$-Lipschitz function.
Define the uniform norm $\|f\|_\infty = \sup_{x} |f(x)|$.
Given $\{U_j\}_{j=1}^\infty$ independent and identically ...

6
votes

1
answer

714
views

### Simple proof of sharp constant in DKW inequality

The DKW inequality says that if $F_n$ is the empirical CDF corresponding to real-valued random variables $X_1, \dots, X_n$ distributed identically and independently from a distribution with CDF $F$, ...

1
vote

1
answer

166
views

### Hypothesis to guarantee Lindeberg's condition

Imagine to have a set of random variables $\{ X_i \}_{i=1}^{n}$ independent (Non identically distributed). In these scenario, if the Lindeberg's condition hold we can extend the result of the CLT, i.e....

8
votes

1
answer

510
views

### Concentration bounds for martingales with adaptive Gaussian steps

Consider the following martingale: $X_1 \sim \mathcal{N}(0, 1)$, and for any $n > 1$, $X_n \sim \mathcal{N}(X_{n-1}, X_{n-1}^2)$ (notice, this is a conditional distribution given $X_{n-1}$).
I am ...