The measure-concentration tag has no usage guidance.

**1**

vote

**0**answers

30 views

### Distribution of singular vectors product

Suppose I have $n$ independent realizations of $Z \sim N_p(0, \Sigma)$ where $\Sigma$ is $p \times p$,symmetric, and positive definite; and $n > p$. Let $X = (z_1, \dots, z_n)' \in \mathbb{R}^{n \...

**-1**

votes

**1**answer

100 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

106 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

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

**2**

votes

**1**answer

60 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

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

**1**

vote

**0**answers

66 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

29 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

27 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

127 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

78 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

90 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

**1**answer

99 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

39 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

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

**2**

votes

**1**answer

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

**7**

votes

**2**answers

126 views

### Largest deviations for uniform order statistics

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

**0**

votes

**0**answers

48 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

193 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

41 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

73 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

79 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

70 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

67 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

153 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

145 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

78 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

128 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

80 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

92 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

182 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

120 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

148 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

79 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

146 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_{...

**3**

votes

**0**answers

64 views

### A concentration problem of product of matrices

Let $A$ be an $n \times m$ matrix with non-negative entries and $B \in \mathbb{R^{n\times n}_{\geq 0}}, C \in \mathbb{R^{m\times m}_{\geq 0}}$ be random matrices where B and C are both symmetric and ...

**2**

votes

**0**answers

98 views

### McDiarmid's Inequality bounding deviation with multiplicative error?

Fix $m$ arbitrary values $x_1, x_2, ..., x_m$ in $[0,1]$, and an integer $n$. Obtain $n$-set $S$ by drawing $n \le m$ times randomly without replacement from $\{1,2,..,m\}$. Define r.v. $X = \sum_{i ...

**2**

votes

**0**answers

35 views

### Mean width of intersection of two elipsoid

My question is regarding mean widths. For a set $\mathcal{T}$ define the mean width
\begin{align*}
\omega(T)=\mathbb{E}_{\mathbf{g}\sim\mathcal{N}(0,\mathbf{I})}\bigg[\underset{\mathbf{u}\in\mathcal{...

**5**

votes

**0**answers

82 views

### Is there a concentration inequality depending on dimension for a symmetric function on product space?

I recently read an elegant paper of Bobkov
Bobkov, S.G., On concentration of measure on the cube, J. Math. Sci., New York 165, No. 1, 60-70 (2010); translation from Probl. Mat. Anal. 44, 55-64 (2010)....

**0**

votes

**0**answers

85 views

### concentration inequalities on RKHS?

Let $\mathcal{H}$ be an RKHS and $\phi$ is defined such that $\langle \phi(x), l\rangle_{\mathcal{H}} = l(h(x),h'(x))$, where $h$ and $h'$ are two functions on a function space $\mathcal{F}$. I'm ...

**1**

vote

**0**answers

99 views

### Tail bound without independence

Suppose $X_i , X_j\in \mathbb{R}^d$ are gaussian vectors and $A$ is an $n\times n$ symmetric PSD matrix where $A_{ij} = f(\|X_i-X_j\|_2), \quad i,j\in 1,\ldots,n\;$ for some non-negative Lipschitz ...

**1**

vote

**1**answer

114 views

### Variance bound of a functional

$X_1,\ldots,X_n$ are i.i.d standard normal random variables.
$a_1,\ldots, a_n$ are constants with $a_i \in [\kappa_1, \kappa_2]$ for all $i$ and $\kappa_1>0$.
$\hat c_n$ is given as the solution ...

**5**

votes

**1**answer

278 views

### What are some of results in low dimensional statistics that do not hold in high dimensions?

This question is partially inspired by the following MO post: What are some of the surprising results of finite sample statistical estimation? and current heated research front of high dimensional ...

**3**

votes

**1**answer

181 views

### Constructive Central Limit Theorem

Background: Let $\{a_i\}_{i=1}^n$ be i.i.d. random variables with zero-mean and unit variance, on a probability space $\Omega$. Define $$s_n=\frac{1}{\sqrt{n}}\sum_{i\leq n} a_i$$
Central limit ...

**2**

votes

**0**answers

112 views

### Anti-concentration for sum of t-wise independent uniform variables

Let $X_{1},\ldots,X_{n}$ be i.i.d. random variables, each variable is uniform over the set of integers $\{ 0,\ldots,D-1 \}$. Let $S = \sum_{i=1}^{n}X_{i}$.
By ``small ball probability'', we have that ...

**3**

votes

**1**answer

129 views

### Concentration inequality of joint event over time of a submartingale

Consider a discrete time submartingale $X_n$ with bounded difference $|X_n-X_{n-1}|\leq c$. With Azuma inequality we have the concentration of a single time event as
$$
P(X_t-X_0 \leq -t) \leq exp\...

**4**

votes

**0**answers

83 views

### Is there an example that both Berry-Essen bound and DKW bound are attained?

The Berry-Essen bound stated that
$$\sup _{{x\in {\mathbb R}}}\left|\widehat{F_{n}(x)}-\Phi (x)\right|\leq C_{0}\cdot \psi _{0}$$
where $\psi _{0}(n)={\Big (}{\textstyle \sum \limits _{{i=1}}^{n}\...

**2**

votes

**2**answers

223 views

### Lower bound on number of samples for an epsilon delta approximation matching the Chernoff bound

So we have two biased coins, one comes out head w.p. $1/2+\epsilon$ and the other w.p. $1/2-\epsilon$. How many times should we flip these two coins to be able to tell them apart w.p. at least $\delta$...

**1**

vote

**1**answer

92 views

### Extension of Gordon's comparison inequality to subgaussian processes?

"Theorem A" in this paper by Y. Gordon:
http://www.math.uiuc.edu/~mjunge/Comps/Gordonm.pdf
is a comparison inequality for Gaussian processes:
Is there an analogue of this result for subgaussian ...