Questions tagged [measure-concentration]

The tag has no usage guidance.

22 questions
Filter by
Sorted by
Tagged with
2k 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 ...
926 views

How fast can extreme eigenvalues of the average of random matrices converge to their expectation?

Suppose that $X_1,X_2,\ldots,X_m$ are independent $d\times d$ random matrices and let $\overline{X} := \frac{1}{m}\sum_{i=1}^m X_i$. One of the questions studied under the theory of random matrices is ...
2k views

Concentration bounds for sums of random variables of permutations

I'm trying to find theorems regarding random variables derived from sampling permutations, specifically concentration bounds. As an example, let $X_i$ be the $\{0,1\}$-random variable that represents ...
3k views

Extension of the Azuma-Hoeffding inequality (when the differences are bounded with large probability)

Let $(X_i)$ be a super-martingale and suppose their differences are bounded ''with high probability'', that is $$\mathbb{P}(\exists\,i=1,\dots,n\text{ s.t. }|X_i-X_{i-1}|>c_i) \,\leq\, \epsilon$$ ...
1k views

390 views

Concentration inequalities in $\ell_{\infty}$ for sums of iid random ("nice") functions?

I'm looking for "tail-bound-like" inequalities that look like this (I state a specific setting but more general settings are interesting): Let $D$ be a distribution on a set of "nice" functions $g$:...
608 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$...
344 views

Concentration and anti-concentration of gap between largest and second largest value in Gaussian iid sample

Let $n \ge 3$ be an integer and let $X=(X_1,\ldots,X_n)$ be random vector with iid coordinates from $N(0,1)$. For $1 \le k \le n$, let $X_{(k)}$ be the value of the $k$th largest coordinate of $X$. ...
88 views

Given two independent Gaussian matrices with i.i.d. entries: $A\in\mathbb{R}^{n\times p}$ and $B\in\mathbb{R}^{n\times q}$, where and $A_{i,j},B_{i,j}\sim\mathcal{N}(0,1)$. Assume that $\max(p,q)<n.... 2answers 422 views Weak convergence of the image of a weakly$L^1$converging sequence This is a follow-up on another question. Can something be said about the image of a weakly converging sequence in$L^1$? More precisely$u_k\ge 0\|u_k\|_{L^1}=\int u_k=1u_k$converges to$u$... 1answer 180 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$... 0answers 122 views For a martingale$f_0,f_1,\ldots $how can we bound$P(\frac{1}{n} \|f_n\| \le 1$for all$ n \ge N)$? Suppose$f_0,f_1, \ldots$is a martingale (or i.i.d sequence) in$\mathbb R^d$with$f_0=0$and all$\|f_n - f_{n-1}\| \le L$say. There are many concentration results for the initial segment of the ... 1answer 143 views How tight is the bound$P(\|X\|^2 \ge t |\langle a,X\rangle|) \ge 1 - t\sqrt{\frac{2}{m-1}}$, where$X \sim N(0, I_m)$and$\|a\| = 1$? Let$X$be a random vector in$\mathbb R^m$with iid$N(0,1)$coordinates and let$a$be a fixed unit vector in$\mathbb R^m$. In another post (SE link here https://math.stackexchange.com/a/3792730/... 1answer 163 views Prove / disprove: If$1 \le n < N$and$A$is an$N \times n$matrix with iid from$\mathcal N(0,1)$, then$s_\min(A) \ge c\sqrt{N}$w.p$1-2e^{-N}$Let$1 \le n < N$be integers and$A$be a random$N\times n$matrix with iid entries from$\mathcal N(0,1)$. This paper (Rudelson and Vershynin) claims in the paragraph just before formula (3.4) ... 1answer 137 views Approximate the singular values of a certain random dot-product kernel matrix (in the sense of El Karoui, Cheng-Singer, etc.) Let$g:\mathbb R \to \mathbb R $be a continuous function which is "sufficiently smooth" (e.g$\mathcal C^3$) around$0$, and "sufficiently integrable" (e.g integrable w.r.t$N(0,...
Let $\Theta$ be a subset of a metric space. Suppose $(X_\theta)_{\theta \in \Theta}$ is a random process on $\Theta$ which is $L$-Lipschitz and with the property that there exists constants $A, B>0$...