All Questions
Tagged with pr.probability measure-concentration
324 questions
5
votes
1
answer
331
views
Matrix concentration bound
Suppose we have $N$ constant matrices $A_i \in R^{m\times m}, 1\leq i \leq N$. Consider $N$ random rotation-matrices $R_i \in SO(m), 1\leq i \leq N$. Is it possible to obtain a concentration bound on
$...
- 51
12
votes
0
answers
489
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 ...
- 399
4
votes
1
answer
502
views
Hoeffding's inequality for sums of pairs of random variables
Let $X_1,\dotsc, X_n$ be $n$ i.i.d. random variables where $X_1 \in [a,b]$. Similarly, let $Y_1,\dotsc,Y_m$ be $m$ i.i.d. random variables where $Y_1 \in [c,d]$. Furthermore, $X_i$ and $Y_j$ are ...
- 399
10
votes
2
answers
847
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,127
4
votes
1
answer
347
views
Concentration of functional of Gaussian random variable
Suppose I have two Gaussian distributions
$p(x) = \frac{1}{(2\pi)^{d/2}|\Sigma_p|^{1/2}}\exp(-\frac{1}{2}x^\top \Sigma_p^{-1} x)$ and $q(x) = \frac{1}{(2\pi)^{d/2}|\Sigma_q|^{1/2}}\exp(-\frac{1}{2}x^\...
- 515
2
votes
1
answer
271
views
How to compute bounding coefficients for McDiarmid's inequality?
I am trying to understand the proof in Sec. A2 of Gretton et al.. To make the question self-contained, I summarize below the key ingredients. At the end of the post, I state my question.
Given a ...
7
votes
2
answers
606
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
4
votes
1
answer
681
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 ...
- 515
2
votes
1
answer
172
views
Symmetry of concentration bounds on mean
Question summary:
If I have a two-sided bound, can I immediately get a one-sided bound with tighter constants?
Question details:
Let $\mathbf X = X_1,...,X_n$ be $n$ i.i.d. real-valued random ...
- 399
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,372
4
votes
0
answers
416
views
concentration of functions of Gaussian processes
Let $\mathcal{C}\in\mathbb{R}^n$ be a subset of the unit ball. Also let $\mathbf{a}_1,\mathbf{a}_2,\ldots,\mathbf{a}_m\in\mathbb{R}^n$ be i.i.d. random Gaussian vectors $\mathcal{N}(\mathbf{0},\mathbf{...
- 859
5
votes
2
answers
565
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,...
- 1,731
10
votes
4
answers
645
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
4
votes
1
answer
286
views
Upper tail concentration of sample covariance matrices
I'm interested in concentration of the following random matrix sum in spectral norm
$\frac{1}{m}\sum_{k=1}^m b_k^2\mathbf{a}_k\mathbf{a}_k^*$
Here $\mathbf{a}_k\in\mathbb{R}^n$ are i.i.d. standard ...
- 363
3
votes
0
answers
193
views
Concentration of the quotient of random variables
Let $X_1, X_2, \cdots, X_n$ be n i.i.d. standard Gaussian random variables. It is clear that we can describe the concentration of $\sum_{i=1}^n \alpha_i X_i$, and $\sum_{i=1}^n \alpha_i X_i^2$ (sub-...
- 31
8
votes
2
answers
486
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
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
4
votes
1
answer
355
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....
- 53
2
votes
1
answer
886
views
Asymptotic behavior of a ratio of sums of iid random variables
Let $X_i$ and $Y_i$ be distributed identically to $X$ and $Y$, respectively. Assume both $X$ and $Y$ take strictly positive values.
Consider the random variable $R_n \doteq \frac{\sum_{i=1}^n X_i}{\...
- 143
2
votes
0
answers
124
views
Intuitive (?) inequality extremal inequality
Consider $N$ pairs of random variables $(X_i, Y_i)$. $X_i$ are iid, with $EX_i=0$ and $EX_i^2=1$. The same conditions hold for $Y_i$. Moreover all $X_i$ are independent of all $Y_j$. It seems very ...
- 461
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
5
votes
0
answers
169
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$...
- 461
2
votes
0
answers
366
views
Convergence rate of Pearson correlation matrix
I am interested in (rather sharp if not the finest) tail/concentration bounds for the Pearson correlation matrix: let $X_1,\ldots,X_N \sim \mathcal{N}(0,1)$ be correlated random variables; let $\rho(...
- 121
3
votes
0
answers
268
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 ...
user76479
1
vote
0
answers
360
views
concentration inequalities for quadratic forms of correlated random vectors
Let $\mathbf{n}$ is a Gaussian random vector with mean $\mathbf{0}$ and co-variance matrix $\mathbf{H}$. Let $\mathbf{r} = Sign(\mathbf{n})$, where $Sign(n_i) = 1$ if $n_i>0$ and $Sign(n_i) = -1$ ...
- 39
4
votes
3
answers
345
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,529
2
votes
0
answers
246
views
Tail bounds for suprema of random processes
Classical results concerning concentration of Gaussian random variables due to Cirelson, Ibragimov and Sudakov say that if $V_1,\cdots,V_n$ are jointly Gaussian with variance bounded by $1$, then (...
- 599
3
votes
1
answer
339
views
Probability of Hamming weight
Given $s,t\in(0,1)$, $c>1$, $n\in\Bbb N$, pick ${n^t}$ random vectors $\{v_i\}_{i=1}^{{n^t}}$ such that each $v_i\in\{x\in\{0,1\}^{2^n}:|x|_{hamming}={2^{n-n^s}}\}$.
Denote $v_j\cap v_j$ to be ...
- 13.9k
5
votes
0
answers
138
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 ...
- 121
3
votes
0
answers
270
views
Hamming weight probability of projections
Given $s,t\in(0,1)$, $c>1$, $n\in\Bbb N$, pick $2^{n^t}$ random vectors $\{v_i\}_{i=1}^{2^{n^t}}$ such that each $v_i\in\{x\in\{0,1\}^{2^n}:|x|_{hamming}={2^{n-n^s}}\}$.
If $v_i^\perp$ is ...
- 13.9k
3
votes
1
answer
247
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, ...
- 205
2
votes
0
answers
386
views
What is the concentration of measure for Gaussian random variables which are independent, but are transformed?
This might be a too easy question for Mathoverflow, but Googling led to similar questions and answers here (though not the one I was looking for).
The question is split into two:
I have a matrix $X \...
- 131
2
votes
0
answers
145
views
Concentration bound in high min entropy distribution
Let $(X_{1},\dots,X_{m})$ be joint distribution on $\{0,1\}^{m}$ with that $H_{\infty}(X_{1},\cdots,X_{m})\geq m-r$, where $H_{\infty}$ means min-entropy.
Let $P_{1},...,P_{n}\subseteq [m]$ be sets ...
- 57
5
votes
0
answers
327
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 ...
- 161
1
vote
1
answer
239
views
Concentration bound for a martingale-like setting (the expected difference decreases as the sequence increases)
I went through several martingales concentration bounds, but none of them fit the settings I am interested in, which is the following. Suppose I have a sequence of nonnegative random variables $0=Y_{0}...
- 225
0
votes
1
answer
196
views
reverse FKG type inequality for slightly correlated Gaussian vectors
Let $X$ be a $m$-dimensional Gaussian vector, and $Y$ a $q$-dimensional Gaussian vector, for some $m,q\geq 1$. Assume that the $X_i$ and $Y_j$ are centred and have unit variance. Assume that $E X_i ...
- 1,352
3
votes
3
answers
5k
views
Hoeffding's inequality for vector valued random variables
Is there a version of Hoeffding's inequality for vector valued random variables?
This seems to be hard to find and I wonder why. I suppose it is difficult to show Hoeffding's lemma, since the proof ...
- 619
5
votes
0
answers
137
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}[...
- 619
5
votes
1
answer
705
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)...
- 123
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 ...
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
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