The measure-concentration tag has no wiki summary.

**0**

votes

**0**answers

37 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

33 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

60 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

91 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

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

**2**

votes

**1**answer

80 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

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

**2**

votes

**1**answer

147 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

115 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

99 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

186 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

228 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

190 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

238 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

176 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

267 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

637 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

257 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

313 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

148 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

294 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

220 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

240 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

349 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

161 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

486 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

435 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

429 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

131 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

224 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

364 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

610 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

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

**5**

votes

**0**answers

196 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

152 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

347 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

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

**3**

votes

**3**answers

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

**6**

votes

**2**answers

356 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

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