# Questions tagged [measure-concentration]

The measure-concentration tag has no usage guidance.

22
questions

**3**

votes

**3**answers

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

**18**

votes

**1**answer

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

**14**

votes

**2**answers

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

**9**

votes

**2**answers

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

**12**

votes

**2**answers

1k views

### Can we do better than Azuma-Hoeffding when the variance is small?

The Azuma-Hoeffding Inequality says that if $X_1,X_2, \ldots$ is a martingale and the differences are bounded by constants, $\|X_i - X_{i-1}\| \le 1$ say, then we should not expect the difference $\|...

**13**

votes

**4**answers

1k views

### More than $n$ approximately orthonormal vectors in $R^n$

This question was asked at math.stackexchange, where it got several upvotes but no answers.
It is impossible to find $n+1$ mutually orthonormal vectors in $R^n$.
However, it is well established that ...

**8**

votes

**2**answers

880 views

### Does Multiplicative Version of Azuma's Inequality Hold?

It is known that there are multiplicative version concentration inequalities for
sums of independent random variables. For example, the following
multiplicative version Chernoff bound.
Chernoff bound:...

**2**

votes

**2**answers

3k views

### Hoeffding's inequality for vector valued random variables

Is there a version of Hoeffding's inequality for vector valued random variables?
This seems to be hard to find and I wonder why. I suppose it is difficult to show Hoeffding's lemma, since the proof ...

**6**

votes

**3**answers

363 views

### Isoperimetric inequality for $\epsilon$-expansion of a set only along a certain subspace

Let $\gamma_n$ be the standard gaussian distribution on $\mathbb R^n$. Let $V$ be a $k$-dimensional subspace of $\mathbb R^n$. Finally let $A$ be any (nonempty) Borel subset of $A$ with $\gamma_n(A) = ...

**4**

votes

**1**answer

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

**4**

votes

**1**answer

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

**2**

votes

**2**answers

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

**3**

votes

**0**answers

88 views

### Eigenvalues of Hadamard product of two Wishart-type matrices

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

**0**

votes

**2**answers

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=1$
$u_k$ converges to $u$ ...

**5**

votes

**1**answer

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

**4**

votes

**0**answers

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

**3**

votes

**1**answer

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

**2**

votes

**1**answer

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

**1**

vote

**1**answer

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

**0**

votes

**2**answers

200 views

### Use covering number to get uniform concentration from pointwise concentration

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

**0**

votes

**1**answer

127 views

### Sum of sequences of random variables, with variable success probabilities

Consider two sequences of (not necessarily independent) Bernoulli random variables $X_1, X_2, \ldots, X_n$ and $Y_1, Y_2, \ldots, Y_n$. Suppose that for any $i$, we have $\Pr[X_i = 1] = \Pr[Y_i = 1] = ...

**0**

votes

**1**answer

156 views

### Convergence of quadratic form $y^T Q y$ where $y$ is a random iid sequence of length $n$ and $Q$ is an $n \times n$ random matrix independent of $y$

For each positive integer, let $Q_n=(q_{i,j})_{i,j \in [n]}$ be a random $n \times n$ psd matrix. In the limit $n \to \infty$, suppose the eigenvalues of this sequence of matrices are uniformly ...