Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A sequence of events $A_n, n \in \mathbb{N}$ is said to have a high probability, if $\mathrm{P} (A_n^c) \leq \frac{c}{n^d}$ for some $c, d >0$.

Chernoff bounds are often used to prove some (upper or lower) tail events of a binomial distributed random variable $X$ have a high probability. In such proofs, we are given a function $f$, and often need to find some $a, b>0$, such that $e^{f(n)} \leq \frac{a}{n^b}$ for $n \in \mathbb{N}$.

For example,

  1. $$ e^{-\frac{10 \ln n}{2} \ln(10 \ln n)} \leq \frac{1}{n^8}, \text{ for every } n \geq 2 $$ and $$ e^{-\frac{9 \ln n \ln 9}{2} } \leq \frac{1}{n^8}. $$ How are the exponents $8$ of $\frac{1}{n^8}$ determined in the above two examples?
  2. Is it possible to determine the constants $c, a, b$ for each of the following two examples, $$ e^{- \frac{(c \ln n -\frac{\ln n}{n^2} + 1) * \ln (cn^2 + \frac{n^2}{\ln n}-1)}{2}} \leq \frac{a}{n^b}, $$ and $$ e^{- (c \ln n + 1) * \ln (c\ln n+1) } \leq \frac{a}{n^b}? $$
  3. Does the LHS of each above example belong to the sub-exponential time complexity?

Thanks!

share|improve this question
    
In the second example under 1., since $$ \mathrm e^{-9\ln n\ln 9/2}=n^{-9\ln 9/2}\approx n^{-9.9}\;, $$ the exponent $8$ is somewhat arbitrary and not very tight. –  joriki Sep 20 '12 at 9:11
    
What is the meaning of the exponent $c$ in $P(A_n^c)$? –  Peter Sep 21 '12 at 2:39
    
@Peter: "c" means complement of set. –  Ethan Sep 21 '12 at 14:36

1 Answer 1

1) Try the simple derivation $$e^{(-9\ln n \ln 9)/2} = n^{-4.5\ln 9} \le n^{-8}.$$ You could have also used a somewhat smaller constant instead of $-8$, but it's irrelevant if all you want is high probability for this event.

2) Same as in 1). Just use algebra to simplify the LHS and bring it into the form of the RHS. That will determine the constants $a$ and $b$.

3) The LHS goes to $0$ as $n\rightarrow\infty$ so it clearly is sub-exponential, in fact it's in $o(1)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.