All Questions
Tagged with measure-concentration reference-request
6 questions
12
votes
2
answers
2k
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 $\|...
- 1,955
5
votes
1
answer
248
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$ ...
- 6,853
4
votes
2
answers
434
views
Rate of convergence of sample maximum, $\Big|\max_{j \leq n} |f(U_j)| - \|f\|_\infty\Big|$
Suppose that $f \colon [0, 1] \to \mathbb{R}$ is a $1$-Lipschitz function.
Define the uniform norm $\|f\|_\infty = \sup_{x} |f(x)|$.
Given $\{U_j\}_{j=1}^\infty$ independent and identically ...
- 380
4
votes
1
answer
474
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,529
3
votes
1
answer
182
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/...
- 6,853
2
votes
1
answer
212
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) ...
- 6,853