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