Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Maybe you should consider to use Gamma notation. Do you have any background? –  AD. Sep 18 '10 at 6:51
    
Numerically, I've confirmed it (though the rate of convergence is excruciatingly slow); analytically I'm still working on this, it looks tough. –  J. M. Sep 18 '10 at 16:09
    
Just curious, how did you confirm it numerically? Just evaluating for high values? I'm using Mathematica and NLimit gives incorrect result pastebin.com/2bFE1mQ5 –  Yaroslav Bulatov Sep 18 '10 at 17:26
    
@J. M. Do you have any free software that can handle this? –  AD. Sep 18 '10 at 20:21
    
Not exactly software, but you can evaluate it in Wolfram Alpha for various values of n -- tinyurl.com/26pdmn3 –  Yaroslav Bulatov Sep 18 '10 at 20:32
show 2 more comments

3 Answers

up vote 9 down vote accepted

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).

share|improve this answer
    
Brilliant! This is much neater than what I was trying. :) –  J. M. Sep 19 '10 at 9:28
    
@T.. I would love to have your intuition! –  AD. Sep 19 '10 at 20:29
    
@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. –  T.. Sep 19 '10 at 20:57
    
@T.. Thanks, yes, I noted that it was a 1/Beta factor in the integrand - but I never thought of any binomial sum. –  AD. Sep 20 '10 at 4:31
    
@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. –  T.. Sep 20 '10 at 7:51
show 1 more comment

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.

share|improve this answer
    
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 :( –  Yaroslav Bulatov Sep 18 '10 at 21:01
    
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. –  J. M. Sep 19 '10 at 2:34
add comment

$\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}
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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