# 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.

335 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
• 939
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 ...
• 352
1 vote
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 ...
• 153
10 views

• 167
1 vote
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 ...
• 1,153
1 vote
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 ...
1 vote
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 ...
• 239
1 vote
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 ...
• 217
1 vote
33 views

• 4,353
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 ...
1 vote
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 ...
• 4,353
1 vote
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 ...
1 vote
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}_{+}$ ...
• 1,788
153 views

• 812
1 vote
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$...
• 8,309
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$ ...
• 75
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.$$ ...
• 217
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}$$ ...
• 612
1 vote
109 views

• 8,309
60 views

• 367
1 vote
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 ...
• 8,309
1 vote
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 ...
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 ...