The measure-concentration tag has no usage guidance.

**1**

vote

**0**answers

73 views

### relative chernoff bound

Is the following true? Is there a contradicting example?
Let $x_1,\ldots,x_n$ be independent random "bits", with $\forall u:\Pr[x_i=u]\in\{0,\frac{1}{2}\}$. Denote $x=\sum_i x_i$, and assume $\mathrm{...

**5**

votes

**1**answer

181 views

### Concentration bounds on weighted sum of i.i.d. Bernoulli random variables

Let $X_1,\dots, X_n\sim\operatorname{Bern}(\frac{1}{2})$ be independent, identically distributed random variables, and $\alpha=(\alpha_1,\dots,\alpha_n)\in[0,1]^n$ a vector of non-negative weights ...

**2**

votes

**0**answers

124 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{...

**7**

votes

**1**answer

273 views

### Level sets of weakly differentiable funtions

Let $C$ be a $C^1$ hypersurface in $R^n$ and let $u \in C^1(R^n)$. Suppose
$$\nabla u(x) \cdot \eta(x)=|\nabla u| \ \ \forall x\in C$$
where $\eta(x)$ is the normal vector to $C$ at $x$ ($\nabla u$ ...

**0**

votes

**0**answers

49 views

### Matrix concentration inequality

Let $X \in \mathbb{R}^{n \times d}$ be a fixed matrix and $W \in \mathbb{R}^{n \times d}$ be a random matrix with elements $w_{ij} = x_{ij} + \epsilon_{ij}$, where $\epsilon_{ij}$ are iid subgaussian ...

**4**

votes

**1**answer

55 views

### Concentration of U-statistics for exchangable distributions (and the unbounded case)

Consider the following so-called $U$-statistic of order 2: $$U = \frac1{\binom{m}{2}} \sum_{i < j} h(w_i,w_j)$$ where $w_1,\dots,w_m$ are IID from some distribution and $h$ is symmetric. If $|h(w_1,...

**4**

votes

**2**answers

155 views

### Expected value of Bernoulli quadratic forms

Let $\mathbf{Y}\in\mathbb{R}^{n\times n}$ be a symmetric matrix. Let $\mathbf{x}\in\mathbb{R}^n$ be random vectors with entries i.i.d. $\pm 1$ with equal probability. I'm interested in a lower bound ...

**1**

vote

**1**answer

73 views

### Upper tail concentration of sample covariance matrices

I'm interested in concentration of the following random matrix sum in spectral norm
$\frac{1}{m}\sum_{k=1}^m b_k^2\mathbf{a}_k\mathbf{a}_k^*$
Here $\mathbf{a}_k\in\mathbb{R}^n$ are i.i.d. standard ...

**1**

vote

**0**answers

65 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-...

**2**

votes

**0**answers

34 views

### tail bounds for sum of n iid variables divided by power of n

Let $X_i, 1\leq i\leq n$ be i.i.d. random variables with finite moments. Then $Y_n :=\frac{1}{n^{1+\delta}}\sum_{i=1}^nX_i$ goes to 0 almost surely for any $\delta >0$. What are some good non-...

**7**

votes

**2**answers

192 views

### concentration inequality for entropy from sample

Consider a measure $\mu$ on a finite set, and let $x_1, \ldots, x_n$ be i.i.d samples from $\mu$. Then the expression $S_n = -\frac{1}{n} \sum_{i=1}^n \log \mu(x_i)$ converges by a.s. to the entropy $...

**0**

votes

**0**answers

40 views

### Existence of optimal coupling in optimal transport

Let $P,Q$ be any two distributions over a space $\mathcal{X}$ and let $\mathcal{M}(P,Q)$ be the set of all couplings of $P$ and $Q.$ For a given metric $d$ over $\mathcal{X},$ the optimal transport ...

**9**

votes

**2**answers

349 views

### Adaptive version of the Azuma–Hoeffding inequality

The Azuma inequality states that if we have a martingale $X_1,\ldots,X_N$ that satisfies a bounded difference condition:
$$|X_k - X_{k-1}| \leq c_k$$
Then:
$$\Pr\left[X_N - X_0 \geq \sqrt{2\sum_kc_k^2 ...

**4**

votes

**1**answer

206 views

### Tail bounds on eigenvalue gaps for GUE

What I'm looking for is a non-asymptotic bound on the probability that the smallest gap between eigenvalues of a GUE matrix does not exceed a certain value.
I'm aware of the bounds in
http://imrn....

**2**

votes

**1**answer

157 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}{\...

**2**

votes

**0**answers

98 views

### Intuitive (?) inequality extremal inequality

Consider $N$ pairs of random variables $(X_i, Y_i)$. $X_i$ are iid, with $EX_i=0$ and $EX_i^2=1$. The same conditions hold for $Y_i$. Moreover all $X_i$ are independent of all $Y_j$. It seems very ...

**8**

votes

**1**answer

740 views

### Doob Martingale: Where is the catch?

I am working on a research problem in uncertainty propagation that involves sums of possibly dependent random variables with bounded sets of support.
I am attempting to use the method of bounded ...

**3**

votes

**0**answers

111 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$...

**2**

votes

**0**answers

125 views

### Convergence rate of Pearson correlation matrix

I am interested in (rather sharp if not the finest) tail/concentration bounds for the Pearson correlation matrix: let $X_1,\ldots,X_N \sim \mathcal{N}(0,1)$ be correlated random variables; let $\rho(...

**3**

votes

**0**answers

131 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 ...

**4**

votes

**1**answer

97 views

### Concentration of spectral norm

Let $X_{ij}$ be independent (but not identically distributed) real-valued random variables for $1\leq i\leq j\leq n.$ Let $X$ be the symmetric matrix whose entries are given by $X_{ij}.$ Let
\begin{...

**1**

vote

**0**answers

97 views

### concentration inequalities for quadratic forms of correlated random vectors

Let $\mathbf{n}$ is a Gaussian random vector with mean $\mathbf{0}$ and co-variance matrix $\mathbf{H}$. Let $\mathbf{r} = Sign(\mathbf{n})$, where $Sign(n_i) = 1$ if $n_i>0$ and $Sign(n_i) = -1$ ...

**4**

votes

**2**answers

117 views

### Do subgaussian variables obey the slightly-stronger-than-Chernoff tail bound?

If $X \sim Normal(0,1)$, then we have the tail bound:
$$ (*) \qquad\Pr[X > t] \leq \mathcal{O}\left(\frac{e^{-t^2/2}}{t}\right) .$$
Now for general variables $X$, a nice condition is that $X$ be ...

**2**

votes

**0**answers

130 views

### Tail bounds for suprema of random processes

Classical results concerning concentration of Gaussian random variables due to Cirelson, Ibragimov and Sudakov say that if $V_1,\cdots,V_n$ are jointly Gaussian with variance bounded by $1$, then (...

**2**

votes

**1**answer

131 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 ...

**3**

votes

**0**answers

81 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 ...

**2**

votes

**0**answers

226 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 ...

**7**

votes

**4**answers

179 views

### What can be said about the concentration of measure of product of Gaussian variables?

I have a set of random variables $X_1,\ldots,X_n$, all Gaussian with mean 0 and variance 1, indepedent. Let $p(x_1,\ldots,x_n)$ be some polynomial that takes products and sums of $x_1,\ldots,x_n$.
...

**3**

votes

**1**answer

111 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, ...

**0**

votes

**0**answers

113 views

### What is the concentration of measure for Gaussian random variables which are independent, but are transformed?

This might be a too easy question for Mathoverflow, but Googling led to similar questions and answers here (though not the one I was looking for).
The question is split into two:
I have a matrix $X ...

**0**

votes

**1**answer

93 views

### Question about measure lemma?

"Let (u_j) be a bounded sequence from $W^{1,p}(\Omega)$ how to prove that there exists a subsequence such that $u_j\rightharpoonup u$ in $W^{1,p}_0(\Omega)$ and $|\nabla u_j|\rightharpoonup d\mu,$ $|...

**2**

votes

**0**answers

96 views

### Concentration bound in high min entropy distribution

Let $(X_{1},\dots,X_{m})$ be joint distribution on $\{0,1\}^{m}$ with that $H_{\infty}(X_{1},\cdots,X_{m})\geq m-r$, where $H_{\infty}$ means min-entropy.
Let $P_{1},...,P_{n}\subseteq [m]$ be sets ...

**1**

vote

**0**answers

109 views

### Does Newtonian capacity increase strictly when mass is spread?

We start with two disjoint compact sets A and B with positive capacities. Then, we translate B s.t. $B+rv$ is disjoint from A and B and ,more importantly, $dist(x,y)<dist(x,y+rv)$ for all $x\in A$ ...

**5**

votes

**0**answers

108 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 ...

**1**

vote

**1**answer

114 views

### Concentration bound for a martingale-like setting (the expected difference decreases as the sequence increases)

I went through several martingales concentration bounds, but none of them fit the settings I am interested in, which is the following. Suppose I have a sequence of nonnegative random variables $0=Y_{0}...

**1**

vote

**0**answers

63 views

### Tools to bound the singular values of a finite sum of random matrices from below?

Matrix Chernoff bounds (see also this arXiv paper) are usually used to give upper bounds on the largest eigenvalue of a finite sum of random matrices. Sometimes it can also be used to give a lower ...

**0**

votes

**1**answer

96 views

### reverse FKG type inequality for slightly correlated Gaussian vectors

Let $X$ be a $m$-dimensional Gaussian vector, and $Y$ a $q$-dimensional Gaussian vector, for some $m,q\geq 1$. Assume that the $X_i$ and $Y_j$ are centred and have unit variance. Assume that $E X_i ...

**1**

vote

**1**answer

541 views

### Hoeffding's inequality for vector valued random variables

Is there a version of Hoeffding's inequality for vector valued random variables?
This seems to be hard to find and I wonder why. I suppose it is difficult to show Hoeffding's lemma, since the proof ...

**4**

votes

**0**answers

104 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}[...

**5**

votes

**1**answer

405 views

### Expectation of ratio of functions of i.i.d. Bernoullis: a concentration question

Consider the following $n \times n$ symmetric matrix of i.i.d. Bernoulli random variables, $X_{ij}$. For $i=1,...,n$ and $i<j\le n$. Let $X_{ij} \sim \text{Bernoulli}(p)$ when $i \ne j$ ($p$ fixed)...

**2**

votes

**0**answers

98 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^{...

**3**

votes

**1**answer

158 views

### Strictly positive solutions of a random linear system

Suppose $B\in\mathbb{R}^{m\times n}$ is a random binary matrix with i.i.d entries and $c\in \mathbb{R}^m$ is a strictly positive vector, that is $c_i>0$ for $i=1,2,\cdots m$. Also assume $m<n$, ...

**4**

votes

**0**answers

92 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}...

**3**

votes

**2**answers

357 views

### Measure concentration for law of large numbers

The classical law of large numbers states that
$$\frac1k\sum_{i=1}^k X_i \rightarrow \mathbb{E} X_1$$
for i.i.d. $X_1, X_2, \ldots$ with finite $L^1$ norm.
I was wondering whether is it possible to ...

**8**

votes

**1**answer

264 views

### Bounds on the moments of the binomial distribution

I'm looking for simple and reasonably tight bounds on the k-th moment of the Binomial distribution $B(n,p)$, namely, $E[B(n,p)^k]$. I'm interested in the case when k is large (say on the order of $\...

**4**

votes

**1**answer

239 views

### Concentration inequalities in $\ell_{\infty}$ for sums of iid random (“nice”) functions?

I'm looking for "tail-bound-like" inequalities that look like this (I state a specific setting but more general settings are interesting):
Let $D$ be a distribution on a set of "nice" functions $g$...

**6**

votes

**2**answers

864 views

### Extension of the Azuma-Hoeffding inequality (when the differences are bounded with large probability)

Let $(X_i)$ be a super-martingale and suppose their differences are bounded ''with high probability'', that is
$$\mathbb{P}(\exists\,i=1,\dots,n\text{ s.t. }|X_i-X_{i-1}|>c_i) \,\leq\, \epsilon$$
...

**8**

votes

**1**answer

269 views

### Concentration of sum of powers of normals

Let $Z_1,Z_2,\ldots,Z_n$ be i.i.d. copies of a random variable $Z$ distributed as $\frac{1}{\sqrt{2}}X+i\frac{1}{\sqrt{2}}Y$ with $X$ and $Y$ independent standard Normal random variables i.e.~$X\sim\...

**2**

votes

**1**answer

332 views

### Derive concentration bound for the derivative

It that true to conclude that if a random $f(z)$ is a sub-Gaussian random variable for a constant value of z, its derivative $f'(z)|_{z=k}$ with respect to variable $z$ is also sub-Gaussian?
In ...

**0**

votes

**0**answers

116 views

### Concentration bound for $f(w) = w \times \sin wz$

I need to find an exponential bound for $P(|S_n - \mu| > \lambda)$ where $S_n = \frac{1}{D} \sum_{i=1}^D w_i \sin w_iz$ for a constant $z$, $E(S_n) = \mu$ and $w_i$ are drawn from the normal ...