5
$\begingroup$

$X_1,\ldots,X_k$ are independent random variables distributed like $\text{Binomial}[n,p]$. What is the probability that they are all equal, as a function of $k$ $p$ and $n$, when $n$ is very large?

Currently I have two solutions.

Solution A is general but quite informal. When $n$ is large, a Binomial random variable behaves like a normal random variable, and most of its probability mass is concentrated in the interval $\mu \pm \sigma$, where $\mu$ is the mean value and $\sigma$ is the standard deviation. So we can approximate the variables as being drawn independently at random from a set with $2\sigma$ elements. After the first variable is determined, each of the remaining $k-1$ variables has probability $\approx 1/(2\sigma)$ to have the same value, so the probability that all are equal is $\approx 1/(2\sigma)^{k-1}$. Here $\sigma=\sqrt{p (1-p) n}$, so the probability is:

$${1 \over (4 p (1-p) n)^{(k-1)/2}} $$

Solution B is more formal but works only for $p=1/2$ and $k=2$ variables. Define $Y_2 := n - X_2$. So the event $X_1=X_2$ is identical to the event $X_1+Y_2 = n$. $Y_2$ is distributed like $\text{Binomial}[n,1-p]$, but here $p=1-p$ so it is distributed like $X_1$. Therefore $X_1+Y_2$ is distributed like $\text{Binomial}[2n,1/2]$ and the probability that it equals $n$ is just: ${2n\choose n}2^{-2n}$. By Stirling's approximation, the binomial coefficient is $\approx {4^n \over \sqrt{\pi n}}$, so the probability that $X_1=X_2$ is approximately:

$$ {1\over \sqrt{\pi n}}$$

This is a constant times the outcome of Solution A, which means that both solutions are at least asymptotically correct.

What is a solution that works for every $p$ and $k$?

EDIT: See also: What is the probability that two univariate Gaussian random variables are equal?

$\endgroup$
  • $\begingroup$ Are you after asymptotics when $n\to\infty$, for $k$ and $p$ fixed? $\endgroup$ – Did Mar 8 '17 at 11:36
  • 1
    $\begingroup$ If you are, a natural conjecture is that $$r_n=P(X_1=X_2=\cdots=X_k)$$ is such that, for every fixed $k$ and $p$, $$\lim_{n\to\infty}n^{(k-1)/2}r_n=\frac1{(2\pi p(1-p))^{(k-1)/2}\sqrt{k}}$$ $\endgroup$ – Did Mar 8 '17 at 11:44
  • 1
    $\begingroup$ So we want to simplify or find an approximation of $\sum_{i=0}^n \left( {n \choose i}\, p^i (1-p)^{n-i} \right)^k$ for large $n$, right? $\endgroup$ – Paul Mar 16 '17 at 13:30
  • 1
    $\begingroup$ @Did I think you can turn that into an answer. I tested your formula numerically and it seems right. $\endgroup$ – Paul Mar 16 '17 at 13:54
  • 1
    $\begingroup$ Manually make this post about sort of opposite situation from "Related" to "Linked". $\endgroup$ – Lee David Chung Lin Nov 15 '18 at 11:44
3
+50
$\begingroup$

The Binomial $B_{n,p}(i)$, for large $n$, tends to a normal $N_{\mu,\sigma^2}(x)$ with $\mu=np$ and $\sigma^2 =n p q$ ($q=1-p$). Hence the desired probability $$P_{n,p,k}=\sum_{i=0}^n \left( {n \choose i}\, p^i (1-p)^{n-i} \right)^k$$ can be approximated, one hopes, by the integral

$$ P_{n,p,k} \approx I_{n,p,k}=\int (2 \pi \sigma^2)^{-k/2} \exp\left(- \frac{k(x-\mu)^2}{2 \sigma^2}\right) dx=\\ =(2 \pi \sigma^2)^{-k/2} \sqrt{\frac{2 \pi \sigma^2}{k}}=\frac{1}{\sqrt{k \, (2 \pi n p q)^{k-1}}}$$

$\endgroup$
  • $\begingroup$ This fits my calculation for $k=2,p=1/2$. $\endgroup$ – Erel Segal-Halevi Mar 17 '17 at 13:16
  • $\begingroup$ It is also similar to my initial approximate calculation, except for a factor of $\sqrt{k}$ in the denominator. $\endgroup$ – Erel Segal-Halevi Mar 17 '17 at 13:18

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.