Questions tagged [measure-concentration]
The measure-concentration tag has no usage guidance.
397 questions
3
votes
0
answers
93
views
Tighter Freedman's inequality for a special martingale difference sequence
Let $X_{1}, \ldots, X_{T} \in \{0, 1\}$ be a sequence of Boolean random variables with
$$
\mathbb{E}[X_{t} | X_{1}, \dots, X_{t - 1}] = p_{t}.
$$
Consider the sequence $Y_{t} := X_{t} - p_{t}$ (which ...
- 41
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
3
votes
1
answer
159
views
Sub-Gaussian concentration without the sub-Gaussian norm
A random variable $X$ is said to have sub-Gaussian tails with parameter $\sigma>0$ if
$$\Pr[|X|\geq t] \leq 2\exp(-t^2/(2\sigma^2))$$
I am interested if $X_0, X_1$ are independent, and have sub-...
- 2,183
0
votes
0
answers
72
views
Reflections of Voronoi diagrams
I wonder if something similar to the following fact is known, and I would greatly appreciate any references.
Let $t_1, t_2, \ldots, t_N$ be unit vectors in $\mathbb{R}^n$.
Let $S$ denote the unit ...
- 1
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
2
votes
3
answers
184
views
Existence and sharpness of Bernstein-type bounds on the moment-generating function
Let $X$ be a centred random variable with variance $\sigma^2$, and whose moment-generating function exists in an open neighbourhood of the origin.
Say that $X$ satisfies a 'Bernstein-type' MGF bound ...
- 801
3
votes
0
answers
130
views
A Talagrand inequality for the supremum of partial sums over function classes under dependence. (Reference request)
As a consequence to the Talagrand concentration inequality, it is well known that for a measurable space $(S,\mathcal{S})$ and an i.i.d. sample $X_1,...,X_n$ of $S$-valued random variables, if $\...
- 141
0
votes
0
answers
44
views
Large Deviation Principle for an adaptive sampling rule for Multi Armed Bandits
Consider the following adaptive strategy for sampling from a Multi Armed Bandit with $K$ arms:
Split the $T$ rounds into $N (\in \mathbb{N})$ disjoint intervals. Each interval is indexed by $i=1,2,\...
- 9
3
votes
1
answer
130
views
Does a DKW-type inequality hold for the empirical CDF of a random vector on the sphere?
I've begun to study concentration of measure because of its relevance to statistical mechanics. In recent decades concentration inequalities have played a role in elucidating foundational conceptual ...
- 131
2
votes
1
answer
83
views
Azuma-Hoeffding for one-side bounded super-martingale sequence
Suppose we have a real-valued super-martingale difference sequence $\{X_k\}$ w.r.t. some filtration $\mathcal{F_k}$, i.e., $X_k$ is $\mathcal{F_k}$-measurable, and
$$ \mathbb{E}[X_k|\mathcal{F}_{k-1}] ...
- 33
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
0
votes
1
answer
80
views
Uniform concentration bound (function-valued random variable / continuous stochastic process)
I'm trying to consider a probability space $\Omega$ and
$f(x,\xi):\mathcal{X}\times\Omega\to\mathbb{R}$ (stochastic process over space? or function-valued random variable?), where $\mathcal{X}\subset\...
- 321
0
votes
1
answer
108
views
RMT for modified Wishard matrix $Y'Y$ (where $i$th row of $Y$ is zero if $|x_i^\top u| \le \theta$; else it equals $x_i$)
Let $n$ and $d$ be positive integers tending to infinity such that $d/n \to \phi \in (0,\infty)$. Let $X$ be an $n \times d$ random matrix with iid rows $x_1,\ldots,x_n$ from $N(0, \Sigma)$, where $\...
- 6,853
-1
votes
1
answer
163
views
Is it true that if a random vector has independent coordinates each bounded by $1$ then $P[ \|X\| \leq \epsilon\sqrt{n}] \leq (C\epsilon)^{n}$?
I'm studying Vershynin's well-written book on "High Dimensional Probability" and the third chapter on concentration of random vectors.
Exercise 3.1.7 from the book is the following.
Let $X =...
- 401
2
votes
1
answer
386
views
A maximal inequality
Let $\{X_i\}_{i\in\mathbb{N}}$ be i.i.d. symmetric random variables, with $-1\leq X_i\leq 1$, $\mathbb{E}(X_i) =0$, $\mathbb{E}(X_i^2) = 1$. We have that:
$$
P\left(\bigcap_{k = 1}^{n}\frac{|\sum_{i = ...
- 63
2
votes
1
answer
136
views
Concentration bound for a increasingly weighted sum of bernoulli random variables
Given $x_1,x_2,\ldots,x_n$ i.i.d. bernoulli random variables with $P(x_i=1)=\frac1n$. Given a constant $c=1+\frac{1}{m}, m\geq n$. Is there an explicit theorem that can derive a concentration argument ...
- 25
1
vote
1
answer
101
views
Weak Borell-TIS inequality for a subgaussian process
It is a known fact (Borell-TIS inequality) that, given an almost surely bounded Gaussian centered process $X(t), t \in T$, where $T$ is a topological space, $$\mathbb{P}\{\sup_t X(t)-\mathbb{E} \sup_t ...
- 177
2
votes
1
answer
119
views
Simultaneous Concentration of $\sum_{i = 1}^{n} X_i^2$ and $\sum_{i = 1}^{n} X_i$ with $X_i$ iid. Poisson
Consider $n$ independent Poisson(1)-distributed random variables $(X_i)_{1 \leq i \leq n}$.
This is a (hopefully more interesting) follow-up question to Super-exponential concentration for $\frac{\...
- 578
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
3
votes
1
answer
156
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$-...
- 2,830
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
1
vote
2
answers
194
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)}$...
- 139
0
votes
0
answers
53
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(...
- 31
1
vote
1
answer
115
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 ...
- 121
0
votes
0
answers
116
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....
- 11
0
votes
1
answer
231
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, ...
- 105
2
votes
1
answer
237
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$, $\...
- 23
4
votes
1
answer
189
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 $...
- 53
19
votes
0
answers
553
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{...
- 484
2
votes
1
answer
250
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 \...
- 1,741
0
votes
2
answers
282
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(\...
- 105
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
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
1
vote
2
answers
221
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 ...
- 6,853
4
votes
1
answer
321
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 ...
- 801
2
votes
1
answer
238
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}...
- 801
1
vote
1
answer
144
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)...
- 333
1
vote
1
answer
191
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(|...
- 13
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
108
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 ...
- 305
2
votes
2
answers
269
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 ...
- 305
1
vote
1
answer
287
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
0
votes
1
answer
124
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 ...
- 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
3
votes
0
answers
70
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 ...
- 2,772
5
votes
1
answer
402
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 =...
- 380
1
vote
1
answer
207
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(...
- 91
0
votes
1
answer
182
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 ...
- 801