Questions tagged [measure-concentration]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-1 votes
0 answers
44 views

Super-exponential concentration for $\frac{\sum_{i = 1}^{n} X_i}{\sum_{i = 1}^{n} X_i^2}$ with $X_i$ iid. Poisson

Consider $n$ independent Poisson(1)-distributed random variables $(X_i)_{1 \leq i \leq n}$. Is it true, that $$P\left(\frac{\sum_{i = 1}^{n} X_i}{\sum_{i = 1}^{n} X_i^2} \leq \epsilon \right) \leq \...
unwissen's user avatar
2 votes
0 answers
84 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,...
TOM's user avatar
  • 2,248
3 votes
1 answer
119 views

Concentration of measure on spheres with respect to a unitary of trace approximately zero

Cross-posted from MSE, where it hasn’t received any answer yet: This question arose out of my attempt to understand how a unitary of trace approximately zero acts on the unit sphere of a $n$-...
David Gao's user avatar
  • 1,262
2 votes
0 answers
49 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....
WeakLearner's user avatar
1 vote
2 answers
157 views

Inner product of the spherical cap and Gaussian

Let $d\in \mathbb{N}$ and $\eta \sim N(0,I_d)$ where $N(0,I_d)$ is the gaussian distribution with the covariance matrix of $I_d$. Also, define a spherical cap as follows. Fix $v \in \mathbb{S}^{(d-1)}$...
MMH's user avatar
  • 139
0 votes
0 answers
46 views

Concentration inequalities for leave-one-out sum

