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,
- $ 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?
- 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}? $
- Does the LHS of each above example belong to the sub-exponential time complexity?
Thanks!