# Questions tagged [measure-concentration]

The measure-concentration tag has no usage guidance.

**4**

votes

**1**answer

105 views

### Is there a counterexample to the Thin Shell Conjecture for sub-exponential distributions?

The thin shell conjecture states that there exist universal constants $C,c>0$ such that every logconcave isotropic random vector $X$ in every Euclidean space $\mathbb{R}^n$ satisfies
$$\mathbb{P}\...

**0**

votes

**1**answer

43 views

### Anti-concentration: upper bound for $P(\sup_{a \in \mathbb S_{n-1}}\sum_{i=1}^na_i^2Z_i^2 \ge \epsilon)$

Let $\mathbb S_{n-1}$ be the unit sphere in $\mathbb R^n$ and $z_1,\ldots,z_n$ be a i.i.d sample from $\mathcal N(0, 1)$.
Question
Given $\epsilon > 0$ (may be assumed to be very small), what is ...

**0**

votes

**0**answers

19 views

### Anti concentration of $\frac{1}{n}zz^T + \text{diag}(z_1^2,\ldots,z_n^2)$ for sub-gaussian i.i.d $z_1,\ldots,z_n$ and $z:=(z_1,\ldots,z_n)$

Let $z_1,\ldots,z_n$ be an i.i.d sample from a sub-gaussian distribution. Define the $n$-by-$n$ p.s.d matrix $C_n := \frac{1}{n}zz^T + \text{diag}(z_1^2,\ldots,z_n^2)$, where $z:=(z_1,\ldots,z_n)$.
...

**0**

votes

**0**answers

17 views

### Concentration of $X^T\eta\eta^TX \in \mathbb R^d$ for i.i.d $(x_i,\eta_i)$ and sub-gaussian $\eta_i$

Suppose $(x_1,\eta_1),\ldots,(x_n,\eta_n)$ are $n$ i.i.d points in $\mathbb R^{d+1}$ such that $\eta_1,\ldots,\eta_n$ are $\sigma$-subgaussian. Let $X \in \mathbb R^{n \times d}$ be the vertical ...

**0**

votes

**0**answers

39 views

### The problems of global asymptotic freeness

