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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – joriki Sep 20 '12 at 9:11
  • $\begingroup$ What is the meaning of the exponent $c$ in $P(A_n^c)$? $\endgroup$ – Peter Sep 21 '12 at 2:39
  • $\begingroup$ @Peter: "c" means complement of set. $\endgroup$ – Ethan Sep 21 '12 at 14:36
1
$\begingroup$

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)$.

$\endgroup$

Your Answer

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

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