7
$\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 '19 at 19:51
  • 1
    $\begingroup$ Well not clear to me how expression behaves under multiple parameters. $\endgroup$
    – VS.
    Oct 25 '19 at 20:12
7
$\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=1,\dots,k$. Let \begin{equation} h_i:=\frac kn\,a_i-1=o(n^{-1/3}). \end{equation} By Stirling's formula: \begin{equation} m!\sim\sqrt{2\pi m}(m/e)^m \end{equation} as $m\to\infty$,
\begin{equation} \binom{n}{a_1,\ldots,a_k} \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} Since $(1+h)\ln(1+h)=h+h^2/2+O(|h|^3)$ as $h\to0$, $\sum_{i=1}^k h_i=0$, and $h_i=o(n^{-1/3})$, we have \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} Collecting the pieces, we get \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 '20 at 21:59
  • $\begingroup$ @VS. : Everything seems correct as written. Why the doubt? $\endgroup$ Jan 31 '20 at 1:34
  • $\begingroup$ Pretty sure it was $(n)+k/2$ that you implied but nevertheless wanted to be sure. $\endgroup$
    – VS.
    Jan 31 '20 at 1:40
4
$\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 '19 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 '20 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 '19 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 '19 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 '19 at 17:51
  • 5
    $\begingroup$ This is my personal algebra. Take $a_1=\ldots=a_k=1/k$ and multiply. $\endgroup$ Oct 26 '19 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 '19 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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