The measure-concentration tag has no wiki summary.

**1**

vote

**0**answers

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

**0**

votes

**0**answers

32 views

### Tail Bounds for the minimum value of a function

Consider y to be the minimum value of an objective function over some subspace. More specifically
$y= \min_x \|e+Bx\|_\infty \quad s.t. \quad x\in \mathcal{S}$
where $e$ is a known vector, $B$ is a ...

**7**

votes

**1**answer

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

**2**

votes

**1**answer

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

**4**

votes

**2**answers

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

**7**

votes

**1**answer

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

**2**

votes

**1**answer

139 views

### Derive concentration bound for the derivative

It that true to conclude that if a random $f(z)$ is a sub-Gaussian random variable for a constant value of z, its derivative $f'(z)|_{z=k}$ with respect to variable $z$ is also sub-Gaussian?
In ...

**0**

votes

**0**answers

42 views

### Concentration bound for $f(w) = w \times \sin wz$

I need to find an exponential bound for $P(|S_n - \mu| > \lambda)$ where $S_n = \frac{1}{D} \sum_{i=1}^D w_i \sin w_iz$ for a constant $z$, $E(S_n) = \mu$ and $w_i$ are drawn from the normal ...

**3**

votes

**1**answer

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

**3**

votes

**1**answer

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

**8**

votes

**4**answers

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

**3**

votes

**1**answer

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

**1**

vote

**0**answers

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

**1**

vote

**1**answer

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

**1**

vote

**0**answers

128 views

### Upper bound on expectations of the sum of product of a martingale difference sequence with a predictable sequence, weighted by certain random weights

Let $(\mathcal{F}_i)_{i\geq 1}$ be a filtration. Let $0\leq p_i\leq 1$, be a random variable measurable w.r.t. $\mathcal{F}_i$. Consider two sequences of random vectors ...

**2**

votes

**1**answer

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

**1**

vote

**2**answers

199 views

### Asymptotic Expansion of Distribution in Central Limit Theorem for Non-Identically Distributed Random Variables

My question is related to the following theorem (e.g. Section XVI.4 of Feller's 1971 book): Let $Z_i$ $(i=1,\cdots,n)$ be independent and identically distributed random variables with mean zero, ...

**2**

votes

**1**answer

247 views

### Upper bound on the maxima of ratio of expectation of quantities under Gaussian measure

Let $\lambda,\eta >0$ be given, and $u:\mathbb{R}\rightarrow \mathbb{R}$ be a real valued function. Define
$$\Delta(u)= \frac{\int u(h) \exp(-\eta ...

**4**

votes

**1**answer

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

**1**

vote

**2**answers

242 views

### How many boxes so that there is $k$ of same of color from $n$ different colors?

Say you have $m$ boxes each of which is colored with one of $n$ colors. What should $m$ be so that the probability that there is atleast $k$ boxes with one same color is strictly greater than ...

**4**

votes

**0**answers

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

**8**

votes

**2**answers

287 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

**3**answers

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

**2**

votes

**1**answer

262 views

### A Johnson-Lindenstrauss lemma for finite fields?

Given $m$ points in $\mathbb{R}^N$, the Johnson-Lindenstrauss lemma guarantees the existence of a linear operator $\mathbb{R}^N\rightarrow\mathbb{R}^n$ that nearly preserves pairwise distances between ...

**2**

votes

**0**answers

340 views

### Concentration of sum of independent random variables

Let $X_1, ..., X_n$ be i.i.d. sub-Gaussian random variables with mean $0$ and variance $1$. That is, we have $Pr[|X_i| > t] \leq \exp(1-t^2/K^2)$ for all $t>0$ and a parameter $K$.
Then we can ...

**5**

votes

**0**answers

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

**5**

votes

**2**answers

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

**3**

votes

**1**answer

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

**2**

votes

**1**answer

265 views

### concentration inequality for averages of dependent random variables

Let $X \in R^n$ be a random vector such that
$$P(|X_i| > \epsilon) \le 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| ...

**7**

votes

**2**answers

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

**2**

votes

**0**answers

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

**4**

votes

**2**answers

542 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] = ...

**4**

votes

**1**answer

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

**-1**

votes

**2**answers

437 views

### Approximating a subspace by sampling a base without replacement

Let $X$ be a $p \times n$ matrix, with $p > n$. Now, suppose I sample $m < n$ columns from $X$ at random, without replacement. I would like to characterize the distance between the subspace ...

**1**

vote

**0**answers

165 views

### A Multiplicative version of McDiarmid's Inequality like the one of Chernoff-Hoeffding Bounds

McDiarmid's Inequality basically says the following:
Let $X_1, X_2, X_3, \ldots, X_n$ denote independent random variables and $f$ is a function of $n$ real arguments. If changing the value of the ...

**0**

votes

**2**answers

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

**2**

votes

**2**answers

390 views

### Weak convergence of the image of an $L^1$ converging sequence under a convex function

Suppose that $u_k$ is a sequence of $L^1$ functions defined on a compact $K\subset R^n$ and a function $f:[0, \infty)\to[0, \infty)$ with the following properties
$u_k\ge 0$
$\|u_k\|_{L^1}=\int ...

**10**

votes

**1**answer

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

**1**

vote

**1**answer

289 views

### Azuma's Inequality when the conditions hold with high probability?

In Azuma's Inequality, is the statement true when $|X_k - X_{k-1}| < c_k$ almost surely rather than with probability 1? If not, is there another result which gives strong concentration when the ...

**6**

votes

**0**answers

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

**1**

vote

**0**answers

153 views

### When does the effective concentration of measure does not occour on a Riemmanian manifold?

Introduction
Let $\mathcal{M}$ be a compact $m$ - dimensional Riemmanian manifold with normalized measure $\mu$ (derived from the metric). It is know that in this setting we have concentration ...

**6**

votes

**1**answer

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

**3**

votes

**0**answers

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

**4**

votes

**3**answers

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

**7**

votes

**2**answers

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

**8**

votes

**2**answers

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