The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
0answers
248 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
149 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
244 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
283 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 ...
5
votes
1answer
287 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 ...
2
votes
2answers
253 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 ...
6
votes
0answers
296 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
381 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
831 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
344 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
582 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 ...
6
votes
0answers
225 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
395 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
412 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
1answer
528 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| ...
9
votes
2answers
636 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 ...
3
votes
0answers
260 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 ...
6
votes
2answers
924 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
463 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
455 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 ...
0
votes
2answers
261 views

Weak convergence of the image of a weakly $L^1$ converging sequence

This is a follow-up on another question. Can something be said about the image of a weakly converging sequence in $L^1$? More precisely $u_k\ge 0$ $\|u_k\|_{L^1}=\int u_k=1$ $u_k$ converges to $u$ ...
2
votes
2answers
485 views

Weak convergence of the image of an $L^1$ converging sequence under a convex function

Suppose that $u_k$ is a sequence of $L^1$ functions defined on a compact $K\subset R^n$ and a function $f:[0, \infty)\to[0, \infty)$ with the following properties $u_k\ge 0$ $\|u_k\|_{L^1}=\int ...
10
votes
1answer
730 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 ...
1
vote
1answer
357 views

Azuma's Inequality when the conditions hold with high probability?

In Azuma's Inequality, is the statement true when $|X_k - X_{k-1}| < c_k$ almost surely rather than with probability 1? If not, is there another result which gives strong concentration when the ...
13
votes
0answers
333 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 ...
1
vote
0answers
160 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 ...
6
votes
1answer
447 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 ...
3
votes
0answers
223 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 ...
4
votes
3answers
536 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 ...
7
votes
2answers
397 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 ...
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 ...