Probability of $\operatorname{Bin}(n,p)=\operatorname{Bin}(n,q)$ is decreasing when $n$ increases

Question

$\newcommand{\Bin}{\operatorname{Bin}}$I would like to show that $\mathbb P(\operatorname{Binomial}(n,p) = \operatorname{Binomial}(n,q))$ decreases when $n$ increases for a fixed pair $(p,q)$. This can be reformulated as $\mathbb P(X_n=0)$ decreases where $X_n=\sum_{i=1}^n S_i$ is a lazy random walk where $S_i=-1,0,1$ with probability $p(1-q),pq+(1-p)(1-q),(1-p)q$. For $p=q$ this can be done by characteristic functions. Any ideas for general $(p,q)$? I feel like this should be well known.

P.S. This question is crossposted from mathstackexchange, where it receives no answer even after I put a bounty.

Edit: To be clear the actual question is to show for any pair of $(p,q)$, we have $P(\Bin(n,p)=\Bin(n,q))\le P(\Bin(n-1,p)=\Bin(n-1,q))$ for any $n$, and everything is independent of each other.

Answer 1

We can use the lazy random walk interpretation to show the desired result.

First, observe that it suffices to analyze a non-lazy random walk with $\pm 1$ steps. This is because taking $n$ steps in a lazy walk is like taking $\operatorname{Binomial}(n, v)$ steps in a non-lazy walk, where $v$ is the probability the lazy walk moves in a given step.

To that end, let

• $\{Y_t\}_{t \in \mathbb{N}}$ be a random walk with i.i.d. $\{-1, +1\}$ increments, where $+1$ has probability $u \in (0, 1)$,
• $\{T_n\}_{n \in \mathbb{N}}$ be a random walk with i.i.d. $\{0, +1\}$ increments, where $+1$ has probability $v \in (0, 1)$,
• $X_n = Y_{T_n}$, and
• $f(t) = \mathbf{P}[Y_t = 0]$.

Also suppose $\{Y_t\}_{t \in \mathbb{N}}$ and $\{T_n\}_{n \in \mathbb{N}}$ are independent. This means $X_n$ is a random walk with i.i.d. $\{-1, 0, +1\}$ increments, stepping $-1$ with probability $(1 - u) v$ and stepping $+1$ with probability $u v$.

Relationship to the original question. $X_n$ is the lazy random walk from the question, representing the difference between the two independent binomials. $Y_t$ is the lazy walk's value after $t$ nonzero steps, and $T_n$ is the number of nonzero steps the lazy walk has taken. To specify the process in terms of $p$ and $q$ from the original question, set $u = \frac{(1 - p) q}{p (1 - q) + (1 - p) q}$ and $v = p (1 - q) + (1 - p) q$.

We wish to show $\mathbf{P}[X_n = 0]$ is strictly decreasing in $n$. The key observation is that $T_n$ is strictly stochastically increasing in $n$ (see (2) below), and we can express $\mathbf{P}[X_n = 0]$ as a function of $T_n$: $$\begin{aligned} \mathbf{P}[X_n = 0] &= \mathbf{P}[Y_{T_n} = 0] \\ &= \mathbf{E}\bigl[\mathbf{P}[Y_{T_n} = 0 \mid T_n]\bigr] \\ &= \mathbf{E}[f(T_n)], \end{aligned}$$ where the last step follows from independence of $\{Y_t\}_{t \in \mathbb{N}}$ and $\{T_n\}_{n \in \mathbb{N}}$.

We first show that $f(t) = \mathbf{P}[Y_t = 0]$ is strictly decreasing in $t$. This follows form a short computation: $$\begin{aligned} \frac{f(t + 1)}{f(t)} &= \frac{\mathbf{P}[Y_{t + 1} = 0]}{\mathbf{P}[Y_t = 0]} \\ &= \frac{\frac{(2 (t + 1))!}{((t + 1)!)^2} (u (1 - u))^{t + 1}}{\frac{(2 t)!}{(t!)^2} (u (1 - u))^t} \\ &= u (1 - u) \cdot \frac{(2t + 2) (2t + 1)}{(t + 1)^2} \\ &= 4 u (1 - u) \cdot \frac{(t + 1) \bigl(t + \frac{1}{2}\bigr)}{(t + 1)^2} \\ &< 4 u (1 - u) \leq 1. && (1) \end{aligned}$$

