The measure-concentration tag has no usage guidance.

**3**

votes

**2**answers

396 views

### Non-asymptotic large deviations for a convex set

Let $X_1,\dots,X_n$ be $n$ i.i.d random variables taking values in a Polish vector space $\mathcal{X}$ and with (Borel) probability distribution $\mu$.
For any convex, compact $\Gamma \subset ...

**5**

votes

**1**answer

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

**9**

votes

**0**answers

278 views

### How fast can extreme eigenvalues of the average of random matrices converge to their expectation?

Suppose that $X_1,X_2,\ldots,X_m$ are $m$ independent $d\times d$ random matrices and let $\overline{X} = \frac{1}{m}\sum_{i=1}^m X_i$. One of the questions studied under the theory of random matrices ...

**5**

votes

**0**answers

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

**5**

votes

**0**answers

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

**5**

votes

**0**answers

207 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:
...

**4**

votes

**0**answers

122 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

**0**answers

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

**3**

votes

**0**answers

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

**3**

votes

**0**answers

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

**3**

votes

**0**answers

85 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*}
...

**3**

votes

**0**answers

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

**2**

votes

**0**answers

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

**2**

votes

**0**answers

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

**2**

votes

**0**answers

108 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

**0**answers

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

**2**

votes

**0**answers

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

**2**

votes

**0**answers

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

**2**

votes

**0**answers

239 views

### Does Multiplicative Version of Azuma's Inequality Hold?

It is known that there are multiplicative version concentration inequalities for
sums of independent random variables. For example, the following
multiplicative version Chernoff bound.
Chernoff ...

**1**

vote

**0**answers

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

86 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*}
...

**1**

vote

**0**answers

69 views

### Small ball probabilities for functions of correlated normals

Let $f : \mathbb{R}^k \rightarrow \mathbb{R}$ and let $X$ be distributed k-dimensional normal with mean $0$ (with "arbitrary" covariance matrix). I am looking for references with bounds of the form: ...

**1**

vote

**0**answers

214 views

### Upper bound on expectations of the sum of product of a martingale difference sequence with a predictable sequence, weighted by certain random weights

Let $(\mathcal{F}_i)_{i\geq 1}$ be a filtration. Let $0\leq p_i\leq 1$, be a random variable measurable w.r.t. $\mathcal{F}_i$. Consider two sequences of random vectors ...

**1**

vote

**0**answers

157 views

### When does the effective concentration of measure does not occour on a Riemmanian manifold?

Introduction
Let $\mathcal{M}$ be a compact $m$ - dimensional Riemmanian manifold with normalized measure $\mu$ (derived from the metric). It is know that in this setting we have concentration ...

**0**

votes

**0**answers

76 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

**0**answers

58 views

### Restricted singular values of Wishart matrices

This is an extended question of
Restricted singular values of random matrix.
It is well-known that the smallest singular value of a $p \times \frac{p}{2}$ matrix consisting of i.i.d. ...

**0**

votes

**0**answers

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