Questions tagged [measure-concentration]
The measure-concentration tag has no usage guidance.
397 questions
3
votes
0
answers
152
views
Bounding expected value of maximum of dot product with random chirp
Let $\mathbf{x}\in\mathbb{C}^n$ with $\|\mathbf{x}\|=1$ with $n<\frac{N}{2}$. I am interested in a bound of the form
\begin{equation*}
\mathbb{E}\Big\{\max_{k\in\{1,2,\ldots,n\}}\Big|\sum_{a=1}^ne^{...
- 859
3
votes
2
answers
394
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$, ...
- 127
5
votes
0
answers
117
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}...
- 859
3
votes
2
answers
589
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 ...
- 773
10
votes
1
answer
2k
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
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$:...
- 4,529
10
votes
3
answers
4k
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
9
votes
1
answer
886
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
3
votes
1
answer
460
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 ...
1
vote
0
answers
274
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 ...
5
votes
1
answer
284
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,\...
- 859
4
votes
1
answer
349
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,...
- 941
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,160
5
votes
2
answers
575
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 \...
- 591
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: ...
- 111
2
votes
1
answer
274
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 ...
- 7,633
1
vote
0
answers
611
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 $v_i\in\mathbb{R}^M,w_i\in\...
- 323
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 ...
- 7,633
5
votes
2
answers
684
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, ...
- 325
2
votes
1
answer
439
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 u(h))\exp(-\frac{\lambda}{2}h^2)~\mathrm{d}h}{\...
- 323
5
votes
1
answer
765
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-...
- 23k
2
votes
2
answers
291
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 $\frac{1}...
- 13.9k
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
2
answers
761
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
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 ...
- 3,425
10
votes
1
answer
846
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,633
4
votes
0
answers
1k
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 ...
- 1,324
6
votes
0
answers
337
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-...
- 7,633
6
votes
2
answers
720
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
3
votes
1
answer
1k
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$. ...
- 298
3
votes
1
answer
1k
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| ...
- 461
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
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
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,791
4
votes
1
answer
503
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 ...
- 461
-1
votes
2
answers
605
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 ...
- 461
0
votes
2
answers
492
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$ ...
- 320
2
votes
2
answers
907
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 u_k=1$...
- 320
10
votes
1
answer
931
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
2
votes
1
answer
635
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 ...
- 201
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
1
vote
0
answers
205
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 ...
- 965
6
votes
1
answer
647
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
5
votes
0
answers
397
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,449
5
votes
3
answers
902
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}^...
- 1,010
9
votes
2
answers
616
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,839
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 \...
- 109k