{"id":8476,"date":"2015-08-29T21:06:23","date_gmt":"2015-08-29T19:06:23","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=8476"},"modified":"2019-10-20T15:33:28","modified_gmt":"2019-10-20T13:33:28","slug":"about-the-central-multinomial-coefficient","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2015\/08\/29\/about-the-central-multinomial-coefficient\/","title":{"rendered":"About the central multinomial coefficient"},"content":{"rendered":"
\"Recent<\/a>
Recent edition of a book by James Stirling (1692 -- 1770)<\/figcaption><\/figure>\n

We have already listed many basic aspects of the multinomial law in a former post<\/a>. This post is devoted to an additional remark. Recall that the multinomial law<\/p>\n

\\[ \\mathcal{M}(n,p_1\\delta_{e_1}+\\cdots+p_d\\delta_{e_d}) \\]<\/p>\n

where \\( {e_1,\\ldots,e_d} \\) is the canonical basis of \\( {\\mathbb{R}^d} \\) is given by<\/p>\n

\\[ (p_1\\delta_{e_1}+\\cdots+p_d\\delta_{e_d})^{*n} =\\sum_{\\substack{(n_1,\\ldots,n_d)\\in\\mathbb{N}^d\\\\n_1+\\cdots+n_d=n}} \\binom{n}{n_1,\\ldots,n_d}p_1^{n_1}\\cdots p_d^{n_d}\\delta_{(a_1,\\ldots,a_d)} \\]<\/p>\n

where<\/p>\n

\\[ \\binom{n}{n_1,\\ldots,n_d} =\\frac{n!}{n_1!\\cdots n_d!} \\]<\/p>\n

is the multinomial coefficient. This distribution encodes \\( {n} \\) throws of a dice with \\( {d} \\) faces.<\/p>\n

Maximality of central multinomial coefficient.<\/b> It turns out that the map<\/p>\n

\\[ (n_1,\\ldots,n_d)\\mapsto\\binom{n}{n_1,\\ldots,n_d} \\]<\/p>\n

is maximized when \\( {n_1,\\ldots,n_d} \\) are all equal, more precisely as close as possible to each others due to discreteness. In other words, the central multinomial coefficient is the largest possible multinomial coefficient: for any \\( {d\\geq1} \\) and \\( {n\\geq1} \\),<\/p>\n

\\[ m_{n,d} :=\\max_{\\substack{(n_1,\\ldots,n_d)\\in\\mathbb{N}^d\\\\n_1+\\cdots+n_d=n}} \\frac{n!}{n_1!\\cdots n_d!} = \\frac{n!}{q!^{d-r}(q+1)!^r}. \\]<\/p>\n

where \\( {q:=n\\mod d} \\) in other words (Euclidean division)<\/p>\n

\\[ n=qd+r, \\quad 0\\leq r<d, \\]<\/p>\n

and in particular, if \\( {n=qd} \\) then<\/p>\n

\\[ m_{n,q}=m_{qd,d}=\\frac{n!}{q!^d}. \\]<\/p>\n

Namely if \\( {n_1+\\cdots+n_d=n} \\) and \\( {n_1<q} \\) then necessarily \\( {n_k\\geq q+1} \\) for some \\( {1\\leq k\\leq d} \\), and then, for instance in the case \\( {k=2} \\) to keep things simple,<\/p>\n

\\[ \\frac{n!}{n_1!\\cdots n_d!} <\\frac{n_2}{n_1+1}\\frac{n!}{n_1!\\cdots n_d!} =\\frac{n!}{(n_1+1)!(n_2-1)!n_3!\\cdots n_d!}. \\]<\/p>\n

This type of reasoning by monotonicity allows to establish that the maximum \\( {m_{n,d}} \\) is achieved when \\( {q\\leq n_k\\leq q+1} \\) for any \\( {1\\leq k\\leq n} \\), for instance by \\( {n_1=\\cdots=n_r=q+1} \\) and \\( {n_{r+1}=\\cdots=n_d=q} \\), hence the result.<\/p>\n

Application to simple random walk.<\/b> The simple symmetric random walk \\( {{(X_n)}_{n\\geq0}} \\) on \\( {\\mathbb{Z}^d} \\) is intimately associated to the multinomial law. Namely, for every \\( {n\\geq0} \\), the law of \\( {X_n-X_0} \\) is the image law of the multinomial law<\/p>\n

\\[ \\mathcal{M} \\left(n,\\sum_{x\\in\\{\\pm e_1,\\ldots,\\pm e_d\\}}\\frac{1}{2d}\\delta_x\\right) \\]<\/p>\n

by the map (we throw \\( {n} \\) times a dice with \\( {2d} \\) faces which are \\( {\\pm e_1,\\ldots,\\pm e_d} \\))<\/p>\n

\\[ (x_1,\\ldots,x_{2d})\\mapsto (x_1-x_2,\\ldots,x_{2d}-x_{2d-1}). \\]<\/p>\n

The sequence \\( {{(X_n)}_{n\\geq0}} \\) is an auto-regressive process, but also a homogeneous Markov chain with state space \\( {\\mathbb{Z}^d} \\) and transition kernel \\( {P(x,y)=\\mathbb{P}(X_1=y\\,|\\,X_0=x)} \\). The chain is irreducible and by parity has period \\( {2} \\). Moreover there is translation invariance and \\( {P(x,y)=P(0,y-x)} \\). It follows that the chain is recurrent if and only if the series \\( {\\sum_{n\\geq1}P^{2n}(0,0)} \\) is convergent. From the multinomial formula<\/p>\n

\\[ \\begin{array}{rcl} P^{2n}(0,0) &=&\\frac{1}{(2d)^{2n}} \\sum_{\\substack{n_1+\\cdots+n_{2d}=n\\\\n_1=n_2,\\ldots,n_{d-1}=n_d}} \\binom{2n}{n_1,\\ldots,n_{2d}}\\\\ &=&\\frac{1}{(2d)^{2n}}\\sum_{n_1+\\cdots+n_d=n} \\frac{(2n)!}{n_1!^2\\cdots n_d!^2}. \\end{array} \\]<\/p>\n

Case \\( {d=1} \\).<\/em> In this case the sum in the formula for \\( {P^{(2n)}(0,0)} \\) boils down to the central binomial coefficient \\( {\\binom{2n}{n}} \\), and the Stirling formula \\( {n!\\sim \\sqrt{2\\pi n}(n\/e)^n} \\) gives<\/p>\n

\\[ P^{2n}(0,0) =\\frac{1}{2^{2n}}\\frac{(2n)!}{n!^2} \\sim \\frac{1}{\\sqrt{\\pi n}}, \\]<\/p>\n

which is not sumable in \\( {n} \\) and therefore the chain is recurrent.<\/p>\n

Case<\/em> \\( {d=2} \\). The Vandermonde convolution identity for binomial coefficients<\/p>\n

\\[ \\binom{n+m}{r}=\\sum_{k=0}^r\\binom{n}{k}\\binom{m}{r-k} \\]<\/p>\n

gives<\/p>\n

\\[ \\begin{array}{rcl} P^{2n}(0,0) &=&\\frac{1}{4^{2n}}\\sum_{n_1+n_2=n}\\frac{(2n)!}{n_1!^2n_2!^2}\\\\ &=&\\frac{(2n)!}{4^{2n}n!^2} \\sum_{n_1+n_2=n}\\left(\\frac{n!}{n_1!n_2!}\\right)^2\\\\ &=&\\frac{(2n)!}{4^{2n}n!^2}\\sum_{k=0}^n\\binom{n}{k}^2 \\\\ &=&\\frac{(2n)!}{4^{2n}n!^2}\\frac{(2n)!}{n!^2} \\underset{n\\rightarrow\\infty}{\\sim}\\frac{1}{\\pi n} \\end{array} \\]<\/p>\n

which is not summable and thus the chain is recurrent. Note the appearance of the squared central binomial coefficient \\( {\\binom{2n}{n}^2} \\) in the last formula.<\/p>\n

Case<\/em> \\( {d=3} \\). The multinomial formula gives<\/p>\n

\\[ \\begin{array}{rcl} P^{2n}(0,0) &=&\\frac{1}{6^{2n}}\\sum_{n_1+n_2+n_3=n}\\frac{(2n)!}{n_1!^2n_2!^2n_3!^2}\\\\ &=&\\frac{(2n)!}{2^{2n}3^nn!^2}\\sum_{n_1+n_2+n_3=n}\\binom{n}{n_1, n_2, n_3}^2 \\left(\\frac{1}{3}\\right)^{n}. \\end{array} \\]<\/p>\n

Now if \\( {n=3m} \\) then \\( {\\binom{n}{n_1, n_2, n_3}\\leq \\binom{n}{m, m, m}} \\) and thus, thanks to the multinomial formula of size \\( {n} \\) and parameter \\( {(1\/3,1\/3,1\/3)} \\), we get, for \\( {n=3m} \\),<\/p>\n

\\[ P^{2n}(0,0) \\leq \\frac{(2n)!}{2^{2n}3^nn!^2}\\binom{n}{m, m, m} \\sim \\frac{1}{2}\\left(\\frac{3}{\\pi n}\\right)^{3\/2} =\\frac{c}{n^{3\/2}}, \\]<\/p>\n

thus<\/p>\n

\\[ \\sum_mP^{6m}(0,0)<\\infty. \\]<\/p>\n

Since \\( {(1\/6)^{2k}P^{6m}(0,0)\\leq P^{6m+2k}(0,0)} \\) for \\( {k=1,2} \\), we get<\/p>\n

\\[ \\sum_nP^{2n}(0,0)=\\sum_{k=0,1,2}\\sum_mP^{6m+2k}(0,0)<\\infty \\]<\/p>\n

and therefore the chain is transcient.<\/p>\n

Case<\/em> \\( {d\\geq3} \\). We have<\/p>\n

\\[ \\begin{array}{rcl} P^{2n}(0,0) &=&\\frac{1}{(2d)^{2n}} \\sum_{n_1+\\cdots+n_d=n}\\frac{(2n)!}{n_1!^2\\cdots n_d!^2}\\\\ &=&\\frac{(2n)!}{n!^2(4d)^n} \\sum_{n_1+\\cdots+n_d=n} \\left(\\frac{n!}{n_1!^2\\cdots n_d!^2}\\right)^2\\left(\\frac{1}{d}\\right)^n. \\end{array} \\]<\/p>\n

We have<\/p>\n

\\[ \\begin{array}{rcl} P^{2n}(0,0) &\\leq& \\frac{(2n)!m_n}{n!^2(4d)^n} \\sum_{n_1+\\cdots+n_d=n}\\frac{n!}{n_1!\\cdots n_d!}\\left(\\frac{1}{d}\\right)^n\\\\ &=&\\frac{(2n)!m_n}{n!^2(4d)^n} \\sim \\frac{m_n}{d^n\\sqrt{\\pi n}} \\end{array} \\]<\/p>\n

where \\( {m_n=m_{n,d}} \\) is the maximal value of the multinomial coefficient<\/p>\n

\\[ \\binom{n}{n_1,\\ldots,n_d}=\\frac{n!}{n_1!\\cdots n_d!} \\]<\/p>\n

on<\/p>\n

\\[ \\{(n_1,\\ldots,n_d)\\in\\mathbb{N}^d:n_1+\\cdots+n_d=n\\}. \\]<\/p>\n

Since \\( {m_{n+1}\/m_n=(n+1)\/(q+1)\\leq d} \\), the sequence \\( {{(m_n\/d^n)}_{n\\geq1}} \\) is \\( {\\searrow} \\) and thus<\/p>\n

\\[ \\begin{array}{rcl} \\sum_n\\frac{m_n}{d^n\\sqrt{n}} &=&\\sum_q\\sum_{n=qd}^{(q+1)d-1}\\frac{m_n}{d^n\\sqrt{n}}\\\\ &\\leq& \\sum_q\\frac{1}{\\sqrt{q}}\\sum_{n=qd}^{(q+1)d-1}\\frac{m_n}{d^n}\\\\ &\\leq& \\sum_q\\frac{dm_{qd}}{d^{qd}\\sqrt{q}}. \\end{array} \\]<\/p>\n

Now the value of \\( {m_d} \\) and the Stirling formula give, as \\( {q\\rightarrow\\infty} \\),<\/p>\n

\\[ \\frac{m_{qd}}{d^{qd}\\sqrt{q}} =\\frac{(dq)!}{d^{dq}q!^d\\sqrt{q}} \\sim \\frac{\\sqrt{d}}{(2\\pi)^{(d-1)\/2}q^{d\/2}}. \\]<\/p>\n

But \\( {d\\geq3} \\) and thus \\( {\\sum_qq^{-d\/2}<\\infty} \\), which gives<\/p>\n

\\[ \\sum_nP^{2n}(0,0)<\\infty, \\]<\/p>\n

and therefore the chain is transcient.<\/p>\n","protected":false},"excerpt":{"rendered":"

We have already listed many basic aspects of the multinomial law in a former post. This post is devoted to an additional remark. Recall that…<\/p>\n

Continue readingAbout the central multinomial coefficient<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"iawp_total_views":809},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/8476"}],"collection":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/comments?post=8476"}],"version-history":[{"count":8,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/8476\/revisions"}],"predecessor-version":[{"id":11657,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/8476\/revisions\/11657"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=8476"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=8476"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=8476"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}