All Questions
Tagged with pr.probability measure-concentration
324 questions
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
1
answer
339
views
Probability of Hamming weight
Given $s,t\in(0,1)$, $c>1$, $n\in\Bbb N$, pick ${n^t}$ random vectors $\{v_i\}_{i=1}^{{n^t}}$ such that each $v_i\in\{x\in\{0,1\}^{2^n}:|x|_{hamming}={2^{n-n^s}}\}$.
Denote $v_j\cap v_j$ to be ...
- 13.9k
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
1
answer
247
views
Concentration and Correlation for Magnitudes of Gaussian Vectors
Suppose we have a large collection of standard normal random variables $a_i\in\mathbb{R}^n$. We know by standard concentration results that if we take $m \geq C\left(t/\epsilon\right)^2n$ samples, ...
- 205
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
1
answer
668
views
Lower-bound for smallest eigenvalue of random $k \times $k matrix $C(W)$ defined by $C(W)_{i,j} := 2(w_i^\top w_j)^2 + \|w_i\|^2\|w_j\|^2$
Let $k$ and $d$ be positive integers such that $d/k:=\lambda > 1$. Let $W$ be $k \times d$ random matrix with rows $w_1,\ldots,w_k \in \mathbb R^d$ drawn iid from $N(0,(1/d)I_d)$, and define the $k ...
- 6,853
2
votes
1
answer
274
views
Is there monotonicity of measure concentration?
Suppose $X$ and $Y$ are nonnegative random variables such that $\mathrm{Pr}(X\geq t)\leq\mathrm{Pr}(Y\geq t)$ for all $t\geq0$. Now take $X_1,\ldots,X_n$ to be independent with the same distribution ...
- 7,633
2
votes
2
answers
690
views
Concentration and anti-concentration of gap between largest and second largest value in Gaussian iid sample
Let $n \ge 3$ be an integer and let $X=(X_1,\ldots,X_n)$ be random vector with iid coordinates from $N(0,1)$. For $1 \le k \le n$, let $X_{(k)}$ be the value of the $k$th largest coordinate of $X$.
...
- 6,853
2
votes
1
answer
99
views
Concentration Inequality for Bounding Lipschitz Empirical Lass
Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, $(X_n:\Omega\rightarrow \mathbb{R}^m)_n$ be a sequence of i.i.d. random variables and let $L:\mathbb{R}^m\rightarrow [0,\infty)$ be ...
- 77
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
2
votes
2
answers
468
views
Concentration bound on maximum subset sum of standard Gaussians
Let $X_1, \dots, X_n$ be standard Gaussians. Let $\mathcal{S} \subseteq \{A \in 2^{\{1, \dots, n\}} : |A| = k\} $ be a family of subsets of $\{1,\dots, n\}$ with fixed size $k$. [Note that $\mathcal{S}...
- 151
2
votes
1
answer
287
views
Bernstein Inequality for continous local martingale
I'm looking for a simple proof of the following fact, which is somehow Bernstein inequality in continuous time.
Let $(M_t)_{t\geq 0}$ be a continuous local martingale. Then :
$$P\left(\sup_{t\in [0,...
- 245
2
votes
1
answer
847
views
Concentration inequality for quadratic form of Gaussian variables with non-idempotent matrix
Given $y \sim N(0,\sigma^2 I)$, and $M$ that is a symmetric matrix (not necessarily idempotent)
what is the distribution of ${y^T M y}$?
is there a high probability bound on $|{y^T M y}|$?
Most ...
- 123
2
votes
1
answer
172
views
Symmetry of concentration bounds on mean
Question summary:
If I have a two-sided bound, can I immediately get a one-sided bound with tighter constants?
Question details:
Let $\mathbf X = X_1,...,X_n$ be $n$ i.i.d. real-valued random ...
- 399
2
votes
2
answers
291
views
How many boxes so that there is $k$ of same of color from $n$ different colors?
Say you have $m$ boxes each of which is colored with one of $n$ colors. What should $m$ be so that the probability that there is atleast $k$ boxes with one same color is strictly greater than $\frac{1}...
- 13.9k
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
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
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
1
answer
462
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^{\...
- 163
2
votes
1
answer
335
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 ...
- 331
2
votes
2
answers
228
views
Minimal conditions on random vector $X \in R^n$ to ensure that $\lim_{t\to 0^+}\sup_{\|w\|_p = 1}\sup_{u \in \mathbb R}\mathbb P(|X'w-u| \le t)=0$
Let $X$ be a random variable on $\mathbb R^n$ and let $S_p^n := \{w \in \mathbb R^n \mid \|w\|_p = 1\}$ be the unit-sphere w.r.t to the $\ell_p$-norm in $\mathbb R^n$. We will be particularly ...
- 6,853
2
votes
1
answer
90
views
Asymptotics of $w^\top G^2 w$, where $w$ is a unit-vector, $G:=X^T(XX^T+t I_n)^{-1}X$, $t > 0$, and $X$ is an $n\times d$ gaussian random matrix
Let $X$ be an random $n \times d$ matrix with entries drawn iid from $N(0,1/d)$ and let $w$ be a unit-vector in $\mathbb R^d$. With $\lambda>0$, and define $G:=X^\top(XX^\top + \lambda I_n)^{-1}X$. ...
- 6,853
2
votes
1
answer
187
views
Compute the limit of trace of inverse of square of rank-1 perturbation of Wishart matrix
Let $a \ge 0$, $b,c>0$ be fixed constants, and let $X$ be an $m \times d$ random matrix with entries drawn iid from $N(0,1/d)$. Consider the random psd matrix $S := a 1_m 1_m^\top + b XX^\top + c ...
- 6,853
2
votes
1
answer
240
views
Lipschitz condition with respect to operator norm of a Gaussian matrix with iid entries. Improved Gaussian Poincare Inequality?
The Gaussian Poincare inequality says that if $q:R^n\to R$ is Lipschitz (for simplicity you may additionally assume smooth with compact support), then $Var[f(X)] \le L^2$
for $X\sim N(0,I_q)$.
Now ...
- 1,724
2
votes
1
answer
302
views
Concentration on discrete probability estimator
Let $t>1$ and $X_1,..., X_t$ a set of real random variables from a discrete distribution, whose pmf is $p(x)$, supported on the points $1,...,k$.
Let $N_t(x) = \sum_{i = 1}^t \mathbb{1}_{X_i =\, x}....
- 245
2
votes
1
answer
180
views
Generalization of Komlós–Major–Tusnády Approximation
The Komlós–Major–Tusnády Approximation (see Wikipedia) considers the sum of uniform variables in $(0,1)$. There are also version where instead the sum of equiprobable $0/1$ variables is used ($p=1/2$)....
- 23
2
votes
1
answer
326
views
What is the Wiener measure of the curves with Hölder index $\frac 1 2$?
One may show that the Wiener measure (for curves in $\mathbb R^n$) is concentrated on the Hölder-continuous curves of Hölder index $< \frac 1 2$. What happens to the curves of Hölder index ...
- 5,407
2
votes
1
answer
167
views
Concentration of emperical conditional probability
Assume sequence $(X_1,X_2, X_3, \ldots)$ is a first-order Markov sequence of real random variables where $X_i \in \mathcal{X}$ for some alphabet $\mathcal{X}$ of finite size $k$. Define emperical ...
- 33
2
votes
2
answers
1k
views
Lower bound on number of samples for an epsilon delta approximation matching the Chernoff bound
So we have two biased coins, one comes out head w.p. $1/2+\epsilon$ and the other w.p. $1/2-\epsilon$. How many times should we flip these two coins to be able to tell them apart w.p. at least $\delta$...
2
votes
1
answer
272
views
How to compute bounding coefficients for McDiarmid's inequality?
I am trying to understand the proof in Sec. A2 of Gretton et al.. To make the question self-contained, I summarize below the key ingredients. At the end of the post, I state my question.
Given a ...
2
votes
1
answer
886
views
Asymptotic behavior of a ratio of sums of iid random variables
Let $X_i$ and $Y_i$ be distributed identically to $X$ and $Y$, respectively. Assume both $X$ and $Y$ take strictly positive values.
Consider the random variable $R_n \doteq \frac{\sum_{i=1}^n X_i}{\...
- 143
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
2
votes
1
answer
150
views
Normalized concentration inequality for empirical CDF (iid sum)
Consider the empirical and population CDF,
$$
F_n(t) = \frac{1}{n} \sum_{i=1}^n 1\{X_i \leq t\} \quad \mbox{and} \quad
F(t) = \mathbb{E} [F_n(t)],
$$
where above $X_1, \dots, X_n$ are iid, real-...
- 370
2
votes
1
answer
938
views
Upper-bound for spectral norm of the covariance matrix of a certain Gaussian vector with correlated entries
Let $n$ and $m$ be large positive integers. Let $x=(x_1,\ldots,x_n)$ be a vector of independent random variables from $N(0,1)$. It is clear that the covariance matrix of $x$ is $I_n$, the identity ...
- 6,853
2
votes
1
answer
165
views
Existence of preferred direction for a random vector with arbitrary distribution on sphere, under a condition on its covariance matrix
Let $X$ be random vector on the unit-sphere $S_{n-1}$ in $\mathbb R^n$. We don't assume that the distribution of $X$ is uniform on $S_{n-1}$
I'm interested in proving the existence of a (...
- 6,853
2
votes
1
answer
116
views
A question on the applicability Chebyshev inequality for sequence of random quantities
Let $(X_n)_n$ and $(Y_n)_n$ be two mutually independent sequences of random tensors (i.e scalars, vectors, matrices, etc.) defined on the same probability space, and let $f$ be a measurable function.
...
- 6,853
2
votes
1
answer
304
views
An approximation problem w.r.t marginal distribution of coordinates of uniform random vector on high-dimensional unit-sphere
Let $X=(X_1,\ldots,X_d)$ be uniformly distributed on the sphere of radius $\sqrt{d}$ in $\mathbb R^d$. Fix a "sufficiently integrable" function $h:\mathbb R \to \mathbb R$, and define ...
- 6,853
2
votes
1
answer
114
views
Reweighting probability measures by convex potentials, and contraction in transport distance
Let $W: \mathbf{R}^d \to \mathbf{R}$ be a convex function such that $\int \exp(-W) = 1$, and define probability measures $\mu_y$ by
$$\mu_y (dx) = \exp( - W (x - y)) \,dx,$$
i.e. each $\mu_y$ is a ...
- 801
2
votes
1
answer
212
views
Prove / disprove: If $1 \le n < N$ and $A$ is an $N \times n$ matrix with iid from $\mathcal N(0,1)$, then $s_\min(A) \ge c\sqrt{N}$ w.p $1-2e^{-N}$
Let $1 \le n < N$ be integers and $A$ be a random $N\times n$ matrix with iid entries from $\mathcal N(0,1)$. This paper (Rudelson and Vershynin) claims in the paragraph just before formula (3.4) ...
- 6,853
2
votes
2
answers
539
views
Chaining tail bound for centered sub-Gaussian process?
On page 5 of a recent manuscript by Lugosi-Mendelson, a claim equivalent to the following statement is made:
Suppose $Z$ is a centered, $\mathbf{R}^d$-valued random variable with $\mathbf{E} e^{\...
- 370
2
votes
1
answer
187
views
Unconditional lower bound for volume of blowup $\mu(B^\epsilon)$ for $\mu(B) \in (0, 1)$ and $\epsilon > 0$ not "too large"
For a Borel subset $B$ of a metric space $X = (X,d)$ and $\epsilon>0$, recall the defintion of the $\epsilon$-blowup of $B$, namely $B^\epsilon = \{x \in X | d(x,B) \le \epsilon\}$. Let $\mu$ be a ...
- 6,853
2
votes
1
answer
508
views
Extension of Gordon's comparison inequality to subgaussian processes?
"Theorem A" in this paper by Y. Gordon:
http://www.math.uiuc.edu/~mjunge/Comps/Gordonm.pdf
is a comparison inequality for Gaussian processes:
Is there an analogue of this result for subgaussian ...
- 517
2
votes
1
answer
439
views
Upper bound on the maxima of ratio of expectation of quantities under Gaussian measure
Let $\lambda,\eta >0$ be given, and $u:\mathbb{R}\rightarrow \mathbb{R}$ be a real valued function. Define
$$\Delta(u)= \frac{\int u(h) \exp(-\eta u(h))\exp(-\frac{\lambda}{2}h^2)~\mathrm{d}h}{\...
- 323
2
votes
1
answer
635
views
Azuma's Inequality when the conditions hold with high probability?
In Azuma's Inequality, is the statement true when $|X_k - X_{k-1}| < c_k$ almost surely rather than with probability 1? If not, is there another result which gives strong concentration when the ...
- 201
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
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
129
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
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