0
$\begingroup$

For $0<\theta<1, \theta'=(1-\epsilon)\theta, \epsilon< \theta, k\in\mathbb{N}$, the problem is to tightly upper bound the following binomial summation:

$$\sum_{i=\lceil \theta k \rceil}^k {k \choose i} (\theta')^i(1- \theta')^{(k-i)}$$.

$\endgroup$
3
  • $\begingroup$ What are your thoughts? $\endgroup$
    – abiessu
    Feb 14, 2016 at 5:01
  • $\begingroup$ To motivate the problem, consider a binary vector $\{0, 1\}^n$ which have at most $\theta' n$ many $1$. Now, in a sample of size $k$ we want to upper bound the probability that it has more than $\theta k$ many $1$. $\endgroup$
    – Ram
    Feb 14, 2016 at 5:16
  • $\begingroup$ Presumably you want bounds with $\theta,\epsilon$ fixed as $k\to\infty$? The largest terms are going to be those with small $i$; indeed, each successive term will be smaller than the first term by some constant factor, so you can bound it by a geometric series, for example. $\endgroup$ Feb 14, 2016 at 6:29

0

You must log in to answer this question.