All Questions
51 questions
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
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
7
votes
1
answer
466
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
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
7
votes
0
answers
759
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 ...
- 968
6
votes
3
answers
447
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,853
5
votes
3
answers
5k
views
Distribution of the individual coordinates of a uniform random vector on a high-dimensional sphere
Let $X=(X_1,\ldots,X_n)$ be a random vector uniformly distributed on the $n$-dimensional sphere of radius $R > 0$. Intuitively, i think that for large $p$ every coordinate $X_i$ is normally ...
- 6,853
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
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
5
votes
1
answer
225
views
Anti-concentration of Gaussian when conditioning on event
Let $v$ be a given vector with $\|v\|_{\Sigma^{-1}} \leq 1$, where $\Sigma$ is a positive semi-definite matrix and $\|v\|_{\Sigma^{-1}} = \sqrt{v^\top\Sigma v}$. Meanwhile, let $u$ be a random vector ...
- 1,127
5
votes
1
answer
1k
views
Explicit constant for Carbery–Wright inequality
The Carbery–Wright inequality is a seminal result about the anti-concentration of polynomials of Gaussian random variables.
See e.g. Meka, Nguyen, and Vu - Anti-concentration for polynomials of ...
- 111
5
votes
0
answers
711
views
Concentration inequality for max component of a multivariate Gaussian in the general case
I am looking to bound the variance of the maximum component of a vector distributed multivariate Gaussian in the general case where the Gaussian distribution has arbitrary mean and full covariance ...
- 283
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
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
4
votes
2
answers
343
views
Concentration of $k$-th pairwise distance of random points in a unit square
For $1\leq i \leq n$, let $X_i\sim \text{Uniform}(0,1)$, $Y_i \sim \text{Uniform}(0,1)$ be $n$ points chosen uniformly in the unit square. Denote the $k$-th smallest pairwise distances across the $n$ ...
- 662
4
votes
1
answer
229
views
Product of estimates of mean values - Concentration of measure inequality
Let $X_{1},...,X_{d} \in \{-1,1\}^d$ be random variables, with $E[X_j]=\mu_j$. Having $n$ i.i.d. samples $x^{(i)}_1,x^{(i)}_2,....,x^{(i)}_d$, $i=1,...,n $, let $\hat{\mu}_{j}=\frac{1}{n}\sum^{n}_{i=1}...
- 107
4
votes
0
answers
162
views
Concentration Inequality for Score Functions of Exponential Familty
Let $p$ be the density of a continuous one-parameter exponential family distribution on $\mathbb{R}$. We assume that
$$p(x) = c(x)\cdot \exp\bigl [ x \cdot \theta - b(\theta ) \bigr ], $$
where $\...
- 1,127
3
votes
1
answer
178
views
Tail probability of random projection
Suppose $v\in R^n$ is a constant unit vector. $P_l$ is a random projection matrix to an $l$ dimensional subspace of $R^n$ which is uniformly sampled from $G(l,R^n)$ which is the collection of all $l$-...
- 1,495
3
votes
2
answers
731
views
Concentration inequality for sum of iid random variables that involve KL distance
Conider $X \in \mathbb{R}^d$ and $Y \in \{0,1\}$, and a joint distribution $p_{XY}(x,y)$, and a set of $N$ i.i.d. samples $\{(X_i,Y_i)\}_{i=1}^{N}$. Define $p_{X0} = p_{XY}(x,0)$ and $p_{X1} = p_{XY}(...
- 482
3
votes
1
answer
527
views
Wasserstein-type concentration inequalities for empirical measures on polish spaces
Let $(\mathcal{X},d)$ be a Polish (metric) space and let $\{X_n\}_{n=1}^{\infty}$ be a sequence of i.i.d. $\mathcal{X}$-valued random elements defined on a common complete (standard) probability space ...
- 5,405
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
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 ...
3
votes
0
answers
334
views
Tail bound on trace norm / nuclear norm / Schatten-1 norm of Rademacher matrix
Let $0 < r \leq d$ integers. Let $X$, $Y$ be $d \times r$ matrices of independent Rademacher variables, that is, $X,Y \in \mathbb{R}^{d \times r}$ with entries $\pm1$ with probability $1/2$. I am ...
- 223
3
votes
0
answers
186
views
Anti-concentration for sum of t-wise independent uniform variables
Let $X_{1},\ldots,X_{n}$ be i.i.d. random variables, each variable is uniform over the set of integers $\{ 0,\ldots,D-1 \}$. Let $S = \sum_{i=1}^{n}X_{i}$.
By ``small ball probability'', we have that ...
- 225
2
votes
1
answer
847
views
Concentration inequality for quadratic form of Gaussian variables with non-idempotent matrix
Given $y \sim N(0,\sigma^2 I)$, and $M$ that is a symmetric matrix (not necessarily idempotent)
what is the distribution of ${y^T M y}$?
is there a high probability bound on $|{y^T M y}|$?
Most ...
- 123
2
votes
1
answer
302
views
Concentration on discrete probability estimator
Let $t>1$ and $X_1,..., X_t$ a set of real random variables from a discrete distribution, whose pmf is $p(x)$, supported on the points $1,...,k$.
Let $N_t(x) = \sum_{i = 1}^t \mathbb{1}_{X_i =\, x}....
- 245
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 ...
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
1
answer
136
views
Concentration bound for a increasingly weighted sum of bernoulli random variables
Given $x_1,x_2,\ldots,x_n$ i.i.d. bernoulli random variables with $P(x_i=1)=\frac1n$. Given a constant $c=1+\frac{1}{m}, m\geq n$. Is there an explicit theorem that can derive a concentration argument ...
- 25
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
2
votes
0
answers
83
views
Concentration inequalities for sets
Assume that we have a random set $B$ which is constructed by selecting elements from $U = \{ X_1, \dots, X_n \}$ where $X_i$ are independent samples from Gaussians with means $\mu_i$ and variances $\...
- 143
1
vote
1
answer
115
views
How does Chernoff-Hoeffding bound with limited independence reduce to the usual generic CH bound with complete independence
As the title might suggest, I am referring to this paper https://www.cs.umd.edu/~srin/PDF/ch-bounds.pdf , titled : Chernoff-Hoeffding Bounds for Application with Limited Independence.
The theorem in ...
- 121
1
vote
1
answer
137
views
Approximate $\log \mathbb E_P[\exp(th(x)]$ for a function $h$ which is lipschitz and has finite moments of order 1 and 2 w.r.t $P$
Let $P$ be a probability measure on a space $\mathcal X$ and $h: \mathcal X \rightarrow \mathbb R$ is measurable function with finite moments of order 1 and 2. I'm interested in approximating the ...
- 6,853
1
vote
2
answers
111
views
Concentration bound for sum of indicators of maximum value of k combinations
Let $X_1, \dots, X_n$ be i.i.d. random variables distributed as $\mathrm{Exp}(\lambda)$ for some $\lambda > 0$ and let $t > 0$. For every combination $J$ of $k$ of these variables, we define $...
- 143
1
vote
1
answer
3k
views
Tail bound regime for Binomial distribution in concentration paper
In paper 'Concentration Inequalities and Martingale Inequalities:A Survey' gives the following inequality:
My question is whether the inequality holds in regime $\lambda$ being $o(\sqrt n)$ (say $\...
- 1,826
1
vote
1
answer
467
views
Sharp tail bounds for the maximum of an iid sample of a random variable supported on $[0, 1]$
Let $X_1,\ldots,X_n$ be an iid sample from a distribution supported on $[0, 1]$.
Question
What are some sharp concentration inequalities (i.e tail bounds) empirical statistic defined by $Z_n := \max(...
- 6,853
1
vote
1
answer
249
views
On concentration of a sum random variable
Take a random variable defined as
$$r=u_{11}v_{1}v_{1}+u_{12}v_{1}v_{2}+\dots+u_{n,n-1}v_{n}v_{n-1}+u_{nn}v_{n}v_{n}$$ where $v_{i}$ are independent uniform random variables from $\{0,\dots,b\}$, $u_{...
- 13.9k
1
vote
1
answer
308
views
$L_1$ norm concentration of an empirical distribution
Suppose we have one random variable $X$, whose sample space is $\mathbb{X}=\{x_1,x_2,\dots,x_m\}$, and the size of the sample space is $m$. We have $N$ i.i.d. samples from this distribution, and $x_i$ ...
- 23
1
vote
1
answer
118
views
What is the order of the left tail of a mixture of non-central chi-square?
Let $\mu\sim N(0,1)$, $Z\sim N(\mu,1)$. Then $Z$ can be viewed as a mixture of Gaussians. It can also be viewed as a Gaussian but there is a prior for the mean.
Let $X\sim\exp(\lambda)$ where the ...
- 1,495
1
vote
1
answer
122
views
Variance bound of a functional
$X_1,\ldots,X_n$ are i.i.d standard normal random variables.
$a_1,\ldots, a_n$ are constants with $a_i \in [\kappa_1, \kappa_2]$ for all $i$ and $\kappa_1>0$.
$\hat c_n$ is given as the solution ...
1
vote
0
answers
68
views
(Anti-)concentration of gap between largest and second largest component of multivariate random gaussian vector
Let $n$ be a large positive integer and let $Y=(Y_1,\ldots,Y_n)$ be a zero-centered random $n$-dmensional real vector with covariance matrix $\Sigma$, an $n$-by-$n$ positive definite matrix with ...
- 6,853
1
vote
0
answers
376
views
Anti-concentration bounds for folded normal and inverse of gaussian variables
Are there any easy to use bounds on sums of the following kind :
$$
\sum_{i = 1}^{i = N} |a_i| \geq P \\
a_i \sim \mathcal{N}(0, 1) \\
$$
and also for sums of the form :
$$
\sum_{i = 1}^{i = M} \...
- 111
0
votes
1
answer
808
views
Concentration of $\ell_2$ norm of a vector sampled from a distribution
Let $X=(X_1,\ldots,X_n)$, where $X_i \sim P_{p_i}(0,\frac{1}{\lambda})$ are iid, $P_{p_i}$ is sub gaussian distribution for $i^\text{th}$ element, and 0 and $1/\lambda$ are mean and variance.
I'm ...
- 61
0
votes
1
answer
231
views
Concentration inequalities for random sampling without replacement
Let a population $C$ consist of $N$ values $c_1, c_2, \cdots, c_N$, with $c_i\in \{0,1\}$. Let $X_1, X_2, \cdots, X_n$ denote a random sample without replacement from $C$ and let $Y_1, Y_2, \cdots, ...
- 105
0
votes
1
answer
378
views
Concentration of norm of linearly transformed normal random vector as dimension go to infinity
Earlier asked on MSE, but didn't get an answer, so posting here:
Let $X=(X_1 \dots X_n) \in \mathbb{R}^n, X_i\sim N(0,1), iid.$ Let $B: \mathbb{R}^n \to \mathbb{R}^n $ be the diagonal linear map: $...
- 1,467
0
votes
1
answer
967
views
Bound the norm of sum of random vector that generated from standard basis
I have a question like this:
Consider $N$ samples $X_1, X_2, ..., X_N$ that uniformly random generated from standard basis $\{e_i, i=1,2,...,d\}$, i.e. $(1,0,0,\cdots,0),(0,1,0,\cdots,0),(0,0,1,0,\...
- 25
0
votes
1
answer
78
views
Uniform concentration bound (function-valued random variable / continuous stochastic process)
I'm trying to consider a probability space $\Omega$ and
$f(x,\xi):\mathcal{X}\times\Omega\to\mathbb{R}$ (stochastic process over space? or function-valued random variable?), where $\mathcal{X}\subset\...
- 321
0
votes
0
answers
116
views
Concentration bounds for sum of weighted sampling without replacement
Let $X$ be a collection of $2l$ non-negative numbers $X_1,X_2,\ldots,X_{2l}$. We draw $l$ weighted (proportional to values) samples without replacement from $X$. Let $S$ denote this set of $l$ samples....
- 11
0
votes
0
answers
86
views
Expected diameter of a random point set
General problem: For a point set $S\subset X$ in a metric space $(X,d)$, let $\text{diam}(S)=\max_{x,y\in S}d(x,y)$. Given a distribution $P$ on $X$ and $m$ i.i.d. points $x_1,\ldots,x_m\sim P$, what ...
- 19
-1
votes
2
answers
614
views
Bounded difference functions and sub-Gaussian random variables
We have the following standard theorem : Let $X$ be some set and $g : X^n \rightarrow \mathbb{R}$ be a measurable function such that it satisfies the ``bounded difference property" i.e $\exists$ $\{...
- 2,246