Questions tagged [measure-concentration]
The measure-concentration tag has no usage guidance.
146 questions with no upvoted or accepted answers
19
votes
0
answers
553
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{...
- 484
12
votes
0
answers
491
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
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
0
answers
168
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
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
0
answers
273
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,372
6
votes
0
answers
554
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
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
5
votes
0
answers
266
views
Concentration inequalities for random measures
For random variables $X_1,\dots,X_n$ with common mean $\mathbb{E}[X_i]=\mu$ and common bounds $a\leq X_i\leq b$, we have the very useful Hoeffding's inequality:
$$\mathbb{P}\left(\left|\mu -\frac1n\...
- 101
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
712
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
5
votes
0
answers
1k
views
Asymptotic behavior of row sums in 2-d array of random variables
Set-up. Let $f : \mathbb{N} \to \mathbb{N}$ be increasing. For each $m \in [0,1]$, consider an infinite two-dimensional array of random variables, where row $n$ has $f(n)$ variables:
$B^m_{1,1}$ $B^...
- 61
5
votes
0
answers
543
views
Vector martingale concentration
Let $\varepsilon_1, \dots, \varepsilon_N$ be a martingale difference sequence in $R^d$ with $\|\varepsilon_n\| \le B_n, a.s.$ for each $n=1,\dots,N$. Do we have some Azuma-type concentration ...
- 719
5
votes
0
answers
143
views
Is there a concentration inequality depending on dimension for a symmetric function on product space?
I recently read an elegant paper of Bobkov
Bobkov, S.G., On concentration of measure on the cube, J. Math. Sci., New York 165, No. 1, 60-70 (2010); translation from Probl. Mat. Anal. 44, 55-64 (2010)....
- 747
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
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
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
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
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
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
4
votes
0
answers
107
views
Upper bound $\tau_C := \int_{\|x\| \le 1}(vol(C \cap (x + C))/vol(C))dx$ for a convex body $C \subseteq \mathbb R^n$, by reducing to a ball
Let $C$ be a convex body in $\mathbb R^n$, i.e a bounded convex subset of $\mathbb R^n$ which has nonempty interior, and which is (A) open, or (B) closed (I'm not sure one makes more sense; choose the ...
- 6,853
4
votes
0
answers
642
views
Comparison of concentrations of different $L^p$-norms of (sub) Gaussian distributions
It's well-known that the Euclidean $2$-norm of subgaussian random vectors concentrates in high dimensions, e.g. when $X \sim \mathcal{N}(0,I_n),$ (or in general $X$ is subgaussian with independent co-...
- 1,467
4
votes
0
answers
143
views
For a martingale $f_0,f_1,\ldots $ how can we bound $P(\frac{1}{n} \|f_n\| \le 1$ for all $ n \ge N)$?
Suppose $f_0,f_1, \ldots$ is a martingale (or i.i.d sequence) in $\mathbb R^d$ with $f_0=0$ and all $\|f_n - f_{n-1}\| \le L$ say. There are many concentration results for the initial segment of the ...
- 1,955
4
votes
0
answers
183
views
Regularity of optimal transport of Gaussian mixtures
In one of the problems that I am working on, I came across the topic of smoothness of optimal transport for Gaussian mixtures. In particular, let $P=P_\theta=\sum_{i=1}^k \frac{1}{k}\mathcal{N}(x| \...
- 161
4
votes
0
answers
116
views
$\ell_p$ geodesic distance on smooth Riemannian manifold and Logarithmic Sobolev Inequalities
Bear with me, I'm not a professional geometer. Recently, I've been studying Logarithmic Sobolev Inequalities (LSI) for probability distributions on manifolds (e.g as done in works of Bobkvo et al. ...
- 6,853
4
votes
0
answers
162
views
Are sums extremal for subgaussian concentration?
Bobkov and Houdre https://projecteuclid.org/euclid.bj/1178291721
showed that among all $f:R^n\to R$ that are $1$-Lipschitz
with respect to the $\ell_1$ metric,
the variance is maximized by sums. ...
- 6,541
4
votes
0
answers
93
views
On symmetry and measure concentration rate for convex bodies
The concentration of measure on the cube $ [0, 1]^n $ equipped with uniform probability measure $\mu_{\infty}$,
states that for any $A \subset [0, 1]^n $ with $ \mu_{\infty}(A) \geq \frac{1}{2} $,
we ...
- 365
4
votes
0
answers
141
views
Is there an example that both Berry-Essen bound and DKW bound are attained?
The Berry-Essen bound stated that
$$\sup _{{x\in {\mathbb R}}}\left|\widehat{F_{n}(x)}-\Phi (x)\right|\leq C_{0}\cdot \psi _{0}$$
where $\psi _{0}(n)={\Big (}{\textstyle \sum \limits _{{i=1}}^{n}\...
- 8,071
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
4
votes
0
answers
76
views
How well does an estimator perform on another dataset?
Suppose $X \sim N(0, \Sigma)$ is a $d$-dimensional Gaussian random vector. And we have $2n$ $i.i.d$ sample $X_1, \ldots, X_{n}, \ldots, X_{2n}$.
Let $\hat{\Sigma}_1 = \frac{1}{n}\sum_{i=1}^nX_i X_i^\...
- 515
4
votes
0
answers
418
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
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
3
votes
0
answers
93
views
Tighter Freedman's inequality for a special martingale difference sequence
Let $X_{1}, \ldots, X_{T} \in \{0, 1\}$ be a sequence of Boolean random variables with
$$
\mathbb{E}[X_{t} | X_{1}, \dots, X_{t - 1}] = p_{t}.
$$
Consider the sequence $Y_{t} := X_{t} - p_{t}$ (which ...
- 41
3
votes
0
answers
130
views
A Talagrand inequality for the supremum of partial sums over function classes under dependence. (Reference request)
As a consequence to the Talagrand concentration inequality, it is well known that for a measurable space $(S,\mathcal{S})$ and an i.i.d. sample $X_1,...,X_n$ of $S$-valued random variables, if $\...
- 141
3
votes
0
answers
70
views
Concentration for Hamming balls
It is well known that Lipschitz functions on the Boolean $n$-cube endowed with the Hamming metric satisfy concentration properties. Specifically, most of their values lie in a range of width $O(\sqrt ...
- 2,772
3
votes
0
answers
335
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
93
views
Explaning why the spectrum of a setting simple structure random matrix is always spiked ($d-1$ eigenvalues close to zero, and $1$ away from zero)
For concreteness, let $m=500$, $d=600$, $N=1000$. Let $W$ be and $d \times m$ matrix with unit-norm rows and let $u$ be a uni-norm vector of length $m$. Given a binary vector $b$ of length $m$, length ...
- 6,853
3
votes
1
answer
374
views
Concentration of very dependent Markov chains
Consider the following simple Markov chain $ X_1\to X_2\to\cdots\to X_n $ where each $X_i$ is $\{-1,1\}$-valued and $X_1\sim\mathrm{Unif}(\{-1,1\})$ (such that the chain is stationary).
The flip ...
- 161
3
votes
0
answers
83
views
Ornstein-Ulhenbeck like semigroup for the orthogonal group with a hypercontractive inequality
I am looking for an Ornstein-Uhlenbeck like semigroup $P_t$ and associated generator $\mathcal{L}$ on $G = \operatorname{SO}(n)$ or $\operatorname{O}(n)$ that has a hypercontractive inequality with a ...
- 941
3
votes
0
answers
226
views
Eigenvalues of Hadamard product of two Wishart-type matrices
Given two independent Gaussian matrices with i.i.d. entries: $A\in\mathbb{R}^{n\times p}$ and $B\in\mathbb{R}^{n\times q}$, where and $A_{i,j},B_{i,j}\sim\mathcal{N}(0,1)$. Assume that $\max(p,q)<n....
- 31
3
votes
1
answer
379
views
Concentration inequality for norm of solution to nonlinear least-squares problem
Define the piecewise-linear function $\psi(t):=\max(t,0)$ for all $t \in \mathbb R$.
Let $d,n,k \to \infty$ at the same rate (i.e $n \asymp k \asymp d$).
Let $y_1,\ldots,y_n \in \{-1,1\}$ uniformly ...
- 6,853
3
votes
0
answers
103
views
Concentration inequalities for gradient flows induced by random fields
Let $G=(G(x))_{x \in \mathbb R^m}$ be a conservative random field with values in $\mathbb R^m$, for large positive integer $m$. That is, there exists a scalar random field $g=(g(x))_{x \in \mathbb R^m}...
- 6,853
3
votes
0
answers
307
views
Upper-bound for eigenvalues of $E [UU^T]$, where $U$ is uniformly distributed on the unit $n$-sphere
Let $X$ be a $\sigma$-subGaussian random vector on $\mathbb R^n$ (for large $n \ge 3$), meaning that the random variable $X^Tv$ is $\sigma$-subGaussian for every unit vector $v \in \mathbb R^n$. ...
- 6,853
3
votes
0
answers
187
views
Concentration Inequalities for the Exponential of Weighted Bernoulli Sums
I want a concentration inequality for the exponential of a weighted sum of independent Bernoulli random variables around its mean, for one of my research works. I was wondering if there is a well ...
- 123
3
votes
0
answers
159
views
Does there exist a compactly supported integrable function with infinite Coulomb energy?
The title of the question pretty much says it all. I am looking for a function $f\in L^1(\Omega)$, where $\Omega \subset \mathbb{R}^3$ is a bounded domain, such that
$$
E[f] = \iint\limits_{\Omega\...
- 401
3
votes
0
answers
166
views
Matrix Chernoff sampling with out replacement
I am interested to know if the matrix Chernoff bound (see Theorem 5.1.1 in https://arxiv.org/pdf/1501.01571.pdf) holds if one samples without replacement.
For example, the Bernstein inequality is ...
- 221
3
votes
0
answers
77
views
A concentration problem of product of matrices
Let $A$ be an $n \times m$ matrix with non-negative entries and $B \in \mathbb{R^{n\times n}_{\geq 0}}, C \in \mathbb{R^{m\times m}_{\geq 0}}$ be random matrices where B and C are both symmetric and ...
- 195
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
3
votes
0
answers
125
views
Concentration of sums of random matrices around the mean, in the Loewner order
Recently, I have found myself interested in concentration properties of random matrices.
Specifically I would like to answer questions of the following sort
Let $\{X_i\}_{i=1}^n$ be i.i.d. copies ...
- 393
3
votes
0
answers
372
views
On the precise concentration of permanent of $\pm1$ matrices
Obtain $M\in\{-1,+1\}^{n\times n}$ by unbiased coin flipping.
What is known about the distribution of permanent $\mathsf{Perm}(M)$? It seems to be bimodal.
Given a function $g(n)$ what is the ...
user94040