5
$\begingroup$

Note: This is exact copy of my Math.SE question, which I am reposting here, as despite bounty it did not receive any answers.


Let there be $n$ pairs of shoes in a box. The the probability that from the $r \le n$ shoes I am taking out of the box there are exactly $p$ pairs is given by \begin{equation*} \mathbb{P}_{n}^{(r)}(p) = \frac{\binom{n}{p} \binom{n-p}{r-2p} 2^{r-2p}}{\binom{2n}{r}}. \end{equation*} For $n = 15$ and $r \in \{6,8,10\}$. The function (assuming the continuous factorial equivalents) looks like this: enter image description here

I am interested in finding the area under that curve, namely $$\int_{0}^{\frac{r}{2}} \frac{\binom{n}{p} \binom{n-p}{r-2p} 2^{r-2p}}{\binom{2n}{r}} \ \text{d}p$$

I consulted this question but could derive how that would help me.

I also thought about writing the first product of binomial coefficients as $$ \binom{n}{n - p}\binom{n - p}{r - 2p} $$ which is similar to the form $\binom{f(x)}{f(y)} \binom{f(y)}{f(x)}$ mentioned in this question.

$\endgroup$
1
  • 2
    $\begingroup$ I would expect the large $n,r$ limit to be unity for any ratio $n/r\geq 1$, since the difference between $\sum_p$ and $\int dp$ should vanish in that limit (and $\sum_p$ is obviously unity). $\endgroup$ Jul 7, 2019 at 19:24

3 Answers 3

5
$\begingroup$

I suspect some form of CLT for large $n, r$, which may possibly be proved by adopting Laplace's method of approximating the integrand by an appropriate gaussian kernel.

Interestingly enough, we can prove that:

$$ \int_{-\infty}^{\infty} \frac{\binom{n}{p}\binom{n-p}{r-2p}2^{r-2p}}{\binom{2n}{r}}\,\mathrm{d}p = 1. $$

To show this, we may apply the Legendre duplication formula to write

$$ \frac{\binom{n}{p}\binom{n-p}{r-2p}2^{r-2p}}{\binom{2n}{r}} = \frac{n!}{\binom{2n}{r}} \frac{\sqrt{\pi}}{\Gamma(1+p)\Gamma(n-r+1+p)\Gamma(\frac{r}{2}+\frac{1}{2}-p)\Gamma(\frac{r}{2}+1-p)}$$

and then apply the Ramanujan's beta integral (see the formula (5.3.14) of DLMF: 5.13).

$\endgroup$
1
$\begingroup$

Following on from Carlo's answer, someone noted in response to one of my questions once that for a unimodal nonnegative function $f$, we have $$ \biggl| \sum_{i=0}^k f(i) - \int_0^k f(x)\,dx \biggr| \le 2\max_{0\le x\le k} f(x).$$ The proof is by drawing a picture.

So to prove closeness of the sum and integral it suffices to prove that the function is unimodal and has a decreasing maximum. That shouldn't be too hard.

$\endgroup$
3
  • $\begingroup$ In your case the sum is exactly 1, so if $\max f \to 0$ then the integral converges to 1. $\endgroup$ Jul 8, 2019 at 20:47
  • $\begingroup$ For odd $r$, too? Because the $\sum_{k = 0}^{\left\lfloor \frac{r}{2} \right\rfloor} \mathbb{P}_n^{(r)} = 1$, but the upper bound of the integral is $\frac{r}{2}$, not rounded down. $\endgroup$ Jul 8, 2019 at 20:49
  • $\begingroup$ The extra $1/2$ in the range won't contribute more than $\max f$ to the integral, so it shouldn't matter. $\endgroup$ Jul 9, 2019 at 13:29
0
$\begingroup$

As I mentioned in a comment, I would expect the large $n,r$ limit to be unity for any ratio $f=r/n\in(0,1]$, since the difference between $\sum_p$ and $\int dp$ should vanish in that limit (and $\sum_p \mathbb{P}_{n}^{(r)}(p)=1$ by normalization). Proving this might be cumbersome, but the numerical evidence is clear:

Plot of $\int_0^{fn/2} \mathbb{P}_{n}^{(fn)}(p)\,dp$ versus $n$ for $f=1/4,1/2,3/4,1$. The convergence to unity is slower for smaller $f$, but it's there, as expected.

$\endgroup$
3
  • $\begingroup$ But can one find a explicit closed form? $\endgroup$ Jul 8, 2019 at 14:57
  • $\begingroup$ you mean a closed-form expression for this integral for any value of $r,n$? this is unlikely to be forthcoming, but note that for $r/n\gtrsim 1/2$ the integral is already close to unity for $r$ of order 10. $\endgroup$ Jul 8, 2019 at 15:04
  • $\begingroup$ Yes, I do. Why is that the case and what would be the / a general strategy for approaching such integrals? $\endgroup$ Jul 8, 2019 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.