# Multinomial Coefficient Estimates

Hello,

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?

Thanks,

Pooya

-

## 2 Answers

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.

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

-
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