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 a easier way to prove it by Cramer’s theorem. 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.

  • $\begingroup$ I tried to improve the formatting. Please double check that it looks ok. $\endgroup$ – Nate Eldredge Apr 10 '14 at 3:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.