From: israel@math.ubc.ca (Robert Israel)
Subject: Re: Approximation/scaling required
Date: 25 Feb 2000 18:24:47 GMT
Newsgroups: sci.math,sci.math.research
Summary: [missing]

In article <38B51B0E.492EBCA@cogs.susx.ac.uk>,
 Lionel Barnett <lionelb@cogs.susx.ac.uk> writes:
> The following problem arose in the calculation of some genealogy
> statistics for a population genetics problem. Let:
> 
> 	             N   N
> 	f(N,n) = SUM    k  p (N,n)
> 	            k=1     k
> 
> for 0 <= n <= N, where:
> 
> 	          / N \      k         N-k
> 	p (N,n) = |   | (n/N) (1 - n/N)
> 	 k        \ k /
> 
> is the binomial distribution for N choices with mean n. I would like an
> approximation for (or at the very least the scaling of)  f(N,n) for
> large N
> (no restriction on n; i.e. n is cannot be assumed to scale in any
> particular way with N).

For convenience, let p = n/N and q = 1-p, and E[Y] = sum_{k=0}^N p_k(N,n) Y(k)
the expected value of a random variable Y(k) in this binomial distribution.
So f(N,n) = E[k^N].

It may be hard to get a very precise answer without making any assumptions
about how n depends on N.  But here are some inequalities.

First, since k^N is a convex function of k, Jensen's inequality tells you
E[k^N] >= E[k]^N = n^N.  

In the other direction, from ln(k) <= ln(m) + (k-m)/m we get
k^N <= m^N exp(kN/m - N), so 
E[k^N] <= m^N exp(-N) E[exp(kN/m)] = m^N exp(-N) (p exp(N/m) + q)^N
We want to choose m to minimize the right side here.  It appears that
the minimum is at m = N/(w+1) where w is the positive solution of
the equation w e^w = q/(p e) (this is expressed in Maple using the 
"Lambert W" function).  This makes the inequality E[k^N] <= (N q/(e w))^N.

Note also that ln(q/(p e)) >= w >= ln(q/(p e)) - ln ln(q/(p e)) when
q/(p e) > e.

Robert Israel                                israel@math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            
Vancouver, BC, Canada V6T 1Z2