二项分布tail probability

hbghlyj

\[\sum_{i=k}^n\binom ni\left(\frac{1}{n}\right)^i\left(1-\frac{1}{n}\right)^{n-i}\leq\binom nk\left(\frac{1}{n}\right)^{k}\]

证明

把$i$换为$i+k$
\[\sum_{i=0}^{n-k}\binom n{i+k}\left(\frac{1}{n}\right)^i\left(1-\frac{1}{n}\right)^{n-i-k}\leq\binom nk\]
代入${\binom n{i+k}\over\binom nk}=\frac{(n-k)\dots(n-i-k+1)}{(k+1)\dots(k+i)}\le\frac{(n-k)\dots(n-i-k+1)}{i!}=\binom{n-k}i$
\[\sum_{i=0}^{n-k}{\binom n{i+k}\over\binom nk}\left(\frac{1}{n}\right)^i\left(1-\frac{1}{n}\right)^{n-i-k}\le\sum_{i=0}^{n-k}\binom{n-k}i\left(\frac{1}{n}\right)^i\left(1-\frac{1}{n}\right)^{n-i-k}=1\]

来源: 这道题盒子1中的球数服从二项分布: $\Pr(\text {盒子1中的球数} ≥k )=\sum_{i=k}^n\binom ni\left(\frac{1}{n}\right)^i\left(1-\frac{1}{n}\right)^{n-i}\color{#f00}\leq\binom nk\left(\frac{1}{n}\right)^{k}$

hbghlyj

Bounds on tail probabilities of discrete distributions Proposition 1(c)

Let $X∼\text{Bin}(m,p)$. The pmf is given by $f_x=\left(\begin{array}{c}m \\ x\end{array}\right) p^x q^{m-x}(0 \leq x \leq m)$, where $q=1-p$.
Then, for $m p \leq n \leq m$
$$
f_n \leq P(X \geq n) \leq \frac{(n+1) q}{n+1-(m+1) p} f_n
$$