Questions tagged [concentration-of-measure]
Use this tag for questions about the principle that a random variable that depends in a Lipschitz way on many independent variables (but not too much on any of them) is essentially constant.
219
questions
0
votes
0answers
12 views
Bound sub-Gaussian variance proxy by variance for $[-1,1]$-valued random variables
Consider a random variable $X$ taking values in $[-1,1]$ with mean $0$ and variance $\sigma^2$. A quantity $V^2$ is a sub-Gaussian variance proxy if $\mathbb{E} \exp(\lambda X) \leq \exp(\lambda^2 V^2/...
0
votes
1answer
24 views
Anti-concentration for Gaussian
Is there a reasonable anti-concentration bound for Gaussian? Let $X\sim\mathcal N(0, \sigma^2)$, can we get $P(|X|>\epsilon)>1-\delta$? Thanks.
0
votes
0answers
6 views
Small gaussian width implies large polar body gaussian measure
This is Ex. 6.14 from http://math.univ-lyon1.fr/~aubrun/ABMB/ABMB.pdf.
First some definitions. For a set $L$ let $w(L) = \mathbb{E} \max_{x \in L} \langle x, g \rangle$ where $g \sim N(0, I)$. Also ...
1
vote
0answers
26 views
Sum of random variables $\mathbf{x}\sim \text{Uniform}(\mathbb{S}^{n−1})$ converges to Gaussian?
Let $\mathbf{x}=(x_1,...,x_n)\sim \text{Uniform}(\mathbb{S}^{n-1})$ and $z\sim\mathcal{N}(0,1)$. How to prove for any $A\subseteq \mathbb{R}$
$$\Big|\mathbb{P}\Big\{\sum_i x_i \in A \Big\} - \mathbb{P}...
7
votes
1answer
147 views
Lower bound on the variance of the maximum of random variables.
I'm trying to figure out a lower bound on the variance of the follow:
$\max_i(x_1,x_2,...x_m)$. Where $x_i, i \in m$ are independent random variables that shares the same variance $\sigma_x$.
I know ...
1
vote
0answers
24 views
Proving an exponential tail bound inequality
In the book "A graduate course in probability" by Allan Gut, I ran into the following lemma. I have no issues with this, however, in the very next page, Gut states that by applying this lemma along ...
2
votes
0answers
24 views
Given $A \in \mathbb R^{m \times n}$, find upper bound for $\mathbb E\|Az\|_q$ for $z$ drawn uniformly at random on the sphere $\{\|z\|_p = 1\}$
Let $m$ and $n$ be positive integers and $p,q \in [1,\infty]$. Consider the finite-dimensiaonal normed vector spaces $X = (\mathbb R^m,\|\cdot\|_p)$ and $Y = (\mathbb R^n,\|\cdot\|_q)$, where
$$
\|x\|...
0
votes
1answer
43 views
Concentration bound on function of the estimate
I know that through concentration inequalities (e.g. Hoeffding, Mcdiarmids, Chernoff) it is possible to have concentration bounds on the empirical mean $\hat{\mu}(N) = \frac{1}{N} \sum_{i = 1}^N X_i$ ...
0
votes
0answers
10 views
Hoeffding Inequality for Confidence Interval (In Phase Retrieval)
I am reading a paper which is related to phase retrieval theory.
In Eq. $3.13$ (Page $14$), the authors state that " Setting $T_n = \sqrt{2\beta \log n}$, then a simple application of Hoeffding’s ...
1
vote
1answer
43 views
Concentration around mean from concentration around median
I got stuck solving exercise 11.3 from the book Concentration of Measure for the Analysis of Randomized Algorithms. The setting is:
Consider again the situation of Section $7.2,$ the number of non-...
0
votes
0answers
10 views
Upper bound for modified total-variation distance between gaussian distributions: $ \sup_B \mathcal N(c',1)(B) - \mathcal N(c, 1)(B^\epsilon)$
For a nonempty Borell subset $B$ of $\mathbb R$ and $\epsilon \ge 0$, let $B^\epsilon := \{x \in \mathbb R \mid d(x,B) \le \epsilon\}$, the $\epsilon$-enlargement of $B$, where $d(x,B):= \inf_{x' \in ...
4
votes
1answer
140 views
Median Concentration implies mean concentrarion
I want to prove that if X is such that
$$P[|X-m_X|\geq t] \leq c_1 e^{-c_2t^2},$$
for $c_1, c_2$ positive constants, $t\geq 0$, then it holds that $$P[|X-E[X]|\geq t] \leq c_3 e^{-c_4t^2},$$ with $c_3=...
0
votes
0answers
14 views
Number of hittings in a Markov chain with stationary initial distribution
Let $\{X_1, \cdots, X_n,\cdots\}$ be a discrete time Markov chain (with discrete or continuous state space) with stationary distribution $\pi$. Given state $A$ (discrete case $A$ is one single point, ...
1
vote
0answers
23 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 ...
0
votes
0answers
23 views
Under what addition conditions does an empirical distribution converge to the true distribution at a rate faster than $1/\sqrt{N}$?
Let $P=(p_1,\ldots,p_K)$ be a finitely supported distribution and $\hat{P}_N$ be its empirical version based on $N$ iid sample. It's a classical result that $\mathbb E[TV(P,\hat{P}_N)] \le C/\sqrt{N}$ ...
1
vote
0answers
36 views
Chernoff Type Bounds for a Stopped Sum of Independent Random Variables
Let $Y_1, \ldots, Y_n$ and $X_1, \ldots, X_n$ be i.i.d. $p$-Bernoulli random variables and let $T \in \{0, \ldots, n\}$ be a stopping time for the process. From Wald's equation, we know
$$
E\left[\...
0
votes
1answer
25 views
Chernoff-type bound over sums of the whole sequence
Let $X_1, X_2, X_3, \ldots, X_n$ be a sequence of i.i.d. Bernoulli independent random variables each being 1 with probability $p$. For each $t \geq 0$ define
$$
S_t := \sum_{i=1}^t X_i.
$$
Is my ...
0
votes
0answers
22 views
Concentration for the maximum magnitude entry for a random matrix
For $A \in {\mathbb R}^{n \times m}$ let,
$$ \vert A \vert _{\max} = \max_{\substack{i=1,\ldots, n\\ j = 1,\ldots,m}} \vert A_{ij} \vert $$
Are there any concentration inequalities known about this ...
1
vote
0answers
45 views
Mathematical demonstration of the distance concentration in high dimensions
I know that in high-dimensional space, the distance between almost all pairs of points has almost the same value ("Distance Concentration"). See Aggarwal et al. 2001, On the Surprising Behavior of ...
1
vote
1answer
39 views
Inequality for probability of an average in terms of individual probabilities
Let $X_1,\cdots,X_n$ be identically distributed nonnegative, real-valued random variables that are not necessarily independent. Note that we trivially have for any $\varepsilon > 0$:
$$ \mathbb{P}\...
0
votes
0answers
38 views
Question on reverse union bound for independent events
From the note on union bound I found the following
Fact 1.3 (Reverse Union Bound) Let $\mathcal{F}_1$ and $\mathcal{F}_2$ be arbitrary events, not necessarily independent. Suppose that $\...
1
vote
0answers
27 views
Concentration inequality on 1-norm of random vector
I would like to give an upper bound on $\Pr\{||X-\mathsf{E}[X]||_1 > t\}$ where $X$ is a $d$-dimensional random vector with each entry follows i.i.d. binomial $(n,p)$ (so $\mathsf{E}[X]$ is ...
1
vote
0answers
23 views
Tail bound on difference of shifted binomials (generalization)
I have a post Tail bound on difference of shifted binomials answered before and now I want to consider I slightly generalization of it which can't be solved using the methods in the previous thread.
...
1
vote
1answer
81 views
Gaussian width of sparse balls
The Gaussian width of a set $T\subset \mathbb{R}^n$ is defined as,
$$
G(T) = E\left[\sup_{\theta \in T} \sum_{i=1}^n \theta_i W_i\right],
$$
where, $\mathbf{W}=(W_1,\ldots,W_n)$ is a sequence of i.i.d....
3
votes
1answer
52 views
Tail bound on difference of shifted binomials
I would like to derive an upper bound on $\mathsf{Pr}\{(\frac{X}{n}-\frac{1}{2})^2 \leq (\frac{Y}{n}-\frac{1}{2})^2\}$ where $X,Y$ are independent and $X\sim$ Bin($n,p$) where $p\neq \frac{1}{2}$, and ...
1
vote
0answers
26 views
Concentration of the value of times Markov Chain visits a certain state
I have a 2-state Markov chain with the following transition matrix
${\displaystyle P={\begin{bmatrix}1-p&p\\1&0\end{bmatrix}} }$,
where $0 < p < 1$.
Initially, we are in State 1.
Let ...
0
votes
0answers
17 views
Upper-bound on $\inf_{(X,X')} P(\|X-X'\| > 2t)$ over all couplings $(X,X')$ of $P_1$ and $P_2$
Preamble: I've been struggling with the problem below (and similar problems https://mathoverflow.net/q/351317/78539) for a while now. Any kind of help would be very useful. Thanks in advance!
So, let ...
0
votes
1answer
27 views
Basic question on union bound for high probability bound for martingale difference sequence
I have two martingale difference sequences $X_i$ and $Y_i$ with $|X_i| \leq 2H$ and $|Y_i| \leq 2H$. Then by Azuma Hoeffding inequality, I can say with probability at least $1-\delta/2$,
$$\sum_{i=1}^...
1
vote
1answer
36 views
Question on union bound for Gaussian Concentration
From the note on union bound I found the following
Now I have the following lemma on multivariate normal distribution (with dimension $d$): Let $x \sim \mathcal{N}(0, \nu(\delta/M)\Sigma^{-1})$ where ...
0
votes
1answer
56 views
A concentration inequality with random normal distributions
Given a constant $C >0$ and $X \sim {\cal N}(\vec{\mu}, \Sigma_{d \times d})$ then do we have a good upperbound on the deviation probability, $\mathbb{P} [ \Vert X \Vert \geq C ]$ ?
Assume $\...
0
votes
1answer
33 views
high probability Gaussian concentration inequality for $\|X\|_{\Sigma^{-1}}$ where $X \sim \mathcal{N}(0,\alpha(\delta) \Sigma)$
In the appendix of this paper appendix, Lemma I.4 the following Gaussian concentration lemma is given.
Consider $d$- dimensional multivariate Gaussian distribution $\overline{\xi}_t^k \sim \mathcal{N}...
3
votes
1answer
127 views
Upper bounds to high dimensional gaussian vectors
I'm trying to prove a claim given in Vershynin's Book - High-dimensional probability.
The notation used is $g$ as a vector, $\sim$ represents similarity. $N(\mu, \sigma^2)$ is a normal distribution ...
0
votes
1answer
56 views
At a given distance from the origin, which convex subsets of an $\ell_p$-ball have the maximal volume?
For a positive integer $n$ and $p \in [1,\infty]$, let $\mathbb B_{n,p} := \{x \in \mathbb R^n \mid \|x\|_p \le 1\}$ be the $\ell_p$ unit-ball in $\mathbb R^n$. Fix $h \in [0, 1]$.
Question. Of ...
1
vote
1answer
72 views
What's wrong with the following proof of $\mathbb{E} \max_{k=1, \dots, N} |X_k| \le C\max_{k=1, \dots, N} \|X_k\|_{\psi_2}$
I was trying to solve the same problem as in this question and ended proving something stronger. However, what I've proven cannot be true, since it is known (taking the $X_k$'s to be independent N(0, ...
1
vote
0answers
29 views
Probability distribution of intersection of $0/1$ Bernoulli sequences
Assume odds of $1$ or $0$ is $0.5$ and independent.
Suppose we have two randomly generated $0$ and $1$ sequences if length $2n$ each and each with number of $1$s between $0.5n - a$ and $0.5n + a$ ...
0
votes
0answers
20 views
Covering numbers and distributions
If given a convex, compact set $A \subset \mathbb{R}^n$ with finite volume having a minimum cardinality $\epsilon$-net denoted by $\mathcal{N}_\epsilon$, is it possible to find a continuous ...
1
vote
0answers
28 views
Concentration theorems for random points in a cuboid
Given an $n$ dimensional cuboid (not cube) of unit volume if we pick two points in there from uniform distribution then what is there any concentration theorems that can be shown on the probability ...
3
votes
1answer
82 views
Strenghtening of Hoeffding inequality on finite range interval
Let $X_1,\ldots,X_n$ be independent random variables with values in $[0,1]$. Let $S_n=\sum_{k=1}^n X_k$ and $m=E(S_n)$. Prove that for $t\in [m,n)$, $$P(S_n\geq t)\leq \left(\frac mt\right)^{t} \left(\...
1
vote
0answers
34 views
Concentration bound for least-square approximation error via uniform row sampling
While reading the following two papers:
1) Faster Least Squares Approximation of Drineas et al (https://arxiv.org/pdf/0710.1435.pdf)
2) Blendenpik: supercharging lapack's least-square solver of ...
0
votes
0answers
37 views
Concentration inequality with random signs and convolutions
Let $\epsilon_k$ be i.i.d random signs (or Rademacher variables), i.e., $P(\epsilon_{k}=1)=P(\epsilon_{k}=-1)=0.5$, $a, b, c, d$ be $n$-dimensional vectors.
I hope to prove a concentration inequality:...
3
votes
1answer
56 views
Upper bound for Rademacher complexity
Given $x_1^n=\{x_1,...,x_n\}$ with $x_j\in R^p$ and $\mathcal{F}$ a class of real-valued functions defined in $R^p$, define $\mathcal{F}(x_1^n)$ as
$$\mathcal{F}(x_1^n)=\{(f(x_1),...,f(x_n)):f\in\...
2
votes
0answers
75 views
Are there any generalization of the DKW inequality to the cluster sampling case?
The famed DKW inequality states the following:
$$\mathbb{P}\left(\sup_{x\in\mathbb{R}}|F_n(x)-F(x)|>\epsilon\right)\leq 2e^{-2n\epsilon^2}$$.
Further using Bahadur's representation, we naturally ...
0
votes
0answers
40 views
Concentration inequality of $L$-Lipschitz function of Gaussian Random Variables
Define $W \in \mathbb{R}^{m \times n}$ as a matrix where each component $W_{ij} \sim \mathcal{N}(0,1)$ is i.i.d. and suppose I have some function $f$ that is $L$-Lipschitz, ie for any $W, \hat{W} \in \...
1
vote
0answers
65 views
Concentration of the number of edges inside a random induced subgraph
Let $G=(V, E)$ be an arbitrary graph with $n := |V|$ vertices and let $r \leq n$ be a parameter. Let $U \subseteq V$ be a subset of size $r$, chosen uniformly at random from the set of all subsets of $...
3
votes
1answer
86 views
Large deviation bound for squared norm of the sum of two random variables
I want to pose this question as general as possible and ask for reference of what to do in similar situations. I'll incrementally add details to narrow down the problem.
I want to derive large ...
0
votes
0answers
25 views
Concentration Inequalities for point processes
I'm looking for some references in Concentration Inequalities on the counting random variable $ N(t) $ for Hawkes and Poisson (temporal) point processes. Could you direct me to some? I haven't ...
0
votes
0answers
39 views
Restricted Isometry Property for Random Orthogonal Projections
The following is from Roman Vershynin's: High-Dimensional Probability: An Introduction with Applications in Data Science.
Let $P$ be the orthogonal projection in $\mathbb{R}^n$ onto an $m-$...
1
vote
1answer
53 views
Variance of number of distinct values in a collection of iid discrete random variables
I'm struggling with the following problem. Let $X_i$ be iid discrete rvs, taking values in $\mathbb{N}$ with arbitrary distribution $\mathrm{P} (X_i = k) = p_k$. Let $Z_n$ be a number of distinct ...
0
votes
0answers
27 views
Isoperimetry / Concentration Inequality
I am currently working with Lipschitz functions $f: \{ 1, \dots , N \}^d \to \mathbf{R}$, and trying to obtain concentration bounds on $f(X)$ about it's mean, where $X$ is uniformly distributed on $\{ ...
1
vote
1answer
37 views
Variation of matrix Bernstein inequality
Let $[X_1, X_2, ..., X_r]$ be a set of independent $d_1 \times d_2$ dimensional random matrices with $\mathbb{E}(X_i) = 0$ and $\|X_i\| \leq B$ (bounded operator norm).
Introduce the sum of random ...
