1
$\begingroup$

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!

  • 0
    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.2012-09-20
  • 0
    What is the meaning of the exponent $c$ in $P(A_n^c)$?2012-09-21
  • 0
    @Peter: "c" means complement of set.2012-09-21

1 Answers 1