Inequality for difference of consecutive atom probabilities for binomial distribution

Question

Edit: This post was originally two questions, the first of which has been answered, but a reference would still be appreciated if existent. The second question has been removed and migrated to its own post here.

---

I would not be particularly surprised if the inequalities I want are readily available in several standard texts. Unfortunately, these days all of my probability books are stuck in my office (and I'm stuck at home). So thanks for the help in advance.

---

Let $B_{n,p}$ denote the usual binomial random variable (i.e., the probability that it equals $k$ is given by ${n \choose k} p^k (1-p)^{n-k}$). I would like some references (or short proofs) for the following fact:

• For all integers $n, k$, and all $0 < p < 1$, we have $\mathbb{P}(B_{n,p} = k) - \mathbb{P}(B_{n,p} = k+1) \leq \dfrac{100}{n p (1-p)}$

[I'd be happy if the number "100" is replaced by whatever universal constant is convenient.]

---

I was having trouble coming up with a particularly good proof of this, so that would be welcome. But ideally, I would prefer a reference if possible. Thanks!

(If curious, this claim could be proven by looking at the left-hand-side as a function of $k$, noting when it's increasing [e.g., by taking consecutive differences], and checking the value at this max. Unsurprisingly, this is maximized when $k$ is one standard-deviation above the mean [this corresponds to the inflection point in the normal distribution])

Answer 1

Concerning your first question: Let $p_k:=P(B_{n,p}=k)$. We have to show that \begin{equation*} p_k-p_{k+1}\ll\frac1{npq}, \tag{1} \end{equation*} where $q:=1-p$ and $a\ll b$ means that $a\le Cb$ for some universal real constant $C>0$. Clearly, without loss of generality (wlog) \begin{equation*} 1\ll npq. \end{equation*} Since $p_{k+1}=\frac{n-k}{k+1}\frac pq\,p_k$, we rewrite (1) as \begin{equation*} \frac{k+1-(n+1)p}{(k+1)q}\,p_k\ll\frac1{npq}. \tag{2} \end{equation*} It is now clear that wlog $k+1\ge(n+1)p$, so that $(k+1)q\ge npq$. Therefore and because $k+1-(n+1)p=k-np+q\le k-np+1$, it suffices to show that \begin{equation*} a_k:=(k-np)\,p_k\ll1. \tag{3} \end{equation*} So, wlog $k>np$. For such $k$, it is easy to see that $a_{k+1}\ge a_k$ iff $k<k_*$, where $k_*$ is an integer such that $|k_*-np-\sqrt{npq}|\ll1$. So, the integer $k_*$ is a maximizer of $a_k$ in $k$. So, wlog $|k-np-\sqrt{npq}|\ll1$ and hence $$k-np\ll \sqrt{npq}.$$ Also, as is well known (see e.g. Proposition 2), \begin{equation*} p_k\ll\frac1{\sqrt{npq}}. \end{equation*} Now (3) immediately follows.