All Questions
Tagged with measure-concentration pr.probability
116 questions with no upvoted or accepted answers
12
votes
0
answers
489
views
Is this extension of Hoeffding's inequality known?
Question Overview:
Is it already known that, when using Hoeffding's inequality to lower bound the mean of i.i.d. random variables, you can replace the upper bound on the random variables with the ...
- 399
9
votes
0
answers
1k
views
Balls and bins -- concentration bounds pertaining to the minimal load bin
Consider the standard balls and bins process, where $m$ balls are thrown uniformly at random into $n$ bins. Previous work has been done on estimating the value of the maximum load (i.e., the number of ...
- 201
7
votes
0
answers
759
views
Product of two random Gaussian matrices - orthant probability
Let $X \in \mathbb{R}^{m \times n}$ and $Y \in \mathbb{R}^{n \times k} $ be two independent Gaussian random matrices, i.e., with entries independently sampled from $\mathcal{N}(0,1)$ (a normal ...
- 968
6
votes
0
answers
273
views
Question about size-biased couplings and concentration of the number of collisions
Edit/Update: I was indeed missing something quite obvious. I assumed the notion of collision used was the one I am used to (number of pairwise collisions, so if a bin received $k$ balls then this ...
- 1,372
6
votes
0
answers
554
views
a variation on Hanson-Wright inequality
The classic Hanson-Wright inequality states that for a Gaussian random vector $\mathbf{x}\in\mathbb{R}^n$ distributed as $\mathcal{N}(\mathbf{0},\mathbf{I})$ and $\mathbf{A}\in\mathbb{R}^{n\times n}$ ...
- 859
6
votes
0
answers
337
views
Chernoff bound in the not-quite-sub-exponential case
In Terry Tao's notes on Concentration of measure, Exercise 7 indicates that the Chernoff bound can be generalized to sub-exponential random variables:
http://terrytao.wordpress.com/2010/01/03/254a-...
- 7,633
5
votes
0
answers
266
views
Concentration inequalities for random measures
For random variables $X_1,\dots,X_n$ with common mean $\mathbb{E}[X_i]=\mu$ and common bounds $a\leq X_i\leq b$, we have the very useful Hoeffding's inequality:
$$\mathbb{P}\left(\left|\mu -\frac1n\...
- 101
5
votes
1
answer
1k
views
Explicit constant for Carbery–Wright inequality
The Carbery–Wright inequality is a seminal result about the anti-concentration of polynomials of Gaussian random variables.
See e.g. Meka, Nguyen, and Vu - Anti-concentration for polynomials of ...
- 111
5
votes
0
answers
711
views
Concentration inequality for max component of a multivariate Gaussian in the general case
I am looking to bound the variance of the maximum component of a vector distributed multivariate Gaussian in the general case where the Gaussian distribution has arbitrary mean and full covariance ...
- 283
5
votes
0
answers
1k
views
Asymptotic behavior of row sums in 2-d array of random variables
Set-up. Let $f : \mathbb{N} \to \mathbb{N}$ be increasing. For each $m \in [0,1]$, consider an infinite two-dimensional array of random variables, where row $n$ has $f(n)$ variables:
$B^m_{1,1}$ $B^...
- 61
5
votes
0
answers
543
views
Vector martingale concentration
Let $\varepsilon_1, \dots, \varepsilon_N$ be a martingale difference sequence in $R^d$ with $\|\varepsilon_n\| \le B_n, a.s.$ for each $n=1,\dots,N$. Do we have some Azuma-type concentration ...
- 719
5
votes
0
answers
143
views
Is there a concentration inequality depending on dimension for a symmetric function on product space?
I recently read an elegant paper of Bobkov
Bobkov, S.G., On concentration of measure on the cube, J. Math. Sci., New York 165, No. 1, 60-70 (2010); translation from Probl. Mat. Anal. 44, 55-64 (2010)....
- 747
5
votes
0
answers
169
views
McDiarmid-like inequality for subgassian random variables
Let $X_n$ be a set of $N$ subgaussian random variables, not necessarily independent, with $E\exp(\lambda X_n) \le \exp(\lambda^2/2)$. Let $X=(X_1,\ldots, X_N)$ and $f:\mathbb R^N \rightarrow \mathbb R$...
- 461
5
votes
0
answers
138
views
Improving concentration estimates by controlling sums on subsets
Let $X_1, \dots, X_N$ be uniform random variables (r.v.) in $[-1, 1]$, and let $S_N$ be their sum $S_N = \sum_{i=1}^N X_i$.
If the r.v. are taken independent, then the CLT suggests that $S_N$ is ...
- 121
5
votes
0
answers
327
views
Eigenvalues of Random Regular Bipartite Graphs
I am looking for a way of getting a good estimate of the eigenvalues of random bipartite d-regular graphs. The literature has very precise values the proofs of which are very involved and since I am ...
- 161
5
votes
0
answers
137
views
Large Deviations: Exponential decay in normed spaces
Let $(X_1,X_2,\cdots)$ be a sequence of independent and identically distributed random variables taking values in some general normed space $(V,||\cdot||)$. Denote $\mu=E[X_1]$ and $S_n=\frac{1}{n}[...
- 619
5
votes
0
answers
117
views
Concentration of weighted random chirp
I'm interested in seeing whether the following is true. Assume $u$ is uniform on $[0,1]$. For a fixed $x\in\mathbb{C}^n$ with $\|x\|_{2}=1$ we have
\begin{align*}
\mathbb{P}\Big\{\Big|\sum_{k=0}^{n-1}...
- 859
5
votes
0
answers
397
views
Concentration of functions of random unitary matrices
Suppose $U$ and $V$ are $n \times n$ random unitary matrices, chosen independently from the Haar measure. Is there any kind of concentration inequality which would be applicable to polynomials $p(U,V)$...
- 2,449
4
votes
0
answers
638
views
Comparison of concentrations of different $L^p$-norms of (sub) Gaussian distributions
It's well-known that the Euclidean $2$-norm of subgaussian random vectors concentrates in high dimensions, e.g. when $X \sim \mathcal{N}(0,I_n),$ (or in general $X$ is subgaussian with independent co-...
- 1,467
4
votes
0
answers
143
views
For a martingale $f_0,f_1,\ldots $ how can we bound $P(\frac{1}{n} \|f_n\| \le 1$ for all $ n \ge N)$?
Suppose $f_0,f_1, \ldots$ is a martingale (or i.i.d sequence) in $\mathbb R^d$ with $f_0=0$ and all $\|f_n - f_{n-1}\| \le L$ say. There are many concentration results for the initial segment of the ...
- 1,955
4
votes
0
answers
162
views
Are sums extremal for subgaussian concentration?
Bobkov and Houdre https://projecteuclid.org/euclid.bj/1178291721
showed that among all $f:R^n\to R$ that are $1$-Lipschitz
with respect to the $\ell_1$ metric,
the variance is maximized by sums. ...
- 6,541
4
votes
0
answers
93
views
On symmetry and measure concentration rate for convex bodies
The concentration of measure on the cube $ [0, 1]^n $ equipped with uniform probability measure $\mu_{\infty}$,
states that for any $A \subset [0, 1]^n $ with $ \mu_{\infty}(A) \geq \frac{1}{2} $,
we ...
- 365
4
votes
0
answers
141
views
Is there an example that both Berry-Essen bound and DKW bound are attained?
The Berry-Essen bound stated that
$$\sup _{{x\in {\mathbb R}}}\left|\widehat{F_{n}(x)}-\Phi (x)\right|\leq C_{0}\cdot \psi _{0}$$
where $\psi _{0}(n)={\Big (}{\textstyle \sum \limits _{{i=1}}^{n}\...
- 8,071
4
votes
0
answers
162
views
Concentration Inequality for Score Functions of Exponential Familty
Let $p$ be the density of a continuous one-parameter exponential family distribution on $\mathbb{R}$. We assume that
$$p(x) = c(x)\cdot \exp\bigl [ x \cdot \theta - b(\theta ) \bigr ], $$
where $\...
- 1,127
4
votes
0
answers
76
views
How well does an estimator perform on another dataset?
Suppose $X \sim N(0, \Sigma)$ is a $d$-dimensional Gaussian random vector. And we have $2n$ $i.i.d$ sample $X_1, \ldots, X_{n}, \ldots, X_{2n}$.
Let $\hat{\Sigma}_1 = \frac{1}{n}\sum_{i=1}^nX_i X_i^\...
- 515
4
votes
0
answers
416
views
concentration of functions of Gaussian processes
Let $\mathcal{C}\in\mathbb{R}^n$ be a subset of the unit ball. Also let $\mathbf{a}_1,\mathbf{a}_2,\ldots,\mathbf{a}_m\in\mathbb{R}^n$ be i.i.d. random Gaussian vectors $\mathcal{N}(\mathbf{0},\mathbf{...
- 859
4
votes
0
answers
1k
views
Concentration of sum of independent random variables
Let $X_1, ..., X_n$ be i.i.d. sub-Gaussian random variables with mean $0$ and variance $1$. That is, we have $\Pr[|X_i| > t] \leq \exp(1-t^2/K^2)$ for all $t>0$ and a parameter $K$.
Then we can ...
- 1,324
3
votes
0
answers
92
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
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
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
3
votes
0
answers
334
views
Tail bound on trace norm / nuclear norm / Schatten-1 norm of Rademacher matrix
Let $0 < r \leq d$ integers. Let $X$, $Y$ be $d \times r$ matrices of independent Rademacher variables, that is, $X,Y \in \mathbb{R}^{d \times r}$ with entries $\pm1$ with probability $1/2$. I am ...
- 223
3
votes
0
answers
93
views
Explaning why the spectrum of a setting simple structure random matrix is always spiked ($d-1$ eigenvalues close to zero, and $1$ away from zero)
For concreteness, let $m=500$, $d=600$, $N=1000$. Let $W$ be and $d \times m$ matrix with unit-norm rows and let $u$ be a uni-norm vector of length $m$. Given a binary vector $b$ of length $m$, length ...
- 6,853
3
votes
1
answer
373
views
Concentration of very dependent Markov chains
Consider the following simple Markov chain $ X_1\to X_2\to\cdots\to X_n $ where each $X_i$ is $\{-1,1\}$-valued and $X_1\sim\mathrm{Unif}(\{-1,1\})$ (such that the chain is stationary).
The flip ...
- 161
3
votes
0
answers
83
views
Ornstein-Ulhenbeck like semigroup for the orthogonal group with a hypercontractive inequality
I am looking for an Ornstein-Uhlenbeck like semigroup $P_t$ and associated generator $\mathcal{L}$ on $G = \operatorname{SO}(n)$ or $\operatorname{O}(n)$ that has a hypercontractive inequality with a ...
- 941
3
votes
1
answer
379
views
Concentration inequality for norm of solution to nonlinear least-squares problem
Define the piecewise-linear function $\psi(t):=\max(t,0)$ for all $t \in \mathbb R$.
Let $d,n,k \to \infty$ at the same rate (i.e $n \asymp k \asymp d$).
Let $y_1,\ldots,y_n \in \{-1,1\}$ uniformly ...
- 6,853
3
votes
0
answers
103
views
Concentration inequalities for gradient flows induced by random fields
Let $G=(G(x))_{x \in \mathbb R^m}$ be a conservative random field with values in $\mathbb R^m$, for large positive integer $m$. That is, there exists a scalar random field $g=(g(x))_{x \in \mathbb R^m}...
- 6,853
3
votes
0
answers
307
views
Upper-bound for eigenvalues of $E [UU^T]$, where $U$ is uniformly distributed on the unit $n$-sphere
Let $X$ be a $\sigma$-subGaussian random vector on $\mathbb R^n$ (for large $n \ge 3$), meaning that the random variable $X^Tv$ is $\sigma$-subGaussian for every unit vector $v \in \mathbb R^n$. ...
- 6,853
3
votes
0
answers
187
views
Concentration Inequalities for the Exponential of Weighted Bernoulli Sums
I want a concentration inequality for the exponential of a weighted sum of independent Bernoulli random variables around its mean, for one of my research works. I was wondering if there is a well ...
- 123
3
votes
0
answers
166
views
Matrix Chernoff sampling with out replacement
I am interested to know if the matrix Chernoff bound (see Theorem 5.1.1 in https://arxiv.org/pdf/1501.01571.pdf) holds if one samples without replacement.
For example, the Bernstein inequality is ...
- 221
3
votes
0
answers
77
views
A concentration problem of product of matrices
Let $A$ be an $n \times m$ matrix with non-negative entries and $B \in \mathbb{R^{n\times n}_{\geq 0}}, C \in \mathbb{R^{m\times m}_{\geq 0}}$ be random matrices where B and C are both symmetric and ...
- 195
3
votes
0
answers
186
views
Anti-concentration for sum of t-wise independent uniform variables
Let $X_{1},\ldots,X_{n}$ be i.i.d. random variables, each variable is uniform over the set of integers $\{ 0,\ldots,D-1 \}$. Let $S = \sum_{i=1}^{n}X_{i}$.
By ``small ball probability'', we have that ...
- 225
3
votes
0
answers
125
views
Concentration of sums of random matrices around the mean, in the Loewner order
Recently, I have found myself interested in concentration properties of random matrices.
Specifically I would like to answer questions of the following sort
Let $\{X_i\}_{i=1}^n$ be i.i.d. copies ...
- 393
3
votes
0
answers
451
views
concentration bounds on weighted multinomial sum
Consider i.i.d random vectors $Y_{1},..,Y_{n}$ and they are chosen uniformly at random from $\{e_{1},..,e_{L}\}$ where $e_{i}$ is a $L\times 1$ vector with $i$th component be 1 and the others be 0. ...
- 31
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
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
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
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