MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


Let $B$ and $n$ be positive integers. Let $p_i \ge 0 $ be such that $\sum_{i=0}^{2B} p_i= 1$. I am interested in asymptotics (in terms of $B$, $n$, and $p_i$) for the coefficients of

$ (p_0 + p_1 x + p_2 x^2 + \dots + p_{2B}x^{2B})^n. $

Of particular interest to me is the central coefficient, i.e., that of $x^{Bn}$. Do you know of any references on this?



share|cite|improve this question

Estimates of the densities of sums of IID random variables are called local limit theorems.

Divide by $x^B$ to get the shifted distribution.

Shepp "A Local Limit Theorem" The Annals of Mathematical Statistics 35(1) 1964 pp 419-423 has some useful results when the mean of the shifted distribution is $0$. If there is no arithmetic progression with difference greater than $1$ containing the support of the distribution, then the coefficient of the central term is

$$\frac{1}{\sqrt{2\pi n \sigma^2}} + o\bigg(\frac{1}{\sqrt{n}}\bigg).$$

I suspect this holds even if some of the $p_i$ are negative.

If the mean of the shifted distribution is not $0$, and the $p_i$ are nonnegative, then you can get exponentially decreasing upper bounds from large deviation theory.

share|cite|improve this answer
Thank you for the answer and the reference. Quite helpful. – Pooya Aug 10 '12 at 11:54

There is a chapter in Knuth and Greene, Mathematics for the analysis of algorithms, that explains how to estimate this type of thing. If $B$ is fixed and $n\to\infty$, the central limit theorem might help; see this question.

Edit: Let me add a little to Douglas Zare's answer. If the mean of your distribution is not $B$, you can make it $B$ just by a transformation $x\mapsto \alpha y$ for suitably chosen constant $\alpha$ (for which you might have to solve a polynomial equation, but that's unavoidable). Then estimate the coefficient of $y^{nB}$ as stated and divide the answer by $\alpha^{nB}$. Also, if $B$ is not constant note that the central-limit theorem estimate will only be good if $n\to\infty$ much faster than $B\to\infty$. It's hard to say exactly how much faster (depends on the amount of variation amongst the $p_i$s) and in the worst case you might have to do your own contour integral like in Knuth and Greene; it isn't all that difficult if you only want the leading term.

share|cite|improve this answer
Thanks, it's a nice book indeed. – Pooya Aug 10 '12 at 11:54
Thanks for the extra information. The mean of the distribution in the problem I have is $B$. – Pooya Aug 15 '12 at 23:19

Your Answer


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.