Let $X_1,...,X_n$ be iid random variables. Consider $f:\mathbb{R}\times\mathbb{R}^{n-1}\to\mathbb{R}$ such that $f$ is symmetric in the last $n-1$ variables. Our goal is to show that $\sum_{i=1}^n f(...
legon's user avatar
  • 31
1 vote
1 answer
55 views

How does Chernoff-Hoeffding bound with limited independence reduce to the usual generic CH bound with complete independence

As the title might suggest, I am referring to this paper https://www.cs.umd.edu/~srin/PDF/ch-bounds.pdf , titled : Chernoff-Hoeffding Bounds for Application with Limited Independence. The theorem in ...
some1fromhell's user avatar
0 votes
0 answers
73 views

Concentration bounds for sum of weighted sampling without replacement

Let $X$ be a collection of $2l$ non-negative numbers $X_1,X_2,\ldots,X_{2l}$. We draw $l$ weighted (proportional to values) samples without replacement from $X$. Let $S$ denote this set of $l$ samples....
Sankhya's user avatar
  • 11
0 votes
0 answers
50 views

Tight Chernoff Concentration for Bernoulli(p) RV

I remember seeing a research paper on tight concentration of Bernoulli(p) random variable in terms of $p$. What I mean is that they used a stronger upper bound for the MGF than $E[e^{s(X-p) }]\leq e^{...
Black Jack 21's user avatar
0 votes
1 answer
180 views

Concentration inequalities for random sampling without replacement

Let a population $C$ consist of $N$ values $c_1, c_2, \cdots, c_N$, with $c_i\in \{0,1\}$. Let $X_1, X_2, \cdots, X_n$ denote a random sample without replacement from $C$ and let $Y_1, Y_2, \cdots, ...
Dotman's user avatar
  • 105
2 votes
1 answer
156 views

Small deviations of real log-concave random variable

I am working with a log-concave real random variable, that has a density $f(x) = \exp(-\varphi(x))$ with $\varphi$ convex. Assuming that $X$ is centered and has unit variance ($\mathbb{E}X=0$, $\...
Hugo Ch's user avatar
  • 23
4 votes
1 answer
182 views

Sign of error in the central limit theorem

Let $X_n$ and $Y_n$ be independent copies of two random variables $X$ and $Y$ with domain $\{-1,0,1\}$ for $n\in \mathbb{N}$. For a given $k\in \mathbb{N}$, I would like to find conditions on $X$ and $...
Flo Dorner's user avatar
17 votes
0 answers
387 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{...
Samuel Johnston's user avatar
2 votes
1 answer
135 views

A concentration inequality related to suprema of sub-Gaussian processes

Let $x_1,\dots,x_n$ be deterministic points in some space $X$ and consider a class of real-valued functions $\mathcal G$ on $X$. We further assume that for any $g \in \mathcal G$, $$ \Bigl(\frac1n \...
passerby51's user avatar
  • 1,639
0 votes
2 answers
213 views

Bounds tighter than the additive Chernoff

Additive Chernoff Suppose $X_1, \ldots, X_n$ are i.i.d. random variables, taking values in $\{0,1\}$. Let $p=\mathrm{E}\left[X_i\right]$ and $\varepsilon>0$. \begin{gather*} \operatorname{Pr}\left(\...
Dotman's user avatar
  • 105
1 vote
0 answers
55 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$, ...
dohmatob's user avatar
  • 6,726
2 votes
0 answers
62 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) ...
IMOS's user avatar
  • 121
1 vote
2 answers
202 views

Beating the $1/\sqrt n$ rate of uniform-convergence over a linear function class

Let $P$ be a probability distribution on $\mathbb R^d \times \mathbb R$, and let $(x_1,y_1), \ldots, (x_n,y_n)$ be an iid sample of size $n$ from $P$. Fix $\epsilon,t\gt 0$. For any unit-vector $w \in ...
dohmatob's user avatar
  • 6,726
3 votes
1 answer
236 views

Sub-Gaussian random variables and convex ordering

Suppose that $X$ is a $1$-sub-Gaussian real-valued random variable, i.e. for all $t \in \mathbf{R}$, it holds that $\log \mathbf{E} \exp \left( t X \right) \leqslant \frac{1}{2} t^2 $. Does there ...
πr8's user avatar
  • 688
2 votes
1 answer
115 views

Simplified upper bounds for moment-generating function of symmetrised random variable

Let $X$ be a nonnegative random variable such that $\mathbf{E} \left[ \exp X \right] < \infty$. For $\theta \leqslant 1$, an appropriate application of Jensen's inequality, yields that \begin{align}...
πr8's user avatar
  • 688
1 vote
1 answer
114 views

Lipschitz-type inequalities for Markov kernels

Let $K(\cdot\mid\cdot)$ be a Markov kernel. For a measure probability $\mu$, denote by $\mu K$ the probability measure induced by $K$ and $\mu$, i.e. $(\mu K)(A):=\int_\Omega \mu(d\omega)K(A\mid\omega)...
Michele's user avatar
  • 313
1 vote
1 answer
164 views

Concentration inequality for square roots

Given a sequence of (not-necessarily-iid) real-valued random variables $X_n$ that converge to $a\in\mathbb{R}$ in probability, suppose we have an exponential concentration inequality of the form $$ P(|...
tim523's user avatar
  • 13
1 vote
0 answers
127 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 ...
dohmatob's user avatar
  • 6,726
1 vote
1 answer
81 views

Asymptotic scaling of mean and variance for the norm of random vector (non gaussian components)

The norm of a vector whoose components $X_i$ are normally distributed follows the Non-central chi distribution and it can be shown that, increasing the number of components $k$ (i.e. the dimension of ...
user1172131's user avatar
2 votes
2 answers
211 views

Asymptotic scaling of mean and variance for non-central chi distribution

Define $Y \equiv \sqrt{\sum_{i=1}^k(\frac{ X_i}{\sigma_i})^2}$, with $X_i \sim \mathcal{N}(\mu_i, \sigma_i^2)$ and independents. It is known that $Y$ is distributed as a non-central chi (Noncentral ...
user1172131's user avatar
1 vote
1 answer
210 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 ...
dohmatob's user avatar
  • 6,726
1 vote
0 answers
78 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)$. ...
Mark Schultz-Wu's user avatar
0 votes
1 answer
86 views

Is the product of sub-Gaussian polynomials in $\mathbb{R}[x]/(x^n-1)$ sub-Gaussian?

Let $\psi_\alpha(x) := \exp(x^\alpha)-1$. It is well-known that for $\alpha\geq 1$ that $$\lVert X\rVert_{\psi_\alpha} = \inf\{k>0\mid \mathbb{E}[\psi_\alpha(|X|/k)] \leq 1\}$$ defines an Orlicz ...
Mark Schultz-Wu's user avatar
1 vote
1 answer
290 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 ...
Peyman's user avatar
  • 243
3 votes
0 answers
56 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 ...
alesia's user avatar
  • 2,582
5 votes
1 answer
389 views

Lower tail of random rank one sums?

Let $\{x_i\}_{i\geq 1}$ be iid random elements of the sequence space $\ell^2(\mathbb{N})$; assume that $\|x_i\|_2 \leq 1$ almost surely. Let $\Sigma = \mathbb{E}[x_1 \otimes x_1]$. Define $$ \Sigma_n =...
Drew Brady's user avatar
1 vote
1 answer
146 views

Anti-concentration inequality for the eigenvalue of Gaussian matrix

Let $f(x) = f(x_1, . . . , x_n)$ be a polynomial of degree $d$ and $\text{Var}[f] = 1$. One result by Carbery and Wright shows that for any $t\in\mathbb{R}$ and $ε > 0$, $$ \text{Pr}_{x\sim N^n}[|f(...
qmww987's user avatar
  • 49
0 votes
1 answer
130 views

Deducing norm concentration from MGF bounds

Suppose that $X$ is a centered, $\mathbf{R}^d$-valued random variable such that for all $t \in \mathbf{R}^d$, there holds the bound $$\log \mathbf{E} \left[ \exp \langle t, X \rangle \right] \leqslant ...
πr8's user avatar
  • 688
1 vote
1 answer
186 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 $$\...
happyle's user avatar
  • 39
0 votes
1 answer
101 views

Positivity of linear combination of gaussian variables

Consider a collection of independent standard Gaussian variables $w_i$ for $i = 1, 2, \ldots, N$. Define its linear combination $f:=\sum_{i=1}^Na_iw_i+b_i$, where $a_i=pb_i$ ($p$ is a fixed parameter),...
happyle's user avatar
  • 39
1 vote
2 answers
218 views

Anti-concentration of gaussian variable

Let $X$ be $\mathcal{N}(\mu,\sigma^2)$ gaussian. Its expectation $\mu$ is positive. Can we derive a lower bound on $$\mathbb{P}(X\geq\epsilon)\geq g(\epsilon,\mu,\sigma) \text{ where } \epsilon\leq\mu$...
M.K's user avatar
  • 155
1 vote
1 answer
187 views

$L_1$ norm concentration of an empirical distribution

Suppose we have one random variable $X$, whose sample space is $\mathbb{X}=\{x_1,x_2,\dots,x_m\}$, and the size of the sample space is $m$. We have $N$ i.i.d. samples from this distribution, and $x_i$ ...
white's user avatar
  • 23
0 votes
0 answers
150 views

Anti-concentration for Bernoulli summation

Suppose $\{ Y_i\}_{i = 1}^n$ is i.i.d. Bernoulli distribution with mean $p$. Denote the sample of $\{ Y_i\}_{i = 1}^n$ as $\overline{Y} = \frac{1}{n} \sum_{i = 1}^n Y_i$. I want to know where there ...
香结丁's user avatar
  • 331
1 vote
1 answer
168 views

concentration of random field to its expectation function

Question Given a random field $X(t)$ where the parameter space $T\subset\mathbb{R}_N$. Is there result regarding the concentration of the random field? For example $\mathbb{P}\{\|X(t)-\mathbb{E}\{X(t)\...
M.K's user avatar
  • 155
0 votes
0 answers
35 views

concentration inequality with matrix coefficient

Let $(X_i)_{i=1}^N$ be mean zero sub-Gaussian random vectors in $\mathbb{R}^n$, i.e., there exists $C>0$ such that for all $u\in \mathbb{R}^n$, $$ \mathbb{E}\left[e^{u^\top X_i}\right]\le e^{\frac{...
John's user avatar
  • 483
2 votes
0 answers
107 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,...
dohmatob's user avatar
  • 6,726
1 vote
1 answer
190 views

Concentration of a certain simple / well-structured random multilinear polynomial with growing degree

Let $k$ and $N_1$ be positive integers and set $N=kN_1$. Partition $[N] := \{1,2,\ldots,N\}$ $k$ disjoint from $G_1,\ldots,G_k$ of each of size $N_1$, and let $\mathcal T(k,N_1)$ be a transversal of ...
dohmatob's user avatar
  • 6,726
2 votes
1 answer
305 views

Converse of the Herbst argument?

Background For a real-valued random variable $X$, define its entropy by $H(X) = E[\phi(X)] - \phi(E[X])$, where $\phi(u) = u \log u$. It can be shown that, if the entropy satisfies the bound $$ H(e^{\...
aest's user avatar
  • 153
2 votes
1 answer
249 views

The lower bound of bivariate normal distribution

Suppose $(Z_1, Z_2)$ is the zero-mean bivariate normal distribution with covariance $\left( \begin{matrix} 1 & \rho; \\ \rho & 1\end{matrix} \right)$ with positive $\rho > 0$. What I want ...
香结丁's user avatar
  • 331
4 votes
2 answers
243 views

Concentration of minimum Hamming distance between $N$ points sampled iid from uniform distribution on $n$-dim hypercube $\{0,1\}^n$

Let $n$ be a large positive integer. Sample $N \ge 2$ points $x_1,\ldots,x_N$ iid from the uniform distribution on the $n$-dimensional hypercube $\{0,1\}^n$. Define the gap $\delta_{N,n} := \min_{i \...
dohmatob's user avatar
  • 6,726
1 vote
0 answers
126 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 ...
dohmatob's user avatar
  • 6,726
4 votes
2 answers
330 views

Rate of convergence of sample maximum, $\Big|\max_{j \leq n} |f(U_j)| - \|f\|_\infty\Big|$

Suppose that $f \colon [0, 1] \to \mathbb{R}$ is a $1$-Lipschitz function. Define the uniform norm $\|f\|_\infty = \sup_{x} |f(x)|$. Given $\{U_j\}_{j=1}^\infty$ independent and identically ...
Drew Brady's user avatar
6 votes
1 answer
714 views

Simple proof of sharp constant in DKW inequality

The DKW inequality says that if $F_n$ is the empirical CDF corresponding to real-valued random variables $X_1, \dots, X_n$ distributed identically and independently from a distribution with CDF $F$, ...
Drew Brady's user avatar
1 vote
1 answer
166 views

Hypothesis to guarantee Lindeberg's condition

Imagine to have a set of random variables $\{ X_i \}_{i=1}^{n}$ independent (Non identically distributed). In these scenario, if the Lindeberg's condition hold we can extend the result of the CLT, i.e....
user1172131's user avatar
8 votes
1 answer
510 views

Concentration bounds for martingales with adaptive Gaussian steps

Consider the following martingale: $X_1 \sim \mathcal{N}(0, 1)$, and for any $n > 1$, $X_n \sim \mathcal{N}(X_{n-1}, X_{n-1}^2)$ (notice, this is a conditional distribution given $X_{n-1}$). I am ...
moshenfeld's user avatar

1
2 3 4 5
8