Questions tagged [concentration-of-measure]

Use this tag for questions about the principle that a random variable that depends in a Lipschitz way on many independent variables (but not too much on any of them) is essentially constant.

Filter by
Sorted by
Tagged with
1 vote
1 answer
24 views

Speed of convergence of empirical probability mass function

I was wondering about the following situation: Suppose we have a random variable $X$ taking values in the finite set $\{1,2,\ldots,k\}$. Let the probability mass function be denoted by $f$. Suppose we ...
user avatar
  • 939
3 votes
0 answers
48 views

Is recycling samples better than drawing fresh ones?

At a high level, I am wondering if in a sequential process it is better to reutilize samples even if these samples have been used to make past decisions. Let me formalize my doubts in a toy example ...
user avatar
1 vote
0 answers
28 views

Concentration probabilities for distributions with $\exp(-c t^\alpha)$ tails

I am trying to generalize the concentration inequalities for the sub-exponential and sub-gaussian distributions to a larger family with tail $\exp(-c t^\alpha)$ for arbitrary $\alpha > 0$. In ...
user avatar
  • 153
0 votes
0 answers
10 views

Lipshitz deviation inequality that implies Bernstein's inequality?

In Keith Ball's convex geometry notes, the author comments on the formal similarity of the following two results: Theorem 1. (Bernstein's Inequality for Bernoulli Random Variables.) Let $\varepsilon_1,...
user avatar
2 votes
0 answers
26 views

Tail bounds for sub-Gaussian and sub-exponential distributions

