Questions tagged [measure-concentration]
The measure-concentration tag has no usage guidance.
381
questions
23
votes
1
answer
1k
views
A Rademacher ‘root 7’ anti-concentration inequality
Let $r_1,r_2,r_3,\dotsc$ be an IID sequence of Rademacher random variables, so that $\mathbb P(r_n=\pm1)=1/2$, and $a_1,a_2,\dotsc$ be a real sequence with $\sum_na_n^2=1$. For $S=\sum_na_nr_n$, does ...
- 16.8k
18
votes
1
answer
1k
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 ...
- 181
17
votes
0
answers
392
views
Talagrand's "Creating convexity" conjecture
We say a subset $A$ of $\mathbb{R}^N$ is balanced if
\begin{equation}
x \in A, \lambda \in [-1,1] \implies \lambda x \in A.
\end{equation}
Given a subset $A$ of $\mathbb{R}^N$, we write
\begin{...
- 445
15
votes
4
answers
2k
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 that ...
- 1,150
14
votes
3
answers
2k
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 ...
- 539
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,761
12
votes
0
answers
443
views
Is this extension of Hoeffding's inequality known?
Question Overview:
Is it already known that, when using Hoeffding's inequality to lower bound the mean of i.i.d. random variables, you can replace the upper bound on the random variables with the ...
- 389
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 \...
- 103k
11
votes
4
answers
2k
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$.
...
11
votes
1
answer
1k
views
Maximal inequality for the average of i.i.d. random variables
Let $Z_i$ be i.i.d. random variables with $\mathbb{E}[Z_i] = 0$ and $\mathbb{E}|Z_i|^p< \infty$ for $p=1,2,3,\cdots$. I am looking for the following type of estimate if possible, and it is not like ...
- 485
10
votes
1
answer
905
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 ...
- 225
10
votes
2
answers
3k
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$$
...
- 223
10
votes
1
answer
1k
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 $\...
- 211
10
votes
2
answers
812
views
Minimum separation among $m$ random points on an $n$-dimensional unit sphere
Consider $m$ points $v_1, \ldots, v_m \in R^{n}$, which are uniformly distributed on the $n$-dimensional unit sphere $S^{n-1} = \{v:\|v\|_2 = 1\}$. Let the minimum separation be
$$
\rho = \min_{i,j\in{...
- 1,117
10
votes
4
answers
637
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 ...
- 363
10
votes
2
answers
417
views
Largest deviations for uniform order statistics
Let $n >0$.
Let $X_1,\ldots,X_n$ be i.i.d. uniform random variable on $[0,1].$ Denote by $X^{(1)}\leq X^{(2)} \leq \cdots \leq X^{(n)}$ their order statistics, and write $\Delta^{(i)} = \vert X^{(...
- 245
10
votes
1
answer
823
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 ...
- 7,573
9
votes
2
answers
4k
views
What is (approximately) the expected value of $X\log{ X}$ where $X$ is binomial (or Poisson)?
Let $X$ follow a binomial distribution with parameters $n$ and $p$. Are there any known bounds for the expected value of $X\log{X}$, for large $n$ and small (but fixed) $p$? A Poisson approximation ...
- 383
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 ...
- 794
9
votes
2
answers
583
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 ...
- 1,829
9
votes
1
answer
331
views
Concentration inequalities for very rare events on a multiplicative scale
Let $E_1, \dots, E_N$ be independent events, each of probability $p$, where $p$ is very close to $0$. Let $A_N = \frac{1}{N} ( 1_{E_1} + \dots + 1_{E_N} )$ be the proportion of the events $E_i$ that ...
- 323
9
votes
1
answer
821
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\...
- 859
9
votes
1
answer
1k
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 ...
- 219
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 ...
- 201
8
votes
1
answer
583
views
Violating the Lebesgue density theorem
Can anyone exhibit a finite-dimensional metric space (preferably, $R^d$) equipped with a measure that does not satisfy the conclusions of the Lebesgue Density Theorem? Such examples exist in infinite-...
- 6,061
8
votes
1
answer
510
views
Concentration bounds for martingales with adaptive Gaussian steps
Consider the following martingale: $X_1 \sim \mathcal{N}(0, 1)$, and for any $n > 1$, $X_n \sim \mathcal{N}(X_{n-1}, X_{n-1}^2)$ (notice, this is a conditional distribution given $X_{n-1}$).
I am ...
- 83
8
votes
3
answers
1k
views
Counterexample of non-negative sequence weakly converging in $\mathscr{M}^1$ but not $L^1$
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 convergence ...
- 2,710
8
votes
2
answers
415
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 $...
- 83
8
votes
2
answers
742
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 ...
user34424
8
votes
2
answers
1k
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 bound:...
- 175
8
votes
0
answers
163
views
Do compact universal covers have concentration of measure phenomenon?
$\DeclareMathOperator\vol{vol}\DeclareMathOperator\diam{diam}$I have a sequence of compact Riemannian manifolds $M_n$ with $\diam (M_n) \to 0$ and finite fundamental groups $\pi_1 (M_n)$ so that their ...
- 686
7
votes
3
answers
387
views
Chernoff-type bounds for a stopped sum of independent random variables
Let $Y_1, \ldots, Y_n$ and $X_1, \ldots, X_n$ be i.i.d. $p$-Bernoulli random variables and let $T \in \{0, \ldots, n\}$ be a stopping time for the process. From Wald's equation, we know
$$
E\left[\...
- 153
7
votes
2
answers
538
views
Large deviation/concentration inequality for submartingale
Let $S_t = M_t + D_t$ be the sum of a martingale $\left(M_t\right)_{t=1,2,\ldots}$ and a predictable process $(D_t)_{t=1,2,\ldots}$ such that the variance of the increments of $M$ is uniformly bounded ...
- 355
7
votes
1
answer
882
views
Prove an anti-concentration inequality for a martingale
My problem can be described easily:
I have a sequence $(X_l)_{l \in \mathbb{N}}$ of r.v. adapted to some filtration $(\mathcal{F}_l)_{l \in \mathbb{N}}$, such that
$\left|X_{l+1}-X_l\right|\le R$ a. ...
- 73
7
votes
1
answer
403
views
Martingale version of Bernstein-type inequality for (slightly) heavy-tailed distributions?
It is known that for sub-exponentially distributed martingale difference sequence, the following Bernstein-type inequality holds:
$$
ℙ\left(\left|
\sum_{i=1}^N a_i X_i
\right| \ge t \right)
\le
2\...
- 719
7
votes
1
answer
360
views
Do i.i.d. sums concentrate any faster than martingales?
Suppose $X_1,X_2, \ldots, X_N \in \mathbb R^d$ are random variables with each $\|X_n\|_2 \le 1/2$ (this choice of the constant simplifies later formulae).
The simplest concentration inequality I know ...
- 1,761
7
votes
1
answer
384
views
Transportation-cost inequality for pushforward measure
Let $X=(X,d_X)$ and $Y=(X,d_Y)$ be metric spaces and $\varphi: X\rightarrow Y$ be an $L$-Lipschitz map, with $0 \le L < \infty$. Suppose $\mu$ is a probability measure on $X$ which satisfies ...
- 6,726
7
votes
2
answers
564
views
Uniform Concentration Bounds on Weighted Sum of i.i.d. Bernoulli Random Variables
Let $\delta_1,...,\delta_n$ be $n$ independent identically distributed Bernoulli random variables with $\mathbb{P}(\delta_1=1)=p$. We consider a set $\Omega = \{\mathbf{a}:=(a_1,...,a_n)~|~a_i\in [0,c/...
- 71
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^...
- 1,771
7
votes
0
answers
697
views
Product of two random Gaussian matrices - orthant probability
Let $X \in \mathbb{R}^{m \times n}$ and $Y \in \mathbb{R}^{n \times k} $ be two independent Gaussian random matrices, i.e., with entries independently sampled from $\mathcal{N}(0,1)$ (a normal ...
- 876
7
votes
1
answer
338
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
627
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{...
- 965
6
votes
1
answer
3k
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 ...
- 1,342
6
votes
1
answer
198
views
Good upper-bound for $\mathbb E[|X-np|^r]$ where $X \sim \text{Binomial}(n,p)$ and $r \ge 1$
Disclaimer. Question moved from SE.
Setup
Let $X \sim \text{Binomial}(p, n)$, and $r \ge 1$.
Question
What is a good upper-bound for $\mathbb E[|X-np|^r]$ ?
Solution for small $r$
If $r=2$, then ...
- 6,726
6
votes
3
answers
417
views
Isoperimetric inequality for $\epsilon$-expansion of a set only along a certain subspace
Let $\gamma_n$ be the standard gaussian distribution on $\mathbb R^n$. Let $V$ be a $k$-dimensional subspace of $\mathbb R^n$. Finally let $A$ be any (nonempty) Borel subset of $A$ with $\gamma_n(A) = ...
- 6,726
6
votes
2
answers
683
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}$ ...
- 293
6
votes
1
answer
401
views
Is there a counterexample to the Thin Shell Conjecture for sub-exponential distributions?
The thin shell conjecture states that there exist universal constants $C,c>0$ such that every logconcave isotropic random vector $X$ in every Euclidean space $\mathbb{R}^n$ satisfies
$$\mathbb{P}\...
- 7,573
6
votes
1
answer
716
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$, ...
- 342
6
votes
0
answers
268
views
Question about size-biased couplings and concentration of the number of collisions
Edit/Update: I was indeed missing something quite obvious. I assumed the notion of collision used was the one I am used to (number of pairwise collisions, so if a bin received $k$ balls then this ...
- 1,342
6
votes
0
answers
527
views
a variation on Hanson-Wright inequality
The classic Hanson-Wright inequality states that for a Gaussian random vector $\mathbf{x}\in\mathbb{R}^n$ distributed as $\mathcal{N}(\mathbf{0},\mathbf{I})$ and $\mathbf{A}\in\mathbb{R}^{n\times n}$ ...
- 859