The measure-concentration tag has no usage guidance.

**13**

votes

**0**answers

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

**11**

votes

**4**answers

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

**10**

votes

**1**answer

732 views

### Non-probabilistic proof of the Johnson–Lindenstrauss lemma

The Johnson–Lindenstrauss lemma states that a small set of points in a high-dimensional space can be embedded into a space of much lower dimension in such a way that distances between the points are ...

**9**

votes

**2**answers

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

**9**

votes

**2**answers

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

**8**

votes

**3**answers

837 views

### Counterexample of non-negative sequence weakly converging in $\mathscr{M}^1$ but not $L^1$

Hi.
Consider a a sequence of non-negative functions $(f_n)_n$, bounded in $L^1([-1,1])$ and weakly$-\star$ converging in $\mathscr{M}^1([-1,1])$ to some $f\in L^1([-1,1])$. What I mean by this ...

**8**

votes

**2**answers

387 views

### Supremum of measure of sets of measure less or equal to 1/2.

Let $(X,d)$ be a metric space equipped with a probability measure $\mu$ (defined on the Borel $\sigma$-algebra on the topology induced by the metric $d$). I am interested in the different values that ...

**8**

votes

**2**answers

1k 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 \...

**8**

votes

**1**answer

269 views

### Concentration of sum of powers of normals

Let $Z_1,Z_2,\ldots,Z_n$ be i.i.d. copies of a random variable $Z$ distributed as $\frac{1}{\sqrt{2}}X+i\frac{1}{\sqrt{2}}Y$ with $X$ and $Y$ independent standard Normal random variables i.e.~$X\sim\...

**8**

votes

**1**answer

265 views

### Bounds on the moments of the binomial distribution

