The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
0answers
50 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 ...
3
votes
0answers
48 views

Bounds on truncated empirical mean

Let $(X_1,X_2,\cdots)$ be a sequence of independent and identically distributed random variables, $|X_i|\leq1$ and $S_n=\frac{1}{n}[X_1+\cdots+X_n]$. Is there an upper bound on the probability of ...
1
vote
0answers
81 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$ ...
0
votes
0answers
29 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. ...
5
votes
0answers
57 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
70 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
35 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
75 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
172 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
92 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 ...
4
votes
1answer
155 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$ ...
0
votes
0answers
75 views

Bounding Random Quadratic Gauss sums

I'm interested in seeing whether the following is true. Assume $u$ is uniform on $[0,1]$ and $|\epsilon_k|=1$ for all $k=1,2,\ldots,n$. We have \begin{align*} ...
1
vote
0answers
68 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
132 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
0answers
83 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*} ...
2
votes
1answer
295 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 ...
0
votes
0answers
45 views

Tail Bounds for the minimum value of a function

Consider y to be the minimum value of an objective function over some subspace. More specifically $y= \min_x \|e+Bx\|_\infty \quad s.t. \quad x\in \mathcal{S}$ where $e$ is a known vector, $B$ is a ...
7
votes
1answer
146 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 ...
2
votes
1answer
136 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 ...
4
votes
2answers
374 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$$ ...
7
votes
1answer
204 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
284 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
47 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
173 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
125 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 ...
9
votes
4answers
450 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 ...
3
votes
1answer
264 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
63 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
1answer
188 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
162 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
119 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 ...
1
vote
2answers
219 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, ...
2
votes
1answer
261 views

Upper bound on the maxima of ratio of expectation of quantities under Gaussian measure

Let $\lambda,\eta >0$ be given, and $u:\mathbb{R}\rightarrow \mathbb{R}$ be a real valued function. Define $$\Delta(u)= \frac{\int u(h) \exp(-\eta ...
4
votes
1answer
234 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 ...
1
vote
2answers
244 views

How many boxes so that there is $k$ of same of color from $n$ different colors?

Say you have $m$ boxes each of which is colored with one of $n$ colors. What should $m$ be so that the probability that there is atleast $k$ boxes with one same color is strictly greater than ...
4
votes
0answers
205 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 ...
8
votes
2answers
329 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
3answers
722 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 ...
2
votes
1answer
280 views

A Johnson-Lindenstrauss lemma for finite fields?

Given $m$ points in $\mathbb{R}^N$, the Johnson-Lindenstrauss lemma guarantees the existence of a linear operator $\mathbb{R}^N\rightarrow\mathbb{R}^n$ that nearly preserves pairwise distances between ...
2
votes
0answers
393 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 ...
5
votes
0answers
181 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: ...
5
votes
2answers
341 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}$ ...
3
votes
1answer
305 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$. ...
2
votes
1answer
328 views

concentration inequality for averages of dependent random variables

Let $X \in R^n$ be a random vector such that $$P(|X_i| > \epsilon) \le 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| ...
7
votes
2answers
446 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 ...
2
votes
0answers
204 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 ...
4
votes
2answers
663 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] = ...
4
votes
1answer
447 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 ...
-1
votes
2answers
441 views

Approximating a subspace by sampling a base without replacement

Let $X$ be a $p \times n$ matrix, with $p > n$. Now, suppose I sample $m < n$ columns from $X$ at random, without replacement. I would like to characterize the distance between the subspace ...
1
vote
0answers
198 views

A Multiplicative version of McDiarmid's Inequality like the one of Chernoff-Hoeffding Bounds

McDiarmid's Inequality basically says the following: Let $X_1, X_2, X_3, \ldots, X_n$ denote independent random variables and $f$ is a function of $n$ real arguments. If changing the value of the ...