Let $X_{N}\in\mathcal{M}_{N}\big(L^{\infty-}(\Omega,\mathbb{P})\big)$ be a $N\times N$ random complex matrix such its entries $(x_{ij}, 1\leq i, j\leq N)$ be $i.i.d.$, centred with variance $1$. $X_{...

**1**

vote

**1**answer

64 views

### Sharp tail bounds for the maximum of an iid sample of a random variable supported on $[0, 1]$

Let $X_1,\ldots,X_n$ be an iid sample from a distribution supported on $[0, 1]$.
Question
What are some sharp concentration inequalities (i.e tail bounds) empirical statistic defined by $Z_n := \max(...

**1**

vote

**0**answers

51 views

### Almost orthogonality of independent random vectors [closed]

If $X_1$ and $X_2$ are two independent isotropic random vectors in $\mathbb{R}^n$,
then $\mathbb{E}\|X_i\|_{2}^{2}=n$, $\mathbb{E}\langle X_1,X_2\rangle^{2}=n$.
How can I show from the above result ...

**0**

votes

**0**answers

16 views

### Non-asymptotic tail-bounds for Hotelling $T^2$ statistic

Let $X_1,\ldots,X_n$ be an i.i.d sample from a distribution on $\mathbb R^p$ with mean $\mu = 0 \in \mathbb R^p$ and $p$-by-$p$ covariance matrix $\Sigma$ of rank $r \le p$. Consider the centered ...

**3**

votes

**1**answer

82 views

### Non-asymptotic tail bounds for $D_{\text{Hellinger}}(P\|\hat{P}_N)$

Let P be a distribution on a finite set of size $k$ and let $\hat{P}_N=(N_1/N,\ldots,N_k/N)$ be the empirical distribution (frequencies) from a samples of size $N$. Consider the Hellinger distance ...

**2**

votes

**1**answer

52 views

### Generalization of Komlós–Major–Tusnády Approximation

The Komlós–Major–Tusnády Approximation (see Wikipedia) considers the sum of uniform variables in $(0,1)$. There are also version where instead the sum of equiprobable $0/1$ variables is used ($p=1/2$)....

**0**

votes

**2**answers

109 views

### Distribution of the individual coordinates of a uniform random vector on a high-dimensional sphere

Let $X=(X_1,\ldots,X_n)$ be a random vector uniformly distributed on the $n$-dimensional sphere of radius $R > 0$. Intuitively, i think that for large $p$ every coordinate $X_i$ is normally ...

**9**

votes

**1**answer

278 views

### Maximal inequality for the average of i.i.d. random variables

Let $Z_i$ be i.i.d. random variables with $\mathbb{E}[Z_i] = 0$ and $\mathbb{E}|Z_i|^p< \infty$ for $p=1,2,3,\cdots$. I am looking for the following type of estimate if possible, and it is not like ...

**2**

votes

**0**answers

47 views

### General SLLN-like asymptotic mean concentration

Disclaimer: As I am not very knowledgeable of the field to which this question pertains, I will introduce a temporary terminology to convey the idea of my question at the risk of conflicting with ...

**3**

votes

**0**answers

107 views

### Asymptotic behavior of row sums in 2-d array of random variables

Set-up. Let $f : \mathbb{N} \to \mathbb{N}$ be increasing. For each $m \in [0,1]$, consider an infinite two-dimensional array of random variables, where row $n$ has $f(n)$ variables:
$B^m_{1,1}$ $B^...

**3**

votes

**1**answer

117 views

### Tail probability of random projection

Suppose $v\in R^n$ is a constant unit vector. $P_l$ is a random projection matrix to an $l$ dimensional subspace of $R^n$ which is uniformly sampled from $G(l,R^n)$ which is the collection of all $l$-...

**0**

votes

**1**answer

115 views

### Does log-concave approximable distribution satisfy transportation-cost inequality?

Definition: Recall that a distribution $\mu$ on $\mathbb R^d$ is said to be log-convave with constant $c > 0$, if density $d\nu \propto e^{-V}dvol$ satisfying the curvature condition
$$
\...

**6**

votes

**1**answer

119 views

### Transportation-cost inequality for pushforward measure

Let $X=(X,d_X)$ and $Y=(X,d_Y)$ be metric spaces and $\varphi: X\rightarrow Y$ be an $L$-Lipschitz map, with $0 \le L < \infty$. Suppose $\mu$ is a probability measure on $X$ which satisfies ...

**1**

vote

**1**answer

82 views

### What is the order of the left tail of a mixture of non-central chi-square?

Let $\mu\sim N(0,1)$, $Z\sim N(\mu,1)$. Then $Z$ can be viewed as a mixture of Gaussians. It can also be viewed as a Gaussian but there is a prior for the mean.
Let $X\sim\exp(\lambda)$ where the ...

**4**

votes

**1**answer

134 views

### General distributions with the “transportation-cost inequality” property to piece log-concave distributions

It is now known [Otto et Villani 2000; Cordero et al 2006; etc.] that on an $n$-dimensional smooth Riemannian manifold $X$ and a probability measure $\mu$ on $X$ with density $d\mu \propto e^{-V}dvol$ ...

**1**

vote

**0**answers

62 views

### Upper bound for $\sup_{W_d(Q, P) \le \epsilon} Q(A)$, where $W_d$ is the Wasserstein metric

Let $X=(X,d)$ be a metric space and let $W_d$ denote the Wasserstein metric induced by this metric, on the space of probability distributions on $X$. Let $\epsilon \ge 0$, $A$ be a Borel subset of $X$...

**2**

votes

**0**answers

75 views

### Matrix Chernoff sampling with out replacement

I am interested to know if the matrix Chernoff bound (see Theorem 5.1.1 in https://arxiv.org/pdf/1501.01571.pdf) holds if one samples without replacement.
For example, the Bernstein inequality is ...

**0**

votes

**0**answers

32 views

### General conditions for Gaussian isoperimetric inequaliteis

Context
I'm doing some work in which i need to show that the blow-up $B_\epsilon$ of a Borel set $B$ has large measure for $\epsilon$ sufficiently large. I've found a very attractive tool for doing ...

**0**

votes

**0**answers

33 views

### Probability One Binomial is Greater than Another Dependent One

Let $\mathbf{n}\sim\text{Multinomial}(n,(p,q,r))\in\mathbb{N}^{3}$ where $p<q$. Can we find an upper bound for
$$
\mathbb{P}(\mathbf{n}_1 > \mathbf{n}_2)
$$
of order $e^{-C n}$ (with explicit ...

**1**

vote

**0**answers

139 views

### Matrix Bernstein for spherical random variables

Theorem 4.1 in Tropp's Matrix Concentration Inequalities provides an exponential concentration inequality for the spectral norm of a matrix $Z = \sum_i \gamma_i B_i $, where $\gamma_i$ are an i.i.d. ...

**1**

vote

**1**answer

80 views

### A distribution which is Wasserstein-close to a compactly supported distribution is almost compactly supported

I wonder whether this is true: If a distribution is very close (in the Wassertein sense) to another distribution with compact support, then the former must put only tiny amount of mass outside a ...

**4**

votes

**0**answers

94 views

### $\ell_p$ geodesic distance on smooth Riemannian manifold and Logarithmic Sobolev Inequalities

Bear with me, I'm not a professional geometer. Recently, I've been studying Logarithmic Sobolev Inequalities (LSI) for probability distributions on manifolds (e.g as done in works of Bobkvo et al. ...

**1**

vote

**2**answers

163 views

### Lower bound on misclassification rate of Lipschitz functions in terms of Lipschitz constant

Important note
@MateuszKwaśnicki in the comment section has raised a fundamental issue with the current statement of the problem. I'm trying to bugfix it.
Setup
I wish to show that a Lipschitz ...

**0**

votes

**0**answers

74 views

### Upper-bound KL divergence between sub-gaussian variables with same variance

A random variable $X$ is said to be sub-gaussian with mean $\mu$ and pseudo-variance $\sigma^2$ iff
$$\mathbb \log(E[\exp(t(X-\mu))]) \le \frac{t^2}{2\sigma^2},\;\forall t \in \mathbb R.
$$
It's a ...

**2**

votes

**0**answers

64 views

### Are sums extremal for subgaussian concentration?

Bobkov and Houdre https://projecteuclid.org/euclid.bj/1178291721
showed that among all $f:R^n\to R$ that are $1$-Lipschitz
with respect to the $\ell_1$ metric,
the variance is maximized by sums. ...

**3**

votes

**1**answer

92 views

### Concentration of measure in graph theory

I am looking for elementary statements in graph theory that illustrate the concentration of measure phenomenon.
(Say, something bit more interesting than most of graphs have diameter 2.)

**8**

votes

**2**answers

157 views

### Largest deviations for uniform order statistics

Let $n >0$.
Let $X_1,\ldots,X_n$ be i.i.d. uniform random variable on $[0,1].$ Denote by $X^{(1)}\leq X^{(2)} \leq \cdots \leq X^{(n)}$ their order statistics, and write $\Delta^{(i)} = \vert X^{(...

**3**

votes

**1**answer

117 views

### What is the Wiener measure of the curves with Hölder index $\frac 1 2$?

One may show that the Wiener measure (for curves in $\mathbb R^n$) is concentrated on the Hölder-continuous curves of Hölder index $< \frac 1 2$. What happens to the curves of Hölder index ...

**5**

votes

**1**answer

199 views

### Variance modulo 1

The fact that the variance of the sum of independent random variables is the sum of their variances allows one to have a good understanding of how well-concentrated each term $X_i$ in a sum of $n$ ...

**0**

votes

**0**answers

50 views

### Lower-bound on the the intersection of an Ellipsoid and a ball

Let $\mathcal{E}=\Big\{x:\mathbb{R}^n: \sum_{i=1}^n\frac{x_i^2}{a_i^2}\le 1\Big\}$ be an ellipsoid. What is a good lower bound for
\begin{align*}
vol\Big(\mathcal{E}\cap \mathcal{B}\Big)
\end{align*}
...

**3**

votes

**1**answer

81 views

### Concentration inequalities specialized for log-likelihood / log-density functions

Let $P$ be a probability measure and $f$ be some probability density function (not necessarily related to $P$). Consider the function
$$
L(X_1,\ldots,X_n)
=\frac1n\sum_{i=1}^n\log f(X_i),
\quad
X_i\...

**0**

votes

**0**answers

85 views

### Concentration of a Gaussian function around its mean

I am interested in showing a certain function of a Gaussian random vector is concentrated around its mean. Let $\mathbf{g}\in\mathbb{R}^n$ be distributed as $\mathcal{N}(\mathbf{0},\mathbf{I}_n)$. I ...

**1**

vote

**0**answers

30 views

### Limiting law of quadratic functions of sample averages

Let $X_1,\cdots,X_n$ be independent centered univariate random variables. Let also $\{w_{ij}\}_{i,j=1}^{k,n}$ be a set of deterministic scalar weights, where $k\ll n$. Define sample averages
$$
\...

**4**

votes

**0**answers

73 views

### On symmetry and measure concentration rate for convex bodies

The concentration of measure on the cube $ [0, 1]^n $ equipped with uniform probability measure $\mu_{\infty}$,
states that for any $A \subset [0, 1]^n $ with $ \mu_{\infty}(A) \geq \frac{1}{2} $,
we ...

**1**

vote

**0**answers

79 views

### Are Outer Products of Sub-Gaussian Vectors Sub-Exponential?

$\newcommand\xx{\mathbf{x}}\newcommand\yy{\mathbf{y}}\newcommand\A{\mathbf{A}}\newcommand\aalpha{\boldsymbol{\alpha}}\newcommand\bbeta{\boldsymbol{\beta}}\newcommand\E{\mathbb{E}}\newcommand\inner[1]{\...

**4**

votes

**1**answer

164 views

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

The concentration of measure on $ [0, 1]^n $ equipped with uniform probability measure $\mu_{\infty}$,
states that for any $A \subset [0, 1]^n $ with $ \mu_{\infty}(A) \geq \frac{1}{2} $,
we have:
$$...

**2**

votes

**1**answer

181 views

### Does variants of Bernstein and Freedman concentration inequalities exist with NO uniform bound on the range of RV or martingale differences

A classic formulation of the Bernstein inequality (from Wikipedia) is as follow:
Let $X_1, \ldots, X_n$ be independent zero-mean random variables. Suppose that $|X_i|\leq M$ almost surely, for all $i$...

**2**

votes

**1**answer

83 views

### Concentration of emperical conditional probability

Assume sequence $(X_1,X_2, X_3, \ldots)$ is a first-order Markov sequence of real random variables where $X_i \in \mathcal{X}$ for some alphabet $\mathcal{X}$ of finite size $k$. Define emperical ...

**6**

votes

**1**answer

142 views

### Martingale version of Bernstein-type inequality for (slightly) heavy-tailed distributions?

It is known that for sub-exponentially distributed martingale difference sequence, the following Bernstein-type inequality holds:
$$
ℙ\left(\left|
\sum_{i=1}^N a_i X_i
\right| \ge t \right)
\le
2\...

**0**

votes

**0**answers

82 views

### Capacity and measure

Fix $p\in [1, 2)$ and denote the $p$-capacity of a compact set $K$ as $p$-$\text{cap}(K)$, i.e.,
\begin{equation}
p\text{-cap}(K)\equiv\left\{\int_{\mathbb{R}^2}|D\varphi|^p\ \mathrm{d}x\ \Big|\ \...

**4**

votes

**0**answers

112 views

### Vector martingale concentration

Let $\varepsilon_1, \dots, \varepsilon_N$ be a martingale difference sequence in $R^d$ with $\|\varepsilon_n\| \le B_n, a.s.$ for each $n=1,\dots,N$. Do we have some Azuma-type concentration ...

**3**

votes

**2**answers

218 views

### Concentration inequality for sum of iid random variables that involve KL distance

Conider $X \in \mathbb{R}^d$ and $Y \in \{0,1\}$, and a joint distribution $p_{XY}(x,y)$, and a set of $N$ i.i.d. samples $\{(X_i,Y_i)\}_{i=1}^{N}$. Define $p_{X0} = p_{XY}(x,0)$ and $p_{X1} = p_{XY}(...

**3**

votes

**1**answer

122 views

### Product of estimates of mean values - Concentration of measure inequality

Let $X_{1},...,X_{d} \in \{-1,1\}^d$ be random variables, with $E[X_j]=\mu_j$. Having $n$ i.i.d. samples $x^{(i)}_1,x^{(i)}_2,....,x^{(i)}_d$, $i=1,...,n $, let $\hat{\mu}_{j}=\frac{1}{n}\sum^{n}_{i=1}...

**3**

votes

**1**answer

149 views

### Uniform Convergence for Vectors

$\textbf{Problem statement:}$
Let $\mathcal H:\mathcal X \rightarrow \{0,1\}$ be a class of Boolean functions for $\mathcal X \subset \mathbb R^n$, and let the VC Dimension of $\mathcal H$ be $VC_{...

**1**

vote

**0**answers

94 views

### Anti-concentration bounds for folded normal and inverse of gaussian variables

Are there any easy to use bounds on sums of the following kind :
$$
\sum_{i = 1}^{i = N} |a_i| \geq P \\
a_i \sim \mathcal{N}(0, 1) \\
$$
and also for sums of the form :
$$
\sum_{i = 1}^{i = M} \...

**1**

vote

**1**answer

151 views

### On concentration of a sum random variable

Take a random variable defined as
$$r=u_{11}v_{1}v_{1}+u_{12}v_{1}v_{2}+\dots+u_{n,n-1}v_{n}v_{n-1}+u_{nn}v_{n}v_{n}$$ where $v_{i}$ are independent uniform random variables from $\{0,\dots,b\}$, $u_{...