Questions tagged [measure-concentration]
The measure-concentration tag has no usage guidance.
146 questions with no upvoted or accepted answers
3
votes
0
answers
451
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. ...
- 31
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
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
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
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
2
votes
0
answers
94
views
Concentration inequalities for functions of random binary strings
Let $(X_1,\ldots,X_n)$ be a vector in $\{0,1\}^n$ drawn uniformly at random among all vectors with exactly $k$ $1'$s. I am interested in inequalities for tail probabilities for the random variables $X,...
- 2,288
2
votes
0
answers
84
views
Concentration result for self-normalized empirical process
In Theorem 1.1 of this paper by Bercu, Gassiat and Rio, a concentration result is derived for the 'self-normalized' empirical process. Specifically, suppose that $(X,X_n)_{n \ge 1}$ is a sequence of i....
- 206
2
votes
0
answers
70
views
A lemma in the application of Lions's concentration compactness pricnciple in Hardy-Littlewood-Sobolev inequality
I'm encountering some problems when reading Lions' paper "the concentration-compactness principle in the calculus of variations. The limit case, Part 2".
The Hardy-Littlewood-Sobolev (HLS) ...
- 121
2
votes
1
answer
329
views
Matrix Bernstein's inequality: from tail probability to expectation
Let $X_i$ be independent, mean zero, $n\times n$, symmetric random matrices. $\|X_i\|\leq K$ almost sure for $\forall I$.
We have matrix Bernstein's inequality for the tail probability as follows
$$\...
- 49
2
votes
0
answers
131
views
Large deviation principle for product of iid bounded symmetric random variables
Let $n$ and $k$ be positive integers. Let $X$ be the empirical mean of $n$ iid Rademacher random variables. Note that the distribution of $X$ is symmetric about 0, and also $|X| \le 1$ w.p 1. Let $X_1,...
- 6,853
2
votes
0
answers
166
views
Convex ordering of measures that are obtained by different push-forwards of a same measure
Suppose that we have a probability measure $\rho$ which is supported on $\mathbb{R}^d$ and absolutely continuous w.r.t. the Lebesgue measure. Take two vector fields $F, G : \mathbb{R}^d \rightarrow \...
- 21
2
votes
0
answers
202
views
Prove or disprove that $u=0$ a.e. on $\Bbb R^d$
Let $\Omega\subset\Bbb R^d$ be an open set. Let $k:\Bbb R^d\to [0,\infty)$ be measurable such that $0\in \operatorname{supp}k$. This implies that $\Omega\subset \Omega_k=\Omega+\operatorname{supp}k$. ...
- 1,101
2
votes
0
answers
184
views
Sudakov's lower bound type inequality for supremum of Chi-squared random variables
Let $\varepsilon$ be $n$-dimensional standard Gaussian veector, i.e., $\varepsilon \sim N_n(0, I_n)$. Let $\mathcal{P}$ be a subset of symmetric projection matrices in $\mathbb{R}^{n \times n}$ with $|...
- 399
2
votes
0
answers
131
views
Eigenvalues of Witten Laplacian induced by log-concave probability measure on manifold
Let $M$ be a closed $n$-dimensional Riemannian manifold and let $\mu=e^{-V}d\mathrm{vol}_M$ be a log-concave probability measure on $M$, such that the pair $(M,\mu)$ verifies the so-called Bakry-Emery ...
- 6,853
2
votes
0
answers
132
views
Concentration of sample covariance for dependent data
Let $X_1, \ldots, X_T$ are sub-Gaussian random vectors in $\mathbb{R}^d$ coming from a common distribution with population covariance $\Sigma$. If they are independent, it is known that the sample ...
- 399
2
votes
0
answers
51
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\|_{...
- 6,853
2
votes
0
answers
172
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 ...
- 6,853
2
votes
1
answer
416
views
High-probability lower bound for norm of least squares solution when both design matrix $X$ and response vector $y$ are random (and independent)
Let $n,d \to \infty$ with $n/d \to \gamma \in (0,\infty)$. Let $X$ be a random $n \times d$ matrix independent rows uniformly distributed on the the unit-sphere in $\mathbb R^d$ and let $y$ be a ...
- 6,853
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
2
votes
0
answers
68
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 ...
- 6,853
2
votes
0
answers
58
views
An upper bound on $\mathbb{E}\bigg[\bigg(\sum_{i=1}^{k}(X^{\top}A_{i}X)^{2}\bigg)^{q}\bigg]$
Let $X\in\mathbb{R}^{d}$ have independent, mean zero subgaussian entries, and $A_{1},\ldots,A_{k}$ be fixed $d\times d$ matrices that have zeros on the diagonal. I would like to upper bound the ...
- 129
2
votes
0
answers
222
views
Concentration inequalities for beta random variables
Let $X$ be a random variable having a beta distribution $$f(x)=\frac{\Gamma(\alpha)\Gamma(\beta)}{\Gamma(\alpha+\beta)}x^{\alpha-1}(1-x)^{\beta-1}$$with mean $\mu=\frac{\alpha}{\alpha+\beta}$, and ...
- 21
2
votes
0
answers
92
views
Lower bound to $\epsilon$-expansion of a subset of a half-sphere
Below are two known lemmas on a $d$-dimensional sphere (related to the isoperimetric inequality). I would like to know: does a similar statement like this holds for a $d$-dimensional dome also (i.e. ...
- 21
2
votes
0
answers
323
views
McDiarmid's Inequality bounding deviation with multiplicative error?
Fix $m$ arbitrary values $x_1, x_2, ..., x_m$ in $[0,1]$, and an integer $n$. Obtain $n$-set $S$ by drawing $n \le m$ times randomly without replacement from $\{1,2,..,m\}$. Define r.v. $X = \sum_{i ...
- 183
2
votes
0
answers
60
views
Mean width of intersection of two elipsoid
My question is regarding mean widths. For a set $\mathcal{T}$ define the mean width
\begin{align*}
\omega(T)=\mathbb{E}_{\mathbf{g}\sim\mathcal{N}(0,\mathbf{I})}\bigg[\underset{\mathbf{u}\in\mathcal{...
- 363
2
votes
0
answers
140
views
Matrices with i.i.d. Heavy tail Columns
I'm wondering if there are any known results about minimum eigenvalue of matrices with i.i.d. heavy tailed columns. In particular, Theorem 5.62 of Roman Vershynin's notes (http://www-personal.umich....
- 859
2
votes
0
answers
64
views
tail bounds for sum of n iid variables divided by power of n
Let $X_i, 1\leq i\leq n$ be i.i.d. random variables with finite moments. Then $Y_n :=\frac{1}{n^{1+\delta}}\sum_{i=1}^nX_i$ goes to 0 almost surely for any $\delta >0$. What are some good non-...
- 121
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
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
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
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
1
vote
0
answers
42
views
Sub-Gaussian analysis via bounded decomposition?
Let $\psi_\alpha(x) := \exp(x^\alpha)-1$.
The Sub-Gaussian Norm $\lVert X \rVert_{\psi_2}$ of a random variable $X$ is defined as
$$
\lVert X\rVert_{\psi_2} = \inf\{c>0\mid \mathbb{E}[\varphi_2(|X|/...
- 2,183
1
vote
0
answers
72
views
Do almost all Gibbs' measures satisfy the weak-Poincare Inequality?
I am trying to interprete the discussion given in Section 3 of this paper,
https://core.ac.uk/download/pdf/82217936.pdf
Lets suppose we restrict to considering Gibbs's measures of the form $\sim e^{-...
- 617
1
vote
0
answers
70
views
Thermal equilibrium between solid (anharmonic lattice) and ideal gas: justification via statistical mechanics
I would greatly appreciate any reference that solves the following problem (or a variant of it). If you know it is open, please say so.
Motivation: Suppose you have a solid (say a block of steel) ...
- 312
1
vote
0
answers
34
views
Discrepancy between probability measures, tested against bounded functions of bounded variance
When studying some concentration inequalities, it became relevant to consider the following discrepancy between two probability measures $\pi$ and $\nu$ (treating $\sigma \in \left( 0, \frac{1}{2} \...
- 801
1
vote
0
answers
57
views
Limiting value of expectation of trace of truncated Gram matrix
Let $n$ and $d$ be large positive integers such that $d/n = a \in (0,1)$, fixed. Let $x_1,\ldots,x_n$ be iid random vectors from $N(0,I_d)$. Fix $b \in (0,1]$ and a unit-vector $v \in \mathbb R^d$, ...
- 6,853
1
vote
0
answers
131
views
Large-deviation inequalities for a class of simple random multivariate polynomials
Let $N$ be a large positive integer and let $[N] := \{1,2,\ldots,N\}$. For any $k$, let $K_{N,k}$ denote the collection of $k$-element subsets of $[N]$. Let $x=(x_1,\ldots,x_N)$ be a uniformly random ...
- 6,853
1
vote
1
answer
288
views
Rate of convergence to uniform distribution
Let $p=(p(1),\ldots,p(N))$ be a discrete distribution on $[N]:=\{1,2,\ldots,N\}$ with full support (i.e all the $p(i)$'s are strictly positive and sum to $1$). Let $i_1,i_2,\ldots,i_T$ be an iid ...
- 6,853
1
vote
0
answers
121
views
Composing an Orlicz norm related to Bernstein's inequality?
This is related to my previous question, but is hopefully more precise.
I would like to reason about tail-bounds for polynomial products of concentrated random variables in $R:=\mathbb{R}[x]/(x^n-1)$.
...
- 2,183
1
vote
1
answer
524
views
Optimal transport between two matrices
I'm investigating the use of optimal transport to define a distance between non-negative matrices that satisfy the condition $\mathbf e^\top\mathbf M\mathbf e = 1$ (i.e., the sum of all elements in ...
- 243
1
vote
0
answers
129
views
Concentration of a combinatorial sum
Let $X=(x_1,\ldots,x_p)$ be an $p \times n$ random matrix with iid entries from $\{\pm 1\}$, distributed so that $\mathbb P(x_{ij} = 1) \equiv 1/2$, where $x_i=(x_{i1},\ldots,x_{in})$. Let $y$ be a ...
- 6,853
1
vote
1
answer
153
views
Minimax estimation rate of sparse vector $w_\star$, w.r.t to mixed norm $\|\hat w_n-w_\star\| := \|\hat w_n - w_\star\|_2 + \|\hat w_n-w_\star\|_q$
Let $n,d,s$ be positive integers with $s \le d$, and let $B_0(d,s)$ be the set of all (real) $d$-dimensional vectors with at most $s$ nonzero components. Given an $n \times d$ matrix $X$ with rows $...
- 6,853
1
vote
0
answers
371
views
Lower bound on the sum of the product of random variables
Let $X_i$ be the $i$-th element of the vector $X=(X_1, ..., X_m)$ of i.i.d. random variables.
I am looking for a lower bound for the expression
$\mathbb{P}((\sum^n_{i=1}\prod^{m_i}_{j=1}(X_j))^2 \geq ...
- 129
1
vote
1
answer
230
views
VC dimension of a certain derived class of binary functions
Let $X$ be a measurable space and let $P$ be a probability distribution on $X \times \{\pm 1\}$. Let $F$ be a function class on $X$, i.e., a collection of (measurable) functions from $X$ to $\mathbb R$...
- 6,853
1
vote
0
answers
143
views
$\newcommand\v{\operatorname{vol}_d(C}$Compact subsets of $ℝ^d$ which maximize $\inf_{|v|\le1}\dfrac{\v\cap(𝜀v+C))}{\v)}$ for fixed $\v)$ and $𝜀>0$
Let $\operatorname{vol}_d$ be the volume measure on $\mathbb R^d$ and let $B_d$ be the unit-ball. For $\varepsilon \ge 0$ and a compact subset $C$ of $\mathbb R^d$ with $\operatorname{vol}_d(C)>0$, ...
- 6,853
1
vote
1
answer
160
views
Given iid $w_1,\dotsc,w_N \sim N(0,1/d)$ iid, find a simple matrix $A$ s.t $\|aa^T-A\|_\text{op}\to0$, where $a_i := E_{G \sim N(0,1)}[f(\|w_i\| G)]$
Let $d$ and $N$ be two large comparable integers, for example assume
$$
N,d \to \infty, \quad d/N \to \gamma \in (0,\infty).
$$
Let $w_1,\dotsc,w_N$ be iid from $N(0,(1/d)I_d)$ and let $f:\mathbb R \...
- 6,853
1
vote
0
answers
351
views
Tail bounds for random Gaussian chaos?
Let $g = (g_1, \dots, g_d)$ be a sequence of independent standard Normal random variables, and suppose $\Sigma$ is a $d \times d$ (deterministic), real, symmetric, positive definite matrix. The Hanson-...
- 380
1
vote
1
answer
415
views
Approximate the singular values of a certain random dot-product kernel matrix (in the sense of El Karoui, Cheng-Singer, etc.)
Let $g:\mathbb R \to \mathbb R $ be a continuous function which is
"sufficiently smooth" (e.g $\mathcal C^3$) around $0$, and
"sufficiently integrable" (e.g integrable w.r.t $N(0,...
- 6,853
1
vote
0
answers
57
views
Concentration inequality for matrix martingale with dynamic upper bounds
Consider a sequence of stochastic PSD matrices $X_1, X_2, \dots, X_n \in \mathbb{R}^{d\times d}$. Let $\mathcal{F}_k = \sigma(X_1, X_2, \dots, X_{k-1})$ be the natural filtration and $Y_k = \mathbb{E}[...
- 11