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

219 questions
Filter by
Sorted by
Tagged with
12 views

140 views

27 views

### Concentration inequality on 1-norm of random vector

I would like to give an upper bound on $\Pr\{||X-\mathsf{E}[X]||_1 > t\}$ where $X$ is a $d$-dimensional random vector with each entry follows i.i.d. binomial $(n,p)$ (so $\mathsf{E}[X]$ is ...
23 views

### Tail bound on difference of shifted binomials (generalization)

I have a post Tail bound on difference of shifted binomials answered before and now I want to consider I slightly generalization of it which can't be solved using the methods in the previous thread. ...
81 views

### Gaussian width of sparse balls

The Gaussian width of a set $T\subset \mathbb{R}^n$ is defined as, $$G(T) = E\left[\sup_{\theta \in T} \sum_{i=1}^n \theta_i W_i\right],$$ where, $\mathbf{W}=(W_1,\ldots,W_n)$ is a sequence of i.i.d....
52 views

### Tail bound on difference of shifted binomials

I would like to derive an upper bound on $\mathsf{Pr}\{(\frac{X}{n}-\frac{1}{2})^2 \leq (\frac{Y}{n}-\frac{1}{2})^2\}$ where $X,Y$ are independent and $X\sim$ Bin($n,p$) where $p\neq \frac{1}{2}$, and ...
26 views

### Concentration of the value of times Markov Chain visits a certain state

I have a 2-state Markov chain with the following transition matrix $P={\begin{bmatrix}1-p&p\\1&0\end{bmatrix}}$, where $0 < p < 1$. Initially, we are in State 1. Let ...
17 views

### Upper-bound on $\inf_{(X,X')} P(\|X-X'\| > 2t)$ over all couplings $(X,X')$ of $P_1$ and $P_2$

Preamble: I've been struggling with the problem below (and similar problems https://mathoverflow.net/q/351317/78539) for a while now. Any kind of help would be very useful. Thanks in advance! So, let ...
27 views

34 views

### Concentration bound for least-square approximation error via uniform row sampling

While reading the following two papers: 1) Faster Least Squares Approximation of Drineas et al (https://arxiv.org/pdf/0710.1435.pdf) 2) Blendenpik: supercharging lapack's least-square solver of ...
37 views

### Concentration inequality with random signs and convolutions

Let $\epsilon_k$ be i.i.d random signs (or Rademacher variables), i.e., $P(\epsilon_{k}=1)=P(\epsilon_{k}=-1)=0.5$, $a, b, c, d$ be $n$-dimensional vectors. I hope to prove a concentration inequality:...
56 views

40 views

86 views

### Large deviation bound for squared norm of the sum of two random variables

I want to pose this question as general as possible and ask for reference of what to do in similar situations. I'll incrementally add details to narrow down the problem. I want to derive large ...
25 views

### Concentration Inequalities for point processes

I'm looking for some references in Concentration Inequalities on the counting random variable $N(t)$ for Hawkes and Poisson (temporal) point processes. Could you direct me to some? I haven't ...
39 views

### Restricted Isometry Property for Random Orthogonal Projections

The following is from Roman Vershynin's: High-Dimensional Probability: An Introduction with Applications in Data Science. Let $P$ be the orthogonal projection in $\mathbb{R}^n$ onto an $m-$...
I'm struggling with the following problem. Let $X_i$ be iid discrete rvs, taking values in $\mathbb{N}$ with arbitrary distribution $\mathrm{P} (X_i = k) = p_k$. Let $Z_n$ be a number of distinct ...