Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

0
votes
2answers
89 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
1answer
217 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
0answers
41 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
0answers
97 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^...
0
votes
0answers
51 views

Concentration of Gaussian and vector on unit sphere

Suppose I have a random vector $v \in \mathbb{R}^{n}$ such that $\|v\|_2 = 1$, where $v$ is uniformly distributed on the unit sphere. I am wondering if I can establish a concentration inequality for ...
3
votes
1answer
114 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
1answer
114 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
1answer
116 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
1answer
80 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
1answer
131 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
0answers
56 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
0answers
68 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
0answers
31 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
0answers
30 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
0answers
136 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
1answer
79 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
0answers
93 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
1answer
122 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
0answers
57 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
0answers
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. ...
3
votes
1answer
89 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
2answers
151 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
1answer
107 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
1answer
194 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
0answers
45 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
1answer
76 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
0answers
81 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
0answers
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
0answers
71 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
0answers
70 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
1answer
163 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
1answer
165 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
1answer
79 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
1answer
132 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
0answers
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
0answers
104 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
2answers
202 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
1answer
121 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
1answer
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
0answers
88 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
1answer
149 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
0answers
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
0answers
109 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
0answers
36 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
0answers
84 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
0answers
87 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
0answers
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
1answer
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
1answer
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
1answer
182 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 ...