Saturday, 31 July 2010

co.combinatorics - Looking for an explicit formula for a limit of a binomial-like expression

Here's a probabilistic solution to your problem. Suppose $X_N$ is a binomial random variable with parameters $N$ and $s/N$ (ie. $X_N$ counts the number of heads in $N$ independent coin flips, each with probability $s/N$ of heads). Also let $P$ be a Poisson random variable with mean $s$, so that for all non-negative integers $k$:
$$Prob[P=k] = e^{-s}frac{s^k}{k!}.$$
A well-known result sometimes called the law of rare events implies that the distribution of $X_N$ converges to that of $P$ as $Nto +infty$. In particular, for any bounded real-valued function $f$ defined on the non-negative integers:
$$E(f(X_N)) = sum_{k=0}^N binom{N}{k}left(1-frac{s}{N}right)^{N-k}left(frac{s}{N}right)^{k}f(k)to E(f(P))=sum_{k=0}^{+infty}e^{-s}frac{s^k}{k!}f(k).$$



Apply this to $f$ satisfying $f(x)=1/x$ if $x>0$, $f(0)=0$, and the LHS becomes your expression. The RHS becomes:
$$sum_{k=1}^{+infty}e^{-s}frac{s^k}{k!times k} = e^{-s}int_{0}^{s}frac{e^{u}-1}{u}du,$$
which I guess is the same as the previous answer.



Added note: a quantitative version of the law of rare events gives the error bound:
$$forall f:Nto [0,1], |E(f(X_N))-E(f(P))|leq sleft(1-e^{-s/N}right);$$
this allows for simultaneous limits in N and $s$, and goes to $0$ iff $s^2/Nto 0$.

No comments:

Post a Comment