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.

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5