3
$\begingroup$

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])

$\endgroup$
  • 1
    $\begingroup$ I second the suggestion by Iosif Pinelis: It is best to avoid stating multiple questions in one post. $\endgroup$ – Yuval Peres Jun 17 '20 at 0:33
  • $\begingroup$ Alright. I’ll move the second one to another post. I’d be happy for a reference for the first fact, by the way... That one feels like it’s already known. $\endgroup$ – Pat Devlin Jun 17 '20 at 2:05
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Alright, thanks. Can we get a similarly short proof of the second point in the original post? $\endgroup$ – Pat Devlin Jun 15 '20 at 23:52
  • 1
    $\begingroup$ @PatDevlin : I think the inequality in your second question can be proved (if it's true) in a straightforward (but likely tedious) way based on Stirling's formula. However, I don't see any reasons for this inequality to be known or to have a short and nice proof. Also, I think asking multiple questions in one post (especially such rather unrelated ones as in this case) should be avoided, for your own sake and for the sake of others. Therefore, I'd suggest you post your second question separately . $\endgroup$ – Iosif Pinelis Jun 16 '20 at 3:26

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.