9
$\begingroup$

Binomial coefficients have a well known asymptotics (https://en.wikipedia.org/wiki/Binomial_coefficient#Bounds_and_asymptotic_formulas) given by $$\binom nk\sim\binom{n}{\frac{n}{2}} e^{-d^2/(2n)} \sim \frac{2^n}{\sqrt{\frac{1}{2}n \pi }} e^{-d^2/(2n)}.$$

Is there corresponding asymptotics for multinomials (I am more interested in what happens analogously in the denominator)?

$\endgroup$
2
  • 1
    $\begingroup$ Use Stirling’s formula? $\endgroup$ Oct 25, 2019 at 19:51
  • 1
    $\begingroup$ Well not clear to me how expression behaves under multiple parameters. $\endgroup$
    – VS.
    Oct 25, 2019 at 20:12

3 Answers 3

9
$\begingroup$

Suppose that $k$ is a fixed natural number, $n\to\infty$, and \begin{equation*} a_i=\frac nk+o(n^{2/3}) \end{equation*} for each $i$; here in what follows, $i\in\{1,\dots,k\}$. Let \begin{equation*} h_i:=\frac kn\,a_i-1=o(n^{-1/3}), \tag{1} \end{equation*} so that $h_i\to0$ and \begin{equation} a_i=\frac nk\,(1+h_i). \tag{2} \end{equation} By Stirling's formula, \begin{equation*} n!\sim(2\pi)^{1/2} n^{1/2}\Big(\frac ne\Big)^n \end{equation*} and, by (2), \begin{equation*} \begin{aligned} a_i!&\sim(2\pi)^{1/2} \Big(\frac nk\Big)^{1/2}(1+h_i)^{1/2}\Big(\frac n{ke}(1+h_i)\Big)^{a_i} \\ &\sim(2\pi)^{1/2} \Big(\frac nk\Big)^{1/2}\Big(\frac n{ke}(1+h_i)\Big)^{a_i}. \end{aligned} \end{equation*} Therefore and because $\sum_{i=1}^k a_i=n$, \begin{equation*} \prod_{i=1}^k a_i!\sim(2\pi)^{k/2} \Big(\frac nk\Big)^{k/2}\Big(\frac n{ke}\Big)^n \prod_{i=1}^k(1+h_i)^{a_i}, \end{equation*} which implies \begin{equation*} \binom{n}{a_1,\ldots,a_k}=\frac{n!}{\prod_{i=1}^k a_i!} \sim(2\pi)^{1/2-k/2}\frac{n^{1/2}}{(n/k)^{k/2}}\frac{k^n}{e^u}, \end{equation*} where \begin{equation*} u:=\sum_{i=1}^k a_i\ln(1+h_i)=\frac nk\sum_{i=1}^k (1+h_i)\ln(1+h_i), \end{equation*} by (2). Note also that (i) $(1+h)\ln(1+h)=h+h^2/2+O(|h|^3)$ as $h\to0$, (ii) $\sum_{i=1}^k h_i=0$ (by the definition of $h_i$ in (1) and the condition $\sum_{i=1}^k a_i=n$), and (iii) $h_i=o(n^{-1/3})$. It follows that \begin{equation*} u=\frac n{2k}\,\sum_{i=1}^k h_i^2+o(1)=\frac k{2n}\,\sum_{i=1}^k(a_i-n/k)^2+o(1). \end{equation*} Thus,
\begin{equation*} \binom{n}{a_1,\ldots,a_k} \sim(2\pi n)^{1/2-k/2}k^{n+k/2}\exp\Big\{-\frac k{2n}\,\sum_{i=1}^k(a_i-n/k)^2\Big\}. \end{equation*}

In particular, when $k=2$, we get the Wikipedia result quoted in the OP: \begin{equation*} \binom na\sim\frac{2^n}{\sqrt{\pi n/2 }} e^{-2(a-n/2)^2/n} \end{equation*} if $n\to\infty$ and $a=\frac n2+o(n^{2/3})$.

$\endgroup$
3
  • $\begingroup$ Is it $(n) +k/2$ or $(n+k)/2$ in exponent? $\endgroup$
    – VS.
    Jan 30, 2020 at 21:59
  • $\begingroup$ @VS. : Everything seems correct as written. Why the doubt? $\endgroup$ Jan 31, 2020 at 1:34
  • $\begingroup$ Pretty sure it was $(n)+k/2$ that you implied but nevertheless wanted to be sure. $\endgroup$
    – VS.
    Jan 31, 2020 at 1:40
5
$\begingroup$

The analogous estimate in the range where your formula is valid (that is, $a_i=\frac nk+o(n^{1/2})$ - note Wikipedia claims the binomial case is valid for $a_i=\frac n2+o(n^{2/3})$, but I wasn't able to reproduce that estimate) is: $$ \binom{n}{a_1\ a_2\ \ldots\ a_k} \sim \frac{k^n}{(2\pi n)^{(k-1)/2}}\exp\left(-\frac kn\sum_{i=1}^k b_i^2\right), $$ where $b_i=a_i-\frac nk$, that is the difference of $a_i$ from its central value.

This can be obtained by using Stirling's formula, and estimates on quantities of the form $(1+\frac an)^n$.

$\endgroup$
2
  • $\begingroup$ @Iosif Pinelis above has the correct version of what I was trying to say... $\endgroup$ Oct 27, 2019 at 20:50
  • $\begingroup$ Doesn't $o(n^{2/3})$ seem wrong? For $n/2 - k = O(n^k)$ where $1/2 < k < 2/3$, the position of $k$ in the normal approximation would keep moving to the left, wouldn't it? (If you get my meaning.) $\endgroup$
    – Eric Auld
    Apr 14, 2020 at 16:32
1
$\begingroup$

Up to Theorem 5 in this article by Raygorodskiy, $${\lfloor na_1 \rfloor +\lfloor na_2 \rfloor\,+ \dots +\lfloor na_k \rfloor\ \choose \lfloor na_1 \rfloor ,\,\lfloor na_2 \rfloor , \, \dots , \lfloor na_k \rfloor\,} =\left(\frac 1 {a_1^{a_1}a_2^{a_2}\cdots a_k^{a_k}}+o(1)\right)^n$$ as $n\to \infty$, assuming $a_j>0,\ j=1\dots k,$ and $a_1+a_2+\cdots+a_k=1.$

$\endgroup$
7
  • 4
    $\begingroup$ I believe the OP is asking for more precise asymptotics than this (this is describing the denominator but not the numerator). $\endgroup$ Oct 26, 2019 at 16:21
  • $\begingroup$ @ Anthony Quas: Thank you for your personal opinion. Criticism should be constructive. Can you present another asymptotics? TIA. $\endgroup$
    – user64494
    Oct 26, 2019 at 17:05
  • 6
    $\begingroup$ I refer to the original question; not to my personal opinion. By the way: the original question does include more precise asymptotics in the binomial case, and the OP is fairly explicitly asking for similarly precise asymptotics in the multinomial case.in the central case the OP is asking about, your asymptotics are simply $(k+o(1))^n$, whereas I believe the OP is looking for something like $Ck^n/n^{(k-1)/2}$. $\endgroup$ Oct 26, 2019 at 17:51
  • 6
    $\begingroup$ This is my personal algebra. Take $a_1=\ldots=a_k=1/k$ and multiply. $\endgroup$ Oct 26, 2019 at 19:50
  • 3
    $\begingroup$ The estimate that the OP quoted is (per the Wikipedia page that he cites) valid for $k=n/2+o(n^{2/3})$. The estimate that I hinted at (once the Gaussian decay term is included) should hold in the corresponding range: $a_i=n/k+o(n^{2/3})$. $\endgroup$ Oct 26, 2019 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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