I'm looking for simple and reasonably tight bounds on the k-th moment of the Binomial distribution $B(n,p)$, namely, $E[B(n,p)^k]$. I'm interested in the case when k is large (say on the order of $\...

**8**

votes

**1**answer

741 views

### Doob Martingale: Where is the catch?

I am working on a research problem in uncertainty propagation that involves sums of possibly dependent random variables with bounded sets of support.
I am attempting to use the method of bounded ...

**7**

votes

**2**answers

192 views

### concentration inequality for entropy from sample

Consider a measure $\mu$ on a finite set, and let $x_1, \ldots, x_n$ be i.i.d samples from $\mu$. Then the expression $S_n = -\frac{1}{n} \sum_{i=1}^n \log \mu(x_i)$ converges by a.s. to the entropy $...

**7**

votes

**2**answers

400 views

### construction of a random measure with a given mean

Let me first pose a trivial question.
Given a Borel probability measure $\mu$ on the real line, is it possible to construct a purely atomic random measure $M$ whose mean is $\mu$?
The answer is ...

**7**

votes

**4**answers

179 views

### What can be said about the concentration of measure of product of Gaussian variables?

I have a set of random variables $X_1,\ldots,X_n$, all Gaussian with mean 0 and variance 1, indepedent. Let $p(x_1,\ldots,x_n)$ be some polynomial that takes products and sums of $x_1,\ldots,x_n$.
...

**7**

votes

**1**answer

274 views

### Level sets of weakly differentiable funtions

Let $C$ be a $C^1$ hypersurface in $R^n$ and let $u \in C^1(R^n)$. Suppose
$$\nabla u(x) \cdot \eta(x)=|\nabla u| \ \ \forall x\in C$$
where $\eta(x)$ is the normal vector to $C$ at $x$ ($\nabla u$ ...

**6**

votes

**1**answer

451 views

### First nonzero eigenvalue of the Laplacian on the submanifold

Consider a compact, connected $n$ dimensional Riemmanian manifold $\mathcal{N}$ and its $m$ dimensional closed submanifold $\mathcal{M}$ (with the metric coming from from the one defined on $\mathcal{...

**6**

votes

**2**answers

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

**6**

votes

**0**answers

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

**6**

votes

**0**answers

232 views

### Chernoff bound in the not-quite-sub-exponential case

In Terry Tao's notes on Concentration of measure, Exercise 7 indicates that the Chernoff bound can be generalized to sub-exponential random variables:
http://terrytao.wordpress.com/2010/01/03/254a-...

**6**

votes

**2**answers

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

**5**

votes

**1**answer

182 views

### Concentration bounds on weighted sum of i.i.d. Bernoulli random variables

Let $X_1,\dots, X_n\sim\operatorname{Bern}(\frac{1}{2})$ be independent, identically distributed random variables, and $\alpha=(\alpha_1,\dots,\alpha_n)\in[0,1]^n$ a vector of non-negative weights ...

**5**

votes

**1**answer

297 views

### Measure concentration for weakly dependent random variables

For an application quite alien to probability theory, I'd like to have a kind of measure concentration estimate, in the following spirit. Suppose that to every $1\le i,j\le n$ there corresponds a zero-...

**5**

votes

**2**answers

397 views

### Local concentration of measure on Erdos-Rényi graph

Let $G_n=(V_n,E_n)$ be an Erdos-Rényi random graph, precisely the vertex set is $V_n=(1,\dots,n)$ and the edge set is $E_n=(ij\in\mathcal{P}_2(V_n)\ |\ \epsilon_{ij}=1)$ where $(\epsilon_{ij})_{ij}$ ...

**5**

votes

**2**answers

432 views

### Non-asymptotic large deviations for a convex set

Let $X_1,\dots,X_n$ be $n$ i.i.d random variables taking values in a Polish vector space $\mathcal{X}$ and with (Borel) probability distribution $\mu$.
For any convex, compact $\Gamma \subset \...

**5**

votes

**1**answer

407 views

### Expectation of ratio of functions of i.i.d. Bernoullis: a concentration question

Consider the following $n \times n$ symmetric matrix of i.i.d. Bernoulli random variables, $X_{ij}$. For $i=1,...,n$ and $i<j\le n$. Let $X_{ij} \sim \text{Bernoulli}(p)$ when $i \ne j$ ($p$ fixed)...

**5**

votes

**1**answer

188 views

### concentration of random matrices involving normal random variables

Define the random variable
\begin{align*}
A=|a_1|^2\mathbf{a}\mathbf{a}^*
\end{align*}
where $\mathbf{a}\in\mathbb{c}^n$ is a random vector distributed as $\mathcal{N}(0,\mathbf{I}/2)+i\mathcal{N}(0,\...

**5**

votes

**0**answers

108 views

### Eigenvalues of Random Regular Bipartite Graphs

I am looking for a way of getting a good estimate of the eigenvalues of random bipartite d-regular graphs. The literature has very precise values the proofs of which are very involved and since I am ...

**4**

votes

**1**answer

239 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

**3**answers

538 views

### Lower bound for Gaussian random vector with negative correlation

Let $X = (X_1,\ldots,X_n) \in \mathbb{R}^n$ be jointly Gaussian with mean $0$, covariance matrix: $Var(X_i) = 1$, $Cov(X_i, X_{i+1}) = -1/2$, and $Cov(X_i, X_j) = 0$ else.
Let $\zeta \in \mathbb{R}^...

**4**

votes

**1**answer

206 views

### Tail bounds on eigenvalue gaps for GUE

What I'm looking for is a non-asymptotic bound on the probability that the smallest gap between eigenvalues of a GUE matrix does not exceed a certain value.
I'm aware of the bounds in
http://imrn....

**4**

votes

**2**answers

117 views

### Do subgaussian variables obey the slightly-stronger-than-Chernoff tail bound?

If $X \sim Normal(0,1)$, then we have the tail bound:
$$ (*) \qquad\Pr[X > t] \leq \mathcal{O}\left(\frac{e^{-t^2/2}}{t}\right) .$$
Now for general variables $X$, a nice condition is that $X$ be ...

**4**

votes

**1**answer

55 views

### Concentration of U-statistics for exchangable distributions (and the unbounded case)

Consider the following so-called $U$-statistic of order 2: $$U = \frac1{\binom{m}{2}} \sum_{i < j} h(w_i,w_j)$$ where $w_1,\dots,w_m$ are IID from some distribution and $h$ is symmetric. If $|h(w_1,...

**4**

votes

**1**answer

97 views

### Concentration of spectral norm

Let $X_{ij}$ be independent (but not identically distributed) real-valued random variables for $1\leq i\leq j\leq n.$ Let $X$ be the symmetric matrix whose entries are given by $X_{ij}.$ Let
\begin{...

**4**

votes

**1**answer

466 views

### An elementary probability question

Let $X$ be a $d$-dimensional random vector distributed according to probability measure $D$. At least the second moment of the coordinates of $X$ is finite.
Consider $n+1$ samples $X_0, \ldots, X_n ...

**4**

votes

**2**answers

155 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

104 views

### Large Deviations: Exponential decay in normed spaces

Let $(X_1,X_2,\cdots)$ be a sequence of independent and identically distributed random variables taking values in some general normed space $(V,||\cdot||)$. Denote $\mu=E[X_1]$ and $S_n=\frac{1}{n}[...

**4**

votes

**0**answers

92 views

### Concentration of weighted random chirp

I'm interested in seeing whether the following is true. Assume $u$ is uniform on $[0,1]$. For a fixed $x\in\mathbb{C}^n$ with $\|x\|_{2}=1$ we have
\begin{align*}
\mathbb{P}\Big\{\Big|\sum_{k=0}^{n-1}...

**3**

votes

**1**answer

555 views

### concentration inequality for averages of dependent random variables

Let $X \in R^n$ be a random vector such that
$$P(|X_i| > \epsilon) > e^{-\epsilon^2}$$
What is a tight bound on
$$P(\sum_{i=1}^n |X_i| > \epsilon)$$
and on
$$P(\max_{1\le i\le n} |X_i| ...

**3**

votes

**1**answer

46 views

### Tail bound for product of normal distribution

Let $U, V$ be two standard normal random variables with covariance $cov(U,V) = \beta \in [0,1)$. Let $W = UV$ be the product of two RV's, and $W_1, W_2, \ldots, W_n$ be n i.i.d copies of $W$, what's ...

**3**

votes

**2**answers

357 views

### Measure concentration for law of large numbers

The classical law of large numbers states that
$$\frac1k\sum_{i=1}^k X_i \rightarrow \mathbb{E} X_1$$
for i.i.d. $X_1, X_2, \ldots$ with finite $L^1$ norm.
I was wondering whether is it possible to ...

**3**

votes

**1**answer

158 views

### Strictly positive solutions of a random linear system

Suppose $B\in\mathbb{R}^{m\times n}$ is a random binary matrix with i.i.d entries and $c\in \mathbb{R}^m$ is a strictly positive vector, that is $c_i>0$ for $i=1,2,\cdots m$. Also assume $m<n$, ...

**3**

votes

**1**answer

155 views

### Variance of maximum of mixture of gaussians

Let $\{X_i\}$ be an iid collection of standard normal $(N(0,1))$ random variables . Let $X = (X_1,\ldots,X_n)$, and consider a function of the form $f(X) = \max(A\cdot X)$, where $A$ is some symmetric,...

**3**

votes

**1**answer

433 views

### Chernoff-Hoeffding bound for complex values

Consider the Chernoff-Hoeffding bound, stated as follows: Let $X_1, \dots, X_K$ be i.i.d. real-valued random variables with expectation value
$\mu$ and satisfying $|X_i| \le b$.
Let $\epsilon > 0$. ...

**3**

votes

**0**answers

111 views

### McDiarmid-like inequality for subgassian random variables

Let $X_n$ be a set of $N$ subgaussian random variables, not necessarily independent, with $E\exp(\lambda X_n) \le \exp(\lambda^2/2)$. Let $X=(X_1,\ldots, X_N)$ and $f:\mathbb R^N \rightarrow \mathbb R$...

**3**

votes

**0**answers

131 views

### A generalization of coupon collector problem - $\geq1$ pick per experiment

Mix $T\geq1$ coupons numbered $1$ to $T$ with a set of $S\geq0$ number of dummy coupons with no numbers. Select $N\geq1$ coupons at each trial at random and put them back.
$N=1$ is standard coupon ...

**3**

votes

**0**answers

81 views

### Improving concentration estimates by controlling sums on subsets

Let $X_1, \dots, X_N$ be uniform random variables (r.v.) in $[-1, 1]$, and let $S_N$ be their sum $S_N = \sum_{i=1}^N X_i$.
If the r.v. are taken independent, then the CLT suggests that $S_N$ is ...

**3**

votes

**1**answer

112 views

### Concentration and Correlation for Magnitudes of Gaussian Vectors

Suppose we have a large collection of standard normal random variables $a_i\in\mathbb{R}^n$. We know by standard concentration results that if we take $m \geq C\left(t/\epsilon\right)^2n$ samples, ...

**3**

votes

**0**answers

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

**3**

votes

**0**answers

228 views

### Concentration of functions of random unitary matrices

Suppose $U$ and $V$ are $n \times n$ random unitary matrices, chosen independently from the Haar measure. Is there any kind of concentration inequality which would be applicable to polynomials $p(U,V)$...

**2**

votes

**1**answer

217 views

### Is there monotonicity of measure concentration?

Suppose $X$ and $Y$ are nonnegative random variables such that $\mathrm{Pr}(X\geq t)\leq\mathrm{Pr}(Y\geq t)$ for all $t\geq0$. Now take $X_1,\ldots,X_n$ to be independent with the same distribution ...