The tag has no usage guidance.

learn more… | top users | synonyms

2
votes
0answers
26 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 ...
7
votes
2answers
166 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
0answers
22 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
2answers
312 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
1answer
192 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 ...
2
votes
1answer
128 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 ...
2
votes
0answers
91 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 ...
7
votes
1answer
473 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
0answers
104 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 ...
2
votes
0answers
112 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 ...
4
votes
0answers
126 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
1answer
88 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 ...
1
vote
0answers
71 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
2answers
108 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
0answers
117 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
1answer
120 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
0answers
74 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
0answers
221 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
4answers
139 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
1answer
99 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
0answers
87 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
1answer
92 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
0answers
90 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
0answers
103 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
0answers
92 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
1answer
106 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 ...
1
vote
0answers
60 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
1answer
93 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
1answer
444 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
0answers
102 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 ...
5
votes
1answer
369 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$ ...
2
votes
0answers
94 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*} ...
3
votes
1answer
153 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
0answers
87 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
2answers
346 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 ...
7
votes
1answer
211 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 ...
3
votes
1answer
225 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 ...
5
votes
2answers
750 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
1answer
237 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 ...
2
votes
1answer
329 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
0answers
71 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 ...
5
votes
1answer
186 views

concentration of random matrices involving normal random variables

Define the random variable \begin{align*} A=|a_1|^2\mathbf{a}\mathbf{a}^* \end{align*} where $\mathbf{a}\in\mathbb{c}^n$ is a random vector distributed as ...
3
votes
1answer
147 views

Variance of maximum of mixture of gaussians

Let $\{X_i\}$ be an iid collection of standard normal $(N(0,1))$ random variables . Let $X = (X_1,\ldots,X_n)$, and consider a function of the form $f(X) = \max(A\cdot X)$, where $A$ is some ...
10
votes
4answers
514 views

More than $n$ approximately orthonormal vectors in $R^n$

This question was asked at math.stackexchange, where it got several upvotes but no answers. It is impossible to find $n+1$ mutually orthonormal vectors in $R^n$. However, it is well established ...
5
votes
2answers
428 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 ...
1
vote
0answers
74 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: ...
2
votes
1answer
212 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 ...
1
vote
0answers
226 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 ...
2
votes
1answer
146 views

What is the spectral norm of a random projection times a diagonal?

Take $n\ll N$. Let $P$ be an $n\times N$ matrix of iid $\mathcal{N}(0,1)$ random variables, and let $D$ be an $N\times N$ diagonal matrix. What can be said about the distribution of the largest ...
2
votes
2answers
239 views

Asymptotic Expansion of Distribution in Central Limit Theorem for Non-Identically Distributed Random Variables

My question is related to the following theorem (e.g. Section XVI.4 of Feller's 1971 book): Let $Z_i$ $(i=1,\cdots,n)$ be independent and identically distributed random variables with mean zero, ...