8
$\begingroup$

The following seems to hold in numerical simulations, is it true? $$\lim_{n\to \infty} \int_0^1 dx \frac{n! 2^{-n} n}{(n x)!(n-n x)!\sqrt{x(1-x)}}=2$$

It's a combination of two known integrals

$$\lim_{n\to \infty} \int_0^1 dx \frac{n! 2^{-n} n}{(n x)!(n-n x)!\}=1$$

$$\int_0^1 dx \frac{1}{\sqrt{x(1-x)}}=\pi$$

First one follows from asymptotic expansion of Gamma and the second is done using trig substitution

Edit: $x!$ is short for $\Gamma(x+1)$.

Limit convergence is apparent for $n$ between 10 and $10^6$, $\log_{10} n$ gives an almost perfect fit to the log of deviation

Motivation -- the last integral is an instance of "Information Volume", an estimate of number of statistically distinguishable distributions in the Bernoulli model, used as a measure of model complexity . A major annoyance is that this integral fails to exist for some popular models, like the geometric distribution family. Perhaps we can fix this by instead estimating the number of observation sequences that are well fit by some distribution in the model? That's the first integral.

  • 0
    Maybe you should consider to use Gamma notation. Do you have any background?2010-09-18
  • 0
    Numerically, I've confirmed it (though the rate of convergence is excruciatingly slow); analytically I'm still working on this, it looks tough.2010-09-18
  • 0
    Just curious, how did you confirm it numerically? Just evaluating for high values? I'm using Mathematica and NLimit gives incorrect result http://pastebin.com/2bFE1mQ52010-09-18
  • 0
    @J. M. Do you have any free software that can handle this?2010-09-18
  • 0
    Not exactly software, but you can evaluate it in Wolfram Alpha for various values of n -- http://tinyurl.com/26pdmn32010-09-18
  • 0
    @Yaroslav: I didn't use `NLimit` ; I wrote a suite of convergence acceleration methods in *Mathematica* and all the methods I applied this on suggest that the limit is 2 (if at least one of the methods gave a different answer then I would have become very skeptical). @AD: It shouldn't be too hard to implement sequence transformation methods in any language of your choice: the theory is intricate, but the algorithms are amazingly simple.2010-09-19
  • 0
    ...as a matter of fact, for kicks, I implemented these methods on a TI-83+ calculator, and they work quite well there too. :) As for analytical proof, fiktor seems to have nailed it, but I'm still trying to verify his steps.2010-09-19

3 Answers 3

9

This is nothing mysterious, it is the continuous analogue of $\Sigma 2^{-n} \binom{n}{k} = 1$ with factorials interpolated by Gamma functions that vary quite smoothly in the middle range where the sum is concentrated and has approximately Gaussian distribution, $k = n/2 + O(\sqrt{n})$.

The ratio between the discrete step function and continuous interpolation is $1+O(1/n)$ in the middle range (using the first few terms of Stirling asymptotic expansion for $\Gamma$).

The $1/\sqrt{x(1-x)}$ is irrelevant because it is effectively a constant factor $2 + O(1/n)$ in the middle range.

The middle range has width less than $n^{1/2 + \epsilon}$.

So, writing the integral in terms of $u = nx$,

$$I_n = \int_0^n \binom{n}{u} 2^{-n} du \frac {1} {\sqrt{x(1-x)}} \sim 2 \int_0^n \binom{n}{u} 2^{-n} du \sim 2$$

with an additive error of $O(n^{\epsilon - 1/2})$. The $\epsilon$ can be a small positive constant or an infinitesimal depending on how you dissect the integral into middle and tails (we have to choose a cut for each $n$, such that the entire middle range is covered as $n \to \infty$; any set of choices will prove convergence, but the rate of convergence depends on the choices).

  • 0
    Brilliant! This is much neater than what I was trying. :)2010-09-19
  • 0
    @T.. I would love to have your intuition!2010-09-19
  • 0
    @AD., in this case the resemblance to the discrete sum is clear and probably in the background of the problem (the OP wrote the question in terms of continuous factorials rather than Gamma function, so in notation it is the same as C(n,k)). The confusing point is, what does the sqrt(x(1-x)) term mean and how does it make the answer 2 instead of 1. For this you look at what x-dependent weight factor is doing to the integral and only the part near x=1/2 matters. This is the whole intuition, the O(1/n) factors are just to show that it can be made rigorous and supports the other answer.2010-09-19
  • 0
    @T.. Thanks, yes, I noted that it was a 1/Beta factor in the integrand - but I never thought of any binomial sum.2010-09-20
  • 0
    @AD. -- it is obscured somewhat by the integration variable being originally x in [0,1], not nx in [0,n]. I find it confusing to keep track of the normalizations in beta and gamma integrals, so working with continuous factorials often makes it easier to see (notationally and otherwise) what is going on.2010-09-20
  • 0
    @T.. Yes, I guess you are right - or at least it does not hurt to think of Beta and Gamma as "continuous combinatorial" extensions of discrete combinatorial functions.2010-09-20
