The tag has no usage guidance.

learn more… | top users | synonyms

13
votes
0answers
348 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 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 is ...
11
votes
4answers
552 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 ...
10
votes
1answer
732 views

Non-probabilistic proof of the Johnson–Lindenstrauss lemma

The Johnson–Lindenstrauss lemma states that a small set of points in a high-dimensional space can be embedded into a space of much lower dimension in such a way that distances between the points are ...
9
votes
2answers
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 ...
9
votes
2answers
677 views

Concentration bounds for sums of random variables of permutations

I'm trying to find theorems regarding random variables derived from sampling permutations, specifically concentration bounds. As an example, let $X_i$ be the $\{0,1\}$-random variable that represents ...
8
votes
3answers
837 views

Counterexample of non-negative sequence weakly converging in $\mathscr{M}^1$ but not $L^1$

Hi. Consider a a sequence of non-negative functions $(f_n)_n$, bounded in $L^1([-1,1])$ and weakly$-\star$ converging in $\mathscr{M}^1([-1,1])$ to some $f\in L^1([-1,1])$. What I mean by this ...
8
votes
2answers
387 views

Supremum of measure of sets of measure less or equal to 1/2.

Let $(X,d)$ be a metric space equipped with a probability measure $\mu$ (defined on the Borel $\sigma$-algebra on the topology induced by the metric $d$). I am interested in the different values that ...
8
votes
2answers
1k views

Levy's isoperimetric inequality for sphere

Let me recall subj: If $s>0$, $A$ and $B$ are two subsets of $\mathbb{S}^{n}$, $|A|=|B|$ ($|\cdot|$ stands for the Lebesgue measure on the sphere) and $B$ is a cup $B=\{ (x_1,x_2,\dots,x_n)\in \...
8
votes
1answer
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\...
8
votes
1answer
265 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 $\...
8
votes
1answer
741 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 ...
7
votes
2answers
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 $...
7
votes
2answers
400 views

construction of a random measure with a given mean

Let me first pose a trivial question. Given a Borel probability measure $\mu$ on the real line, is it possible to construct a purely atomic random measure $M$ whose mean is $\mu$? The answer is ...
7
votes
4answers
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$. ...
7
votes
1answer
274 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$ ...
6
votes
1answer
451 views

First nonzero eigenvalue of the Laplacian on the submanifold

Consider a compact, connected $n$ dimensional Riemmanian manifold $\mathcal{N}$ and its $m$ dimensional closed submanifold $\mathcal{M}$ (with the metric coming from from the one defined on $\mathcal{...
6
votes
2answers
865 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$$ ...
6
votes
0answers
313 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 ...
6
votes
0answers
232 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-...
6
votes
2answers
965 views

Tails of sums of Weibull random variables

Suppose that $X_1, X_2, \ldots, X_n$ are i.i.d random variables distributed according to Weibull distribution with shape $0 < \epsilon < 1$ (it means that $\mathbf{Pr}[X_i \geq t] = e^{-\Theta(t^...
5
votes
1answer
182 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 ...
5
votes
1answer
297 views

Measure concentration for weakly dependent random variables

For an application quite alien to probability theory, I'd like to have a kind of measure concentration estimate, in the following spirit. Suppose that to every $1\le i,j\le n$ there corresponds a zero-...
5
votes
2answers
397 views

Local concentration of measure on Erdos-Rényi graph

Let $G_n=(V_n,E_n)$ be an Erdos-Rényi random graph, precisely the vertex set is $V_n=(1,\dots,n)$ and the edge set is $E_n=(ij\in\mathcal{P}_2(V_n)\ |\ \epsilon_{ij}=1)$ where $(\epsilon_{ij})_{ij}$ ...
5
votes
2answers
432 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
1answer
407 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)...
5
votes
1answer
188 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 $\mathcal{N}(0,\mathbf{I}/2)+i\mathcal{N}(0,\...
5
votes
0answers
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 ...
4
votes
1answer
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$...
4
votes
3answers
538 views

Lower bound for Gaussian random vector with negative correlation

Let $X = (X_1,\ldots,X_n) \in \mathbb{R}^n$ be jointly Gaussian with mean $0$, covariance matrix: $Var(X_i) = 1$, $Cov(X_i, X_{i+1}) = -1/2$, and $Cov(X_i, X_j) = 0$ else. Let $\zeta \in \mathbb{R}^...
4
votes
1answer
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....
4
votes
2answers
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 ...
4
votes
1answer
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
1answer
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{...
4
votes
1answer
466 views

An elementary probability question

Let $X$ be a $d$-dimensional random vector distributed according to probability measure $D$. At least the second moment of the coordinates of $X$ is finite. Consider $n+1$ samples $X_0, \ldots, X_n ...
4
votes
2answers
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 ...
4
votes
0answers
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}[...
4
votes
0answers
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
1answer
555 views

concentration inequality for averages of dependent random variables

Let $X \in R^n$ be a random vector such that $$P(|X_i| > \epsilon) > e^{-\epsilon^2}$$ What is a tight bound on $$P(\sum_{i=1}^n |X_i| > \epsilon)$$ and on $$P(\max_{1\le i\le n} |X_i| ...
3
votes
1answer
46 views

Tail bound for product of normal distribution

Let $U, V$ be two standard normal random variables with covariance $cov(U,V) = \beta \in [0,1)$. Let $W = UV$ be the product of two RV's, and $W_1, W_2, \ldots, W_n$ be n i.i.d copies of $W$, what's ...
3
votes
2answers
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 ...
3
votes
1answer
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$, ...
3
votes
1answer
155 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 symmetric,...
3
votes
1answer
433 views

Chernoff-Hoeffding bound for complex values

Consider the Chernoff-Hoeffding bound, stated as follows: Let $X_1, \dots, X_K$ be i.i.d. real-valued random variables with expectation value $\mu$ and satisfying $|X_i| \le b$. Let $\epsilon > 0$. ...
3
votes
0answers
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$...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
1answer
112 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, ...
3
votes
0answers
266 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 ...
3
votes
0answers
228 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
votes
1answer
217 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 ...