Skip to main content
2 of 3
formatting
Nate Eldredge
  • 29.8k
  • 4
  • 101
  • 150

Concentration bound for $f(w) = w \times \sin wz$

I need to find an exponential bound for $P(|S_n - \mu| > \lambda)$ where $S_n = \frac{1}{D} \sum_{i=1}^D w_i \sin w_iz$ for a constant $z$, $E(S_n) = \mu$ and $w_i$ are drawn from the normal distribution.

One way to do that is to assume that $\forall i: |w_i| < k$. Thus, $\forall i: |w_i \sin w_iz| < k$ and using Hoeffding's inequality we can find an exponential bound for $P(|S_n - \mu| > \lambda \mid w_i < k)$. Then, add the probability of $ \exists i: w_i > k$ to the result. Then, by choosing appropriate $k$ we can find an exponential bound for the given equation which seems like:

$$P(|S_n - \mu| > \lambda) = \exp\left(-C\frac{D\lambda^2}{\log D}\right) $$

However, I think still it would be easier ways to prove it. I failed to prove that $w \sin wz - \mu$ is a subgaussian random variable. In fact it easy to show that $P(|w \sin wz| > \lambda) < C \exp(-c\lambda^2)$ but it is not useful since the random variable do not have zero mean.