2

Limit (and even asymptotic series) of your integral can be calculated using Laplace's method and Stirling's approximation. The solution can be done in 5 steps:
1. Prove, that integral over $[0,1/n]$ can be neglected. In order to do this, use Stirling's approximation for all factorials except $(nx)!$, which can be approximated by a constant.
2. Prove, that integral over $[1/n,\delta]$ can be neglected (for $\delta<1/2$). In order to do this, use Stirling's approximation for all factorials (note, that $z!/(\sqrt{2 \pi z} (z/e)^z))$ is bounded from both sides by positive constants if $z>=1$).
3. Using symmetry you know, that your limit is equal to $\lim_{n\to\infty}\int_{\delta}^{1-\delta}dx(\dots)$.
4. Use Stirling's approximation to approximate factorials. You will get the following:
$$\int_{\delta}^{1-\delta}dx\frac{n!2^{-n}n}{(xn)!(n-xn)!\sqrt{x(1-x)}}=(1+O(n^{-1}))\sqrt{\frac{n}{2\pi}}\cdot$$ $$\int_{\delta}^{1-\delta} x^{-1}(1-x)^{-1}exp\bigl(-n(x\ln x+(1-x)\ln(1-x)+\ln 2)\bigr)dx$$
5. Apply Laplace's method to the last integral and get it's asymptotic.

  • 0
    Wow, I'll need some time to digest this, but this looks like some rigorous St.Petersburg math discipline. I actually grew up there as well, but I think math teachers didn't beat me enough :(2010-09-18
  • 0
    Your attack looks the same as what I was trying out, except what I first did was to cut the original integral in half (the integrand is symmetric over $(0,1)$) so that the limits run from 0 to 1/2.2010-09-19
0

$\newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\dd}{{\rm d}}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\expo}[1]{{\rm e}^{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\ic}{{\rm i}}% \newcommand{\imp}{\Longrightarrow}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\pp}{{\cal P}}% \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert #1 \right\vert}$

$\ds{% {\cal F}_{n} \equiv \int_{0}^{1} {\dd x \over \pars{nx}!\,\pars{n - nx}!\,\sqrt{x\,\pars{1 - x\,}\,}}\,, \qquad \lim_{n \to \infty}\bracks{{\pars{n + 1}! \over 2^{n}}\,{\cal F}_{n}} \ \equalby{?} \ 2}$


$\tt\large Hint$:

\begin{align} \pars{nx}!\pars{n - nx}! &\approx \bracks{\sqrt{2\pi\,}\,\pars{nx}^{nx + 1/2}\expo{-nx}} \bracks{\sqrt{2\pi\,}\,\pars{n - nx}^{n - nx + 1/2}\expo{-\pars{n - nx}}} \\[3mm]&= 2\pi\,\expo{-n}\bracks{n^{nx + 1/2}\,x^{nx + 1/2}} \bracks{n^{n - nx + 1/2}\pars{1 - x}^{n - nx + 1/2}} \\[3mm]&= 2\pi\,\expo{-n}\,n^{n + 1}x^{nx + 1/2}\pars{1 - x}^{n - nx + 1/2} \\[3mm]&= \sqrt{2\pi\,}\,{\rm e}\,{n^{n + 1} \over \pars{n + 1}^{n + 3/2}}\bracks{% \sqrt{2\pi\,}\,\pars{n +1}^{n + 3/2}\expo{-\pars{n + 1}}} x^{nx + 1/2}\pars{1 - x}^{n - nx + 1/2} \\[3mm]&\approx \sqrt{2\pi\,}\,{\rm e}\,{n^{-1/2} \over \pars{1 + 1/n}^{n + 3/2}}\,\pars{n + 1}!\; x^{nx + 1/2}\pars{1 - x}^{n - nx + 1/2} \\[3mm]&\approx \sqrt{2\pi\,}\,n^{-1/2}\pars{n + 1}!\; x^{nx + 1/2}\pars{1 - x}^{n - nx + 1/2} \end{align}

$$ \pars{nx}!\pars{n - nx}! \approx {\sqrt{2\pi\,} \over n^{1/2}}\, \pars{n + 1}!\;x^{nx + 1/2}\pars{1 - x}^{n - nx + 1/2} $$

\begin{align} {\cal F}_{n} &\approx {n^{1/2} \over \sqrt{2\pi\,}\,\pars{n + 1}!} \int_{0}^{1}x^{-1 - nx}\pars{1 - x}^{-1 - n + nx}\,\dd x \end{align}