Skip to main content

All Questions

Filter by
Sorted by
Tagged with
10 votes
2 answers
1k views

Simple proof of sharp constant in DKW inequality

The DKW inequality says that if $F_n$ is the empirical CDF corresponding to real-valued random variables $X_1, \dots, X_n$ distributed identically and independently from a distribution with CDF $F$, ...
3 votes
0 answers
130 views

A Talagrand inequality for the supremum of partial sums over function classes under dependence. (Reference request)

As a consequence to the Talagrand concentration inequality, it is well known that for a measurable space $(S,\mathcal{S})$ and an i.i.d. sample $X_1,...,X_n$ of $S$-valued random variables, if $\...
1 vote
0 answers
42 views

Sub-Gaussian analysis via bounded decomposition?

Let $\psi_\alpha(x) := \exp(x^\alpha)-1$. The Sub-Gaussian Norm $\lVert X \rVert_{\psi_2}$ of a random variable $X$ is defined as $$ \lVert X\rVert_{\psi_2} = \inf\{c>0\mid \mathbb{E}[\varphi_2(|X|/...
5 votes
1 answer
402 views

Lower tail of random rank one sums?

Let $\{x_i\}_{i\geq 1}$ be iid random elements of the sequence space $\ell^2(\mathbb{N})$; assume that $\|x_i\|_2 \leq 1$ almost surely. Let $\Sigma = \mathbb{E}[x_1 \otimes x_1]$. Define $$ \Sigma_n =...
5 votes
1 answer
282 views

What is the spectral norm of a random projection times a diagonal?

Take $n\ll N$. Let $P$ be an $n\times N$ matrix of iid $\mathcal{N}(0,1)$ random variables, and let $D$ be an $N\times N$ diagonal matrix. What can be said about the distribution of the largest ...
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 ...
1 vote
0 answers
351 views

Tail bounds for random Gaussian chaos?

Let $g = (g_1, \dots, g_d)$ be a sequence of independent standard Normal random variables, and suppose $\Sigma$ is a $d \times d$ (deterministic), real, symmetric, positive definite matrix. The Hanson-...
0 votes
0 answers
86 views

Expected diameter of a random point set

General problem: For a point set $S\subset X$ in a metric space $(X,d)$, let $\text{diam}(S)=\max_{x,y\in S}d(x,y)$. Given a distribution $P$ on $X$ and $m$ i.i.d. points $x_1,\ldots,x_m\sim P$, what ...
3 votes
1 answer
555 views

How did the story of Kim-Vu type inequalities continue?

I am interested in the concentration of polynomials of random variables. I have been reading Boucheron, Lugosi, and Massart's "Concentration inequalities" and they give some references. ...
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) ...
0 votes
1 answer
280 views

Lower-bound on smallest singular-value of rectangular random matrix

Let $X$ be a random $N \times n$ matrix with iid entries from $\mathcal N(0, 1)$ and with $n/N =: \lambda(N,n) \le \lambda_0$, for some $\lambda_0 \in (0, 1)$. That is, $X$ is genuinely rectangular (...
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/...
0 votes
1 answer
116 views

Compute lower bound on $\min_{E} \mathcal N(0,\sigma^2 I_n)(E)$ subject to $vol(E \cap H_n(r)) / vol(H_n(r)) \ge p$ where $H_n(r)$ is $n$-hemisphere

Let $n \ge 2$ be an integer, which may be assumed to be very large. For $r > 0$, consider the hemi-sphere $H_n(r) := S_n(r) \cap (\mathbb R^+ \times \mathbb R^{n-1})$, where $$ S_n(r):= \{x \in \...
2 votes
1 answer
97 views

Concentration of measure on finite powers of $S^\infty$

I am wondering about a natural generalization of theorem 1.4 in the article Dvoretzky's theorem — Thirty years later by Milman. My first thought was to look at Milman's paper that he cites for the ...
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 $\|...
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$ ...
1 vote
0 answers
175 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. ...
4 votes
0 answers
116 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. ...
5 votes
1 answer
372 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 ...
10 votes
4 answers
645 views

Expected value of Bernoulli quadratic forms

Let $\mathbf{Y}\in\mathbb{R}^{n\times n}$ be a symmetric matrix. Let $\mathbf{x}\in\mathbb{R}^n$ be random vectors with entries i.i.d. $\pm 1$ with equal probability. I'm interested in a lower bound ...
4 votes
0 answers
141 views

Is there an example that both Berry-Essen bound and DKW bound are attained?

The Berry-Essen bound stated that $$\sup _{{x\in {\mathbb R}}}\left|\widehat{F_{n}(x)}-\Phi (x)\right|\leq C_{0}\cdot \psi _{0}$$ where $\psi _{0}(n)={\Big (}{\textstyle \sum \limits _{{i=1}}^{n}\...
9 votes
0 answers
1k views

Balls and bins -- concentration bounds pertaining to the minimal load bin

Consider the standard balls and bins process, where $m$ balls are thrown uniformly at random into $n$ bins. Previous work has been done on estimating the value of the maximum load (i.e., the number of ...
9 votes
2 answers
1k views

Adaptive version of the Azuma–Hoeffding inequality

The Azuma inequality states that if we have a martingale $X_1,\ldots,X_N$ that satisfies a bounded difference condition: $$|X_k - X_{k-1}| \leq c_k$$ Then: $$\Pr\left[X_N - X_0 \geq \sqrt{2\sum_kc_k^2 ...
1 vote
0 answers
361 views

concentration inequalities for quadratic forms of correlated random vectors

Let $\mathbf{n}$ is a Gaussian random vector with mean $\mathbf{0}$ and co-variance matrix $\mathbf{H}$. Let $\mathbf{r} = Sign(\mathbf{n})$, where $Sign(n_i) = 1$ if $n_i>0$ and $Sign(n_i) = -1$ ...
-1 votes
1 answer
104 views

Question about measure lemma?

"Let (u_j) be a bounded sequence from $W^{1,p}(\Omega)$ how to prove that there exists a subsequence such that $u_j\rightharpoonup u$ in $W^{1,p}_0(\Omega)$ and $|\nabla u_j|\rightharpoonup d\mu,$ $|...
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$:...
1 vote
0 answers
98 views

Small ball probabilities for functions of correlated normals

Let $f : \mathbb{R}^k \rightarrow \mathbb{R}$ and let $X$ be distributed k-dimensional normal with mean $0$ (with "arbitrary" covariance matrix). I am looking for references with bounds of the form: ...
7 votes
2 answers
2k views

Tails of sums of Weibull random variables

Suppose that $X_1, X_2, \ldots, X_n$ are i.i.d random variables distributed according to Weibull distribution with shape $0 < \epsilon < 1$ (it means that $\mathbf{Pr}[X_i \geq t] = e^{-\Theta(t^...
11 votes
2 answers
3k views

Levy's isoperimetric inequality for sphere

Let me recall subj: If $s>0$, $A$ and $B$ are two subsets of $\mathbb{S}^{n}$, $|A|=|B|$ ($|\cdot|$ stands for the Lebesgue measure on the sphere) and $B$ is a cup $B=\{ (x_1,x_2,\dots,x_n)\in \...