Massart and Laurent (see [1], Lemma 1 on page 1325] give tail bounds for $\chi^2$ random variables. A corollary of their bound is the following: $$P\left[\frac{1}{k} X \leq 1- 2\sqrt{\frac{x}{k}} \...
user avatar
  • 698
1 vote
0 answers
65 views

How the second inequality stands?

Taken from paper "A Universal Law of Robustness via isoperimetry" by Bubeck and Sellke. Theorem 3. Let $\mathcal{F}$ be a class of functions from $\mathbb{R}^{d} \rightarrow \mathbb{R}$ and ...
user avatar
1 vote
0 answers
36 views

Markov's inequality for uniformly bounded functions

Question: If $f$ and $g$ are two positive, increasing functions such that $f(t)\leq g(t)$ for all $t>0$ and $X$ is a positive random variable, then is it true that for all $t>0$, $$\frac{\mathbb{...
user avatar
11 votes
2 answers
183 views

Can we control the distance between the empirical and theoretical mean on the whole trajectory any better than using Hoeffding and a union bound?

Suppose $X,X_1,X_2,X_3\dots$ is a $\mathbb{P}$-i.i.d. family of $[-1,1]$-valued random variables with $\mathbb{E}[X] = 0$. Hoeffding's inequality implies that \begin{equation*} \forall T \in \...
user avatar
  • 4,648
0 votes
1 answer
43 views

How to find the size of an ϵ-net of a vector space?

Taken from paper "A Universal Law of Robustness via isoperimetry" by Bubeck and Sellke. Theorem 3. Let $\mathcal{F}$ be a class of functions from $\mathbb{R}^{d} \rightarrow \mathbb{R}$ and ...
user avatar
0 votes
0 answers
22 views

Hanson-Wright Inequality Lowering the Constant to Obtain a Factor of 2 Instead of 4

I'm reading the proof of Hanson-Wright Inequality from Rudelson & Vershynin's paper "Hanson-Wright inequality and sub-gaussian concentration". (https://arxiv.org/pdf/1306.2872.pdf) I'm ...
user avatar
  • 73
0 votes
0 answers
31 views

Probability of failure in a multinomial experiment

Generalised version of Probability of failing to decode a biased die Say we are given a biased die having a total of $N$ sides that shows up $M$ of its sides with a probability of $p$ and the rest of ...
user avatar
0 votes
0 answers
24 views

in-probability bound for maximum of chi square distributions

Let $X_1, \dots, X_n$ be i.i.d. Chi square random variables with $d$ degrees of freedom, i.e. $X_1, \dots, X_n \stackrel{\text{i.i.d}}{\sim} \chi^2_d$. There is a nice bound (see Example 2.7 from the ...
user avatar
  • 2,147
3 votes
0 answers
38 views

Does there exist a uniform Monte-Carlo Approximation of certain function classes?

Given a measurable and bounded function $f:X \to \mathbb{R}$ on a metric-measure space $(X, d, \mathcal{P})$, we can approximate $\int_\chi f$ in terms of $N$ iid samples $X_1, \ldots, X_N \sim \...
user avatar
  • 167
1 vote
0 answers
33 views

Understanding the question in concentration of measure

I'm reading papers about concentration of measure. Could you check if my below understanding is correct? Let $(E, d)$ be a metric space and $\mu$ a probability measure on the Borel $\sigma$-algebra ...
user avatar
  • 1,153
1 vote
0 answers
20 views

A quadratic equation gives linear-like behavior that contradict the relative minimum?

Refer to the below. Is the red term obtained by plugging in the yellow term to the blue term? If not, how is it obtained? If yes, consider the following: If we want to minimize the blue term, i.e. a ...
user avatar
1 vote
1 answer
46 views

Sampling from equal-norm tight frame (Vershynin exercise 5.6.6)

I am struggling with Exercise 5.6.6 from Vershynin's "High-Dimensional Probability": Consider an equal-norm tight frame $(u_i)_{i=1}^{N}$ in $\mathbb{R}^n$. State and prove a result that ...
user avatar
1 vote
0 answers
17 views

Find the optimal value and minimiser for a function

I encounter this problem when reading the proof of Bernstein inequality for bounded random variables. Consider the function $h(\lambda) = \frac{\lambda^2\cdot v^2/2}{1-c\lambda}-\lambda t$ for some ...
user avatar
  • 217
1 vote
0 answers
33 views

Concentration of the empirical moments

I do not know of any results on the concentration of empirical moments. More specifically, my problem is : Let $X_1,...,X_n$ iid sampled by a law $\mathbf{P}$ with moments $\mu_i=\mathbf{E}_{\mathbf{P}...
user avatar
  • 11
3 votes
0 answers
29 views

Gap between two consecutive order statistics under arbitrary distribution.

Consider an arbitrary distribution $\mathcal{D}$ supported on $[a,b]$ with density function $\phi(x)\in[\gamma, \Gamma]$ where $\Gamma\geq \gamma>0$. M i.i.d samples $\{d_i\}_{i=1}^M$ are drawn ...
user avatar
2 votes
0 answers
94 views

A dimension-free upper bound for $\| X \|_{\infty}$ when $X \sim N(0,\Sigma)$

For a $p$-dimensional random vector $X \sim N(0,\Sigma)$, it is known that with high probability $$ \| X \|_{\max} \le C \sqrt{\log p} $$ where $C$ is some constant possibly depending on $\Sigma$. I ...
user avatar
  • 4,353
0 votes
0 answers
38 views

using biased samples to get tighter concentration bounds

Suppose $\{X_1,X_2,\cdots,X_N\}$ are sampled from a fixed distribution $P_X$. Under different assumptions, we may have $|\frac{1}{N}\sum_{i=1}^N X_i- \mathbb{E}(X)|\leq f(N,\delta)$ for a given ...
user avatar
  • 21
2 votes
0 answers
66 views

$\ell_1$ norm of random projection

Let $G_{m, n}$ denote the Grassmannian manifold, i.e. the set containing all possible subspaces of $R^m$ with dimension $n$. Let $E \in G_{m, n}$. We can associate with $E$ an orthogonal projection ...
user avatar
8 votes
1 answer
218 views

Dudley's Inequality can be Loose (Vershynin 8.1.12)

Let $e_1,...,e_n$ denote the canonical basis vectors in $\mathbb{R}^n$. Consider the set $$T = \left \{ \frac{e_k}{\sqrt{1 + \log k}}, k =1,...,n\right \}$$ Show that $$\int_{0}^\infty \sqrt{\log \...
user avatar
0 votes
0 answers
24 views

Lower bound for the max of absolute value of i.i.d Gaussians.

I'm trying to prove the following result : $$ \mathbb{E} \max_{i=1,2,\ldots,n} |X_i| \ge C \sqrt{\log(n)}. $$ where the $ X_i $'s are i.i.d $ \mathcal{N}(0,1) $. To prove it, I tried to use the ...
user avatar
0 votes
1 answer
36 views

probability of error in sampling to estimate sum of a population

Given non-negative numbers $$\{m_1, m_2,\dots,m_n\}$$ we have to estimate the sum $$s = \sum_{i=1}^nm_i$$ using sampling (with replacement). If we sample k numbers uniformly at random, then I can ...
user avatar
0 votes
0 answers
23 views

Hanson-Wright inequality, any relation between the original quadratic form and the decoupled quadratic form?

Hanson-Wright's inequality such as this provides a bound on the second-order chaos of the form $$P(x^\top A x -\mathbb{E}[x^\top A x] > t) $$ For example, $x\sim N(0, I_n)$ and $A$ is some $n\times ...
user avatar
2 votes
1 answer
39 views

Does Hoeffding's inequality hold for uncorrelated random variables?

I know that Hoeffding's inequality holds for sums of independent random variables. However, we also know that being uncorrelated does not necessarily imply independence. But I wish to understand ...
user avatar
2 votes
0 answers
28 views

Poincare constant for Gaussian distribution

The minimum of constant $C$ to satisfy the following condition is called Poincare constant for a probability measure $\mu$. For any smooth function $f$ on $\mathbb{R}$, the relation $$\int_{-\infty}^\...
user avatar
2 votes
0 answers
112 views

Verifying the Bernstein condition for random matrices

Theorem 6.2 of the following paper by J. Tropp states the matrix Bernstein inequality for the subexponential case. Given two i.i.d. sequences $X_1,\dots,X_n \sim N(0,\Sigma)$ and $Y_1,\dots,Y_n \sim N(...
user avatar
  • 4,353
0 votes
0 answers
11 views

L1 Diameter of the Highest Posterior Density Region

In the frequentist statistics, we have confidence intervals with known diameters. However, in Bayesian statistics, we haven't the faintest idea of the diameter of the credible region. I believe it is ...
user avatar
1 vote
0 answers
39 views

Upper bound for operator norm of sample covariance of two sequences of independent Gaussian vectors

Assume $X_1,\dots, X_n \stackrel{\text{i.i.d.}}\sim N(\mu, \Sigma)$ and $Y_1,\dots, Y_n \stackrel{\text{i.i.d.}}\sim N(\gamma, \Gamma)$ are $d$-dimensional random vectors and the two sequences are ...
user avatar
  • 4,353
1 vote
0 answers
38 views

Lower bound on the probability of a sum of iid random variables larger than a threshold

Suppose you are given $n$ iid random variables $X_1,\ldots,X_n$ each taking values in $\{1,2,3,\ldots\}$. Each $X_i$ has the cumulative distribution function $P(X_i \le v) = 1 - \frac{1}{(v+1)^p}$ for ...
user avatar
1 vote
1 answer
21 views

Question about the definition of concentration function $\alpha_{P, X, \rho}(\epsilon):=\sup_{A\subset X}\{1-P(A^{\epsilon})|P(A)\ge 1/2\}$.

I have a question about the definition of concentration function, which is defined as in Wainwright, High-dimensional statistics. The concentration function $\alpha:[0,\infty)\to \mathbb{R}_{+}$ ...
user avatar
  • 1,788
5 votes
2 answers
153 views

Concentration result from Delta method?

Let $X_1,X_2, \cdots$ be iid random variables with finite second moment. Let $\bar{X_n} = (1/n)\sum_{i=1}^{n} X_i$ and $\bar{X^2_n} = (1/n)\sum_{i=1}^{n} X_i^2$. Define $S_n = \bar{X^2_n} - (\bar{X_n})...
user avatar
1 vote
1 answer
44 views

Coupling for tail bounds

Let $X_1, X_2$ be two random variables such that $\mathbf{E}X_1=\mathbf{E}X_2=0$ and $$\forall x\geq 0, \quad \mathbf{P}[X_1\geq x]\leq \mathbf{P}[X_2\geq x].$$ Can we construct a coupling $(Y_1,Y_2)$ ...
user avatar
  • 813
1 vote
1 answer
36 views

Deriving Sample Complexity from given expectation bound

In equations (1.6) and (1.7) of this paper, the authors provide an upper bound on an expectation term and the corresponding sample complexity. I am a bit confused as to how they derive their sample ...
user avatar
  • 4,353
1 vote
0 answers
102 views

Use Chebyshev's inequality in sum of Bernoulli random variables

I'm currently studying for my exams and doing questions related to it. This is a problem I've be stuck on for some time now and I'd like to know how to solve it. Setting: We have $n\geq 10$ random ...
user avatar
  • 470
0 votes
1 answer
71 views

Deriving a variant of Paley-Zygmund inequality for Gaussian variables

Recently I have encountered the following inequalities: Let $Z \sim \mathcal{N}(0,\sigma^2)$, then \begin{equation} \forall t \in \mathbb{R},\text{ } P(|t+Z| \geqslant \sigma) \geqslant P(|Z| \...
user avatar
  • 325
2 votes
0 answers
48 views

Conditional expectation of a function of i.i.d. random variables given some of them

Suppose $(\Omega, \mathcal{A}, \mathbb{P})$ is a probability space $(E, \mathcal{E})$ is a nice measurable space. Let $X_i \colon \Omega \to E$ for $1 \le i \le n$ be i.i.d. random elements, and let $...
user avatar
  • 812
1 vote
0 answers
9 views

Relationship between $\gamma_n(A + B)$, $\gamma_k(A)$, and $\gamma_{n-k}(B)$, where $A \subseteq V$, $B \subseteq V^\perp$, and $\gamma_n := N(0,I_n)$

Let $\gamma_n = \gamma_1^{\otimes n}$ be the standard gaussian measure on $\mathbb R^n$ and let $V$ be a $k$-dimensional subspace of $\mathbb R^n$ with orthogonal completment $V^\perp$. Let $A$ and $B$...
user avatar
  • 8,309
0 votes
1 answer
33 views

Lower bound for probability of being above a certain percentage of the expectation

Let $X$ be a non-negative random variable and $\lambda \in [0,1]$, can we show that $(1-\lambda)^2$ is smaller or equal to $P(X > \lambda E(X))$, where P denotes the probability distribution of $X$ ...
user avatar
  • 75
2 votes
0 answers
21 views

Expectation of sum of k max chi-square variables

Consider $n$ iid standard normal random variables $g_1,\ldots,g_n$, and I am interested in the lower bound for the following expectation $$\mathbb{E}\max_{K\subset [n],|K| = k}\sum_{i\in K}g_i^2.$$ ...
user avatar
  • 217
3 votes
2 answers
128 views

Exponential bound on the tail of a gaussian

Let $Z$ be a centered normal variable of variance $\sigma^2$, I am trying to prove that, $$\sup_{t>0} \left( \mathbb{P}(Z \geq t) \exp\left( \frac{t^2}{2 \sigma^2} \right) \right) = \frac{1}{2} $$ ...
user avatar
  • 612
1 vote
1 answer
109 views

Growth rate of derivatives of $\phi_n(t):=\mathbb E_x[f(x_1)f(tx_1 + (1-t^2)^{1/2} x_2)]$, where $x=(x_1,\ldots,x_n)$ is uniform on unit-sphere

Suppose $f:[-1,1] \to \mathbb R$ is function which is $k$ times continuously-differentiable a.e on $(-1,1)$, for some fixed $k \ge 1$. Let $n$ be a large positive integer, define the function $\phi_n:[...
user avatar
  • 8,309
2 votes
2 answers
51 views

Compute limit of $a_n:=E[f(x_1)f(x_2)]$, for random $(x_1,\ldots,x_n)$ on unit-sphere in $R^n$ and any function $f$ with a jump discontinuity at $0$.

Let $f:[-1,1] \to \mathbb R$ be continuous a.e (and assumed to be bounded, if that helps), with a jump-discontinuity at $0$ and set $$ c:=\frac{f(0^-)+f(0^+)}{2}. $$ For any integer $n \ge 2$, define $...
user avatar
  • 8,309
5 votes
1 answer
60 views

"Bernstein version" of McDiarmid?

I have seen used in a paper the following variant of McDiarmid's inequality, referred to as a "Bernstein-type variant": Theorem. Let $f\colon \mathbb{R}^n \to \mathbb{R}$, and $X_1,\dots, ...
user avatar
  • 63.6k
1 vote
0 answers
108 views

Surface order large deviation in Ising ferromagnet

Background: A familiar behaviour of independent and identically distributed (i.i.d.) random variables $X_1, X_2,\ldots X_n$ is concentration: the probability that the sum $X_1+X_2+\ldots X_n$ exceeds $...
user avatar
1 vote
0 answers
84 views

Integral of product of Hermite polynomials

Let $H_n$ be the $n$th Hermite polynomial of the probabilist. For example, $H_0(x) = 1$, $H_1(x)=x$, $H_2(x) = x^2 - 1$, $H_3(x) = x^3-3x$, etc. Let $u$ and $v$ be unit-vectors in $\mathbb R^d$, and ...
user avatar
  • 8,309
1 vote
0 answers
33 views

How to calculate the the number of nonzero for Poisson binomial distribution

Suppose a sequence of random number $S$, each entry has probability $p_i$ to be 1, otherwise choose zero. The sequence of probability is not necessary identical. According to wiki, we can compute the ...
user avatar
1 vote
0 answers
31 views

Probability of Sampling Points outside of the Empirical Span

Let $P$ be a probability distribution over $\mathbb{R}^d$. Note that we DO NOT assume that $P$ is continuous w.r.t. Lebesgue measure. For example, P can be a multinomial distribution over a finite and ...
user avatar

1
2 3 4 5
7