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$
  • 1
    $\begingroup$ Use Stirling’s formula? $\endgroup$ – Anthony Quas 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})$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is it $(n) +k/2$ or $(n+k)/2$ in exponent? $\endgroup$ – VS. Jan 30 at 21:59
  • $\begingroup$ @VS. : Everything seems correct as written. Why the doubt? $\endgroup$ – Iosif Pinelis Jan 31 at 1:34
  • $\begingroup$ Pretty sure it was $(n)+k/2$ that you implied but nevertheless wanted to be sure. $\endgroup$ – VS. Jan 31 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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @Iosif Pinelis above has the correct version of what I was trying to say... $\endgroup$ – Anthony Quas 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 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.$

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ I believe the OP is asking for more precise asymptotics than this (this is describing the denominator but not the numerator). $\endgroup$ – Anthony Quas 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
  • 5
    $\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$ – Anthony Quas Oct 26 '19 at 17:51
  • 5
    $\begingroup$ This is my personal algebra. Take $a_1=\ldots=a_k=1/k$ and multiply. $\endgroup$ – Anthony Quas 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$ – Anthony Quas 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.