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
    ...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
    @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
    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}