Having shown $f(t)$ is strictly decreasing in $t$, we now show $\mathbf{E}[f(T_n)]$ is strictly decreasing in $n$. It is clear that for all $t \in \{0, \dots, n\}$, $$ \mathbf{P}[T_{n + 1} > t] > \mathbf{P}[T_n > t]. \qquad (2) $$ This is because $T_{n + 1}$ gets one more $\{0, +1\}$-valued step than $T_n$. By summation by parts, for $\mathbb{N}$-valued random variables $T$, $$ \mathbf{E}[f(T)] = f(0) + \sum_{t = 0}^\infty (f(t + 1) - f(t)) \mathbf{P}[T > t]. \qquad (3) $$ By (1), the differences $f(t + 1) - f(t)$ are all positive. Combining this with (2) and (3) implies $\mathbf{E}[f(T_{n + 1})] > \mathbf{E}[f(T_n)]$, as desired.

Remark 1. We have actually shown that if $u \neq \frac{1}{2}$ (i.e. if $p \neq q$), then $\mathbf{P}[Y_t = 0]$ decreases exponentially in $t$. I strongly suspect that $\mathbf{P}[X_n = 0]$ decreases exponentially in $n$, too, though you might need to use a concentration inequality on $T_n$ to show this.

Remark 2. Equation (3) holds for any function $f$ and $\mathbb{N}$-valued random variable under any one of the following sufficient (but not necessary) conditions:

