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

297 questions
Filter by
Sorted by
Tagged with
31 views

### Corollary of Hoeffding’s Inequality

Question I am not from a statistics background I came across the following corollary of Hoeffding’s Inequality and couldn't find the derivation or proof for it so that could anyone please share some ...
46 views

23 views

### Upper bound for Explore-then-commit Bandit algorithm

Background: From the blog, "The explore-then-commit strategy is characterized by a natural number m, which is the number of times each arm will be explored before committing. Thus the algorithm ...
29 views

### Concentration Inequality for the Negative Binomial Distribution

I was wondering if there is any well-known concentration inequality for the Negative Binomial distribution with parameters $r$ and $p$. This random variable is defined as the number of independent ...
8 views

### Invertibiity of random matrix with correlated entries

Let $X$ be a random $n \times d$ with independent whose distributions have densities (w.r.t Lesbegue) and let $W$ be a random $d \times k$ marix with independent entries whose distributions also have ...
57 views

24 views

### Concentration of Least Squares Estimate

We know that if the unknown model satisfies a linearity assumption i.e. $y = x^T\theta + \epsilon$, where $\epsilon$ is Gaussian Noise, we have the least squares estimate $\hat{\theta}$, to be a good ...
34 views

### Proof check: Using Hanson-Wright inequality to concentrate a quadratic form $y^\top A y$ where both $y$ and $A$ are random but independent

Disclaimer. I don't know if this is the right venue to ask this. I'm working out a bigger proof, in a critical step, I'ved used an argument I'm not quite sure about. Let $n$ be a large positive ...
21 views

### Bounds for extreme singular-values of matrix $c_{ij} := \psi(x_i^\top w_j)$ where $x_1,\ldots,x_n,w_1,\ldots,x_k \sim N(0,(1/d)I_d)$ iid

Let $n,d,k$ be large positive integers such that $\max(n/d,k/d) =: \lambda < 1$. Let $X$ be a random $n \times d$ matrix with entries drawn iid from $N(0,1/d)$ and let $W$ be a $k \times d$ random ...
37 views

### Lower-bound on $\mathbb E[\|A^{-1}x\|]$ when $A$ is a positive-definite matrix with eigenvalues in $[a,b]$ and $x=(x_1,\ldots,x_n)$ is iid Rademacher

Let $A$ a positive-definite $n \times n$ matrix with eigenvalues in the interval $[a, b]$ and let $x=(x_1,\ldots,x_n)$ be a random vector with iid components distributed uniformly in $\{\pm 1\}$. ...
31 views

117 views

### The sum of mutually singular measures

I have been trying to make an exercise related to mutually singular measures. Namely the following: Exercise Let $\mu$ be a positive measure and $\nu_1, \nu_2$ be arbitrary measures all defined on ...
70 views

### Upper bound for $|\mathbb E[f(X)] - f(0)|$ when $X \sim N(0,\sigma^2)$ and $f:\mathbb R \to \mathbb R$ is piecewise-linear with $\|f'\|_\infty \le 1$.

Let $f:\mathbb R \to \mathbb R$ be a piecewise linear function such that $f(0)=0$ and $\|f'\|_\infty \le 1$ and let $X$ be a Guassian random variable with mean $0$ and variance $\sigma^2$. What is an ...
84 views

### One mysterious step in proof of Lemma 3 Devroye 83

Can someone help me with one step of the following proof of a multinomial concentration inequality taken from Lemma 3 of "The equivalence of weak, strong and complete convergence in l1 for kernel ...
43 views

### tail bound of the deviation from sum of functions of random variables to its expectation value

I am struggling at an error propagation recently and I do not know what tools can be used in this problem. Explicitly my problem can be represented as following: I have expression \varepsilon=\frac{...
101 views

### Levy's measure concentration lemma generalized for a product measure?

I am looking for a product measure concentration inequality on n-sphere. I think is is a generalization of the Levy's lemma. In my understanding, the lemma by Levy ensure that the measure ...
177 views

### Absolute value of sub-gaussian

Let $\eta_1 , \eta_2, \cdots, \eta_t$ be 1-subgaussian independent random variables with mean 0(but not necessarily identical). Now we know several nice equations about $|\sum_{s=1}^t \eta_s|$. How ...
### Good concentration inequality for $\max_{i,j} X_j- X_i$ where $X_1,\ldots,X_n \overset{iid}{\sim} N(0,1)$.
Let $n$ be a large positive integer and define $\Delta:\mathbb R^n \to \mathbb R$ by $\Delta(x) := \max_{i,j} x_j - x_i$. Let $X_1,\ldots,X_n$ be iid from $N(0,1)$ Question. What is a good ...
Let $f:\mathbb R^n \to \mathbb R$ be coordinatewise $1$-Lipschitz, i.e $|f(x')-f(x)| \le |x'_k-x_k|$ whenever $x=(x_1,\ldots,x_n)$ and $x' = (x'_1,\ldots,x_n')$ are two vectors in $\mathbb R^n$ which ...