Questions tagged [measure-concentration]

The tag has no usage guidance.

119 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
12
votes
0answers
376 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 ...
9
votes
0answers
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 ...
8
votes
0answers
141 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 ...
7
votes
0answers
612 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 ...
6
votes
0answers
254 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 ...
6
votes
0answers
484 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}$ ...
6
votes
0answers
315 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-...
5
votes
0answers
225 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 ...
5
votes
0answers
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^...
5
votes
0answers
370 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 ...
5
votes
0answers
100 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)....
5
votes
0answers
150 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$...
5
votes
0answers
131 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 ...
5
votes
0answers
277 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 ...
5
votes
0answers
130 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}[...
5
votes
0answers
111 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}...
5
votes
0answers
303 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)$...
4
votes
1answer
129 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$ ...
4
votes
0answers
93 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 ...
4
votes
0answers
122 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 ...
4
votes
0answers
110 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. ...
4
votes
0answers
81 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 ...
4
votes
0answers
99 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}\...
4
votes
0answers
118 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 $\...
4
votes
0answers
73 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^\...
4
votes
0answers
287 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{...
4
votes
0answers
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 ...
3
votes
0answers
67 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 ...
3
votes
0answers
89 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....
3
votes
0answers
230 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$. ...
3
votes
0answers
113 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 ...
3
votes
0answers
127 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\...
3
votes
0answers
118 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| \...
3
votes
0answers
117 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 ...
3
votes
0answers
152 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. ...
3
votes
0answers
71 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 ...
3
votes
0answers
90 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 ...
3
votes
0answers
321 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 ...
3
votes
0answers
332 views

concentration bounds on weighted multinomial sum

Consider i.i.d random vectors $Y_{1},..,Y_{n}$ and they are chosen uniformly at random from $\{e_{1},..,e_{L}\}$ where $e_{i}$ is a $L\times 1$ vector with $i$th component be 1 and the others be 0. ...
3
votes
0answers
157 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-...
3
votes
0answers
229 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 ...
3
votes
0answers
256 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 ...
3
votes
0answers
132 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^{...
2
votes
1answer
88 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 ...
2
votes
0answers
40 views

Spectral approximation of $(XX^\top/d)\circ(X\Sigma_dX^\top/d)$ where $X$ is an $n \times d$ random matrix with iid rows from $N(0,\Sigma_d)$

Let $X \in \mathbb R^{n \times d}$ be a random matrix with iid rows from $N(0,\Sigma_d)$ where $\Sigma_d$ is a $d \times d$ psd matrix verifying w.h.p, $\mbox{trace}(\Sigma_d/d)= 1$. $\|\Sigma_d\|_{...
2
votes
0answers
51 views

Asymptotic lower and upper bounds for the eigenvalues of hadamard product $W \circ W$, where $W$ is a large Wishart matrix

Let $n$ and $d$ be large positive integers with $n,d \to \infty$ such that $n/d \to \gamma \in (0,\infty)$. Let $X$ be a random $n \times d$ random matrix with iid copies of log-concave isotropic ...
2
votes
0answers
72 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 $\...
2
votes
1answer
170 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 ...
2
votes
0answers
54 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}...
2
votes
0answers
66 views

Approximate any point of the interval $[-1/2,1/2]$ by the sum of $n$ iid uniform random variables from $[-1,1]$

Let $x \in [-1/2,1/2]$ and $X_1,\ldots,X_n$ be drawn iid from the uniform distribution on $[-1,1]$. Question. Given $\varepsilon \ge 0$ an integer $k \in [1,n]$, what is a good lower-bound on the ...