• $T$ has bounded support (so one can use linearity of expectation).
• $f$ is absolutely bounded (so one can use Fubini's theorem).
• $f$ is nonnegative (so one can use Tonelli's theorem).

In this application, all three conditions hold, which is why I did not dwell on them.

---

On strict vs. weak stochastic ordering. An earlier version of this proof claimed the following:

By a standard property of stochastic ordering, if $f(t)$ is strictly decreasing in $t$, then $\mathbf{E}[f(T_n)]$ is strictly decreasing in $n$, as desired.

The "standard" property I was thinking of is for weak (i.e. standard) stochastic ordering, not strict. I believe a strict version should hold, and it's easy enough to show for integer-valued random variables. But the details for the general version seem complicated enough that above, I replaced the appeal to the property with a direct argument. I've asked about the strict version here.

Answer 2

Here is a proof which also shows the exponential decay in $n$ for $p\neq q$

Let $0<p,q<1$ and $B_{n,p},B_{n,q}$ independent $\mathrm{Binomial}(n,p)$ resp. $\mathrm{Binomial}(n,q)$ distributed random variables.

Using the representation ${n \choose k}=\frac{1}{2\pi}\int_{-\pi}^\pi e^{-ikt}(1+e^{it})^n\,dt$ we find

\begin{align*} d_n:&=\mathbb{P}(B_{n,p}=B_{n,q})\\&=\sum_{k=0}^n {n \choose k}^2 (pq)^k \big((1-p)(1-q)\big)^{n-k}\\ &=\frac{1}{2\pi}\int_{-\pi}^\pi\sum_{k=0}^n {n \choose k} (pq)^k \big((1-p)(1-q)\big)^{n-k}e^{-ikt}(1+e^{it})^n\,dt\\ &=\frac{1}{2\pi}\int_{-\pi}^\pi \Big((1-p)(1-q)+pqe^{-it}\Big)^n (1+e^{it})^n\,dt\\ &=\frac{1}{2\pi}\int_{-\pi}^\pi \Big((1-p)(1-q)+pq +pqe^{-it}+ (1-p)(1-q)e^{it}\Big)^n\,dt \end{align*} that is, $d_n$ is the residue of $f_n(z):= \frac{1}{z}\Big((1-p)(1-q)+pq +\frac{pq}{z}+ (1-p)(1-q)z\Big)^n$ in 0, evaluated by a circle integral over $|z|=1$. Since $f_n(z)$ is analytic on $\mathbb{C}\setminus\{0\}$ we may instead use the circle with $|z|=\sqrt{\frac{pq}{(1-p)(1-q)}}$ (this choice makes the integrand real) in the residue computation and get

\begin{align*} d_n&=\frac{1}{2\pi}\int_{-\pi}^\pi \Big((1-p)(1-q)+pq +\sqrt{pq(1-p)(1-q)}(e^{-it}+ e^{it})\Big)^n\,dt\\ &=\frac{1}{2\pi}\int_{-\pi}^\pi \Big((1-p)(1-q)+pq +2\sqrt{pq(1-p)(1-q)}\,\cos(t)\Big)^n\,dt \end{align*} Let \begin{align*} g:&[-\pi,\pi]\longrightarrow \mathbb{R}\\ &t\mapsto (1-p)(1-q)+pq +2\sqrt{pq(1-p)(1-q)}\,\cos(t) \end{align*} Clearly $g$ is continuous, has minima at $t=-\pi$ and $t=\pi$ given by \begin{align*} m(p,q):=\big(\sqrt{pq} -\sqrt{(1-p)(1-q)}\big)^2 \end{align*} and has a unique maximum at $t=0$, given by \begin{align*} M(p,q):=\big(\sqrt{pq} +\sqrt{(1-p)(1-q)}\big)^2 \end{align*} and $m(p,q)<g(t)<M(p,q)$ for $t\not\in \{-\pi,0,\pi\}$.

Further $\sqrt{pq}+\sqrt{(1-p)(1-q)}\leq 1$, with equality if and only if $p=q$.
( Since by the AGM-inequality $\sqrt{pq}\leq\frac{1}{2}(p+q), \sqrt{(1-p)(1-q)}\leq \frac{1}{2}(2-p-q)$ with equality if and only if $p=q$).

Thus $M(p,q)\leq 1$ and $0<g^{n+1}< g^n$ a.e., therefore the sequence $(d_n)$ is strictly decreasing. Finally, since $d_n<M(p,q)^n$ and $M(p,q)<1$ for $p\neq q$ the decrease is exponential in $n$ in these cases.

ADDED: a much shorter derivation of the residue representation above is possible the (as noted by Dan Romik). Consider the lazy random walk $X_n$ which stays put (step 0) with probability $pq+(1-p)(1-q)$ and steps $+1$ resp. $-1$ with probabilities $p(1-q)$ resp. $q(1-p)$. Then \begin{align*} d_n=\mathbb{P}(X_n=0) &=[z^0]\,\Big(pq+(1-p)(1-q)+p(1-q)z+\frac{q(1-p)}{z}\Big)^n\\ &=[z^{-1}]\,\frac{1}{z}\Big(pq+(1-p)(1-q)+p(1-q)z+\frac{q(1-p)}{z}\Big)^n \end{align*} and now computing the residue using the circle $|z|=\sqrt{\frac{(1-p)q}{(1-q)p}}$ gives \begin{align*} d_n=\frac{1}{2\pi}\int_{-\pi}^\pi \Big(pq+(1-p)(1-q) +2\sqrt{pq(1-p)(1-q)}\,\cos(t)\Big)^n\,dt \end{align*}

Answer 3

Since you are only interested in the non-symmetric case, here is an answer. The local limit theorem states that $\mathbb P(X_n=0)\sim C\rho^{n}n^{-1/2}$, where $\rho$ is the spectral radius. Therefore, $\mathbb P(X_n=0)/\mathbb P(X_{n-1}=0)\sim \rho$. Now, since the random walk is non-centered, $\rho<1$, thus for large enough $n$, $\mathbb P(X_n=0)/\mathbb P(X_{n-1}=0)<1$, i.e. $\mathbb P(X_n=0)$ is eventually decreasing.

I do not know if the word "eventually" is necessary though.

Answer 4

Here's a proof, though I can't help but feel it's far too complicated (which also makes me worried I've made a mistake). On its merits, I suspect the connection to Legendre polynomials could be cleaned up. More significantly, it feels like overkill, that the whole approach is too much.

Let $B_{n,p}$ be a random variable with binomial distribution and parameter $p$, so $$ \mathbb{P}[B_{n,p} = k] = \binom{n}{k}p^k(1-p)^{n-k}. $$ Then for $B_{n,p}$ and $B_{n,q}$ independent we have \begin{align*} \mathbb{P}[B_{n,p} = B_{n,q}] & = \sum_{k = 0}^n \mathbb{P}[B_{n,p} = B_{n,q} = k]\\ & = \sum_{k=0}^n \mathbb{P}[B_{n,p}=k] \cdot \mathbb{P}[B_{n,q}=k]\\ & = \sum_{k=0}^n \binom{n}{k}^2 (pq)^k[(1-p)(1-q)]^{n-k}\\ &= [(1-p)(1-q)]^n\ _2F_1\left(-n,-n,1,\frac{pq}{(1-p)(1-q)}\right) \end{align*} Here, the second equality is independence and the last is from Wolfram Alpha. From Equation (1) in Section 2.7 here, we have $$ _2F_1(a,b,c,z) = (1-z)^{-a} \ _2F_1\left(a,c-b,c,\frac{z}{z-1}\right). $$ With $a = b = -n$, $c = 1$ and $z = \frac{pq}{(1-p)(1-q)}$ (though we'll stick to $z$ for now), this becomes $$ _2F_1\left (-n,-n,1,z \right) = (1-z)^n\ _2F_1\left(-n,n+1,1,\frac{z}{z-1}\right), $$ which by Section 2.2 (11) is the Legendre polynomial $P_n\left(1-2\frac{z}{z-1}\right)$. Evaluating $\frac{z}{z-1}$ at $z=\frac{pq}{(1-p)(1-q)}$ gives $\frac{-pq}{1-p-q}$, so we see \begin{align*} \mathbb{P}[B_{n,p} = B_{n,q}] &= [(1-p)(1-q)]^n \left(1- \frac{pq}{(1-p)(1-q)}\right)^n P_n\left(1+2\cdot \frac{pq}{1-p-q}\right)\\ &= (1-p-q)^n P_n\left(\frac{pq + (1-p)(1-q)}{1-p-q}\right). \end{align*} Legendre polynomials satisfy the recurrence $$ (n+1)P_{n+1}(x) = (2n+1) x P_n(x)-nP_{n-1}(x). $$ Let $E_n = \mathbb{P}[B_{n,p} = B_{n,q}]$. Setting $x = \frac{2pq -p-q+1}{1-p-q}$ and multiplying the previous equation through by $(1-p-q)^{n+1}$, we get $$ (n+1)(1-p-q)^2 E_{n+1} = [\left(pq+(1-p)(1-q)\right)(2n+1) E_n - n E_{n-1}] $$ Note $|1-p-q| < 1$. Then the result will follow if the right-hand side is less than $(n+1) E_n$, or equivalently if
$$ [\left(pq+(1-p)(1-q)\right)(2n+1) E_n -(n+1)E_n < n E_{n-1}. $$ Since $pq + (1-p)(1-q) < 1$ when $p,q$ are non-degenerate, the lefthand side less than $nE_n$, which is less than $n E_{n-1}$ by the inductive hypothesis.

Edit: I made several mistakes in the final inequality, partly due to misusing the three term recurrence. It seems likely the approach can be salvaged though.

Answer 5

First of all, you need to somehow specify a joint distribution; if you compute $\textrm{Bin}(X, 1/2)$ and $\textrm{Bin}(X, 1/2)$ by flipping a single fair coin $n$ times and using the outcomes to determine both random variables, then they are equal with probability $1$! It seems you're assuming independence from your reformulation.

Also, even with independence, if $p = q = 0$ or $p = q = 1$, then they are equal with probability $1$ for all $n$. So I assume you want $0 < p, q < 1$.

Regardless of joint distribution, by de Moivre-Laplace/your favorite law of large numbers/any ergodic theorem, for any fixed $\epsilon > 0$, $P(\textrm{Bin}(n,p))/n \in (p - \epsilon, p + \epsilon)) \rightarrow 1$ as $n \rightarrow \infty$. So if you choose $\epsilon < |p-q|/2$ I think you get your desired result for $p \neq q$.

But in the independent case there's a much simpler proof. If you take any independent random variables $X, Y$ whatsoever with values in $\mathbb{N}$, and denote $M = \max_n P(Y = n)$, then $P(X = Y) = \sum_n P(X = n) P(Y = n) \leq M \sum_n P(X = n) = M$. So it suffices to just show that the max probability of any outcome for $\textrm{Bin}(n, p)$ approaches $0$, which is fairly simple to show directly.