# Month: August 2015

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 the multinomial law

$\mathcal{M}(n,p_1\delta_{e_1}+\cdots+p_d\delta_{e_d})$

where ${e_1,\ldots,e_d}$ is the canonical basis of ${\mathbb{R}^d}$ is given by

$(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)}$

where

$\binom{n}{n_1,\ldots,n_d} =\frac{n!}{n_1!\cdots n_d!}$

is the multinomial coefficient. This distribution encodes ${n}$ throws of a dice with ${d}$ faces.

Maximality of central multinomial coefficient. It turns out that the map

$(n_1,\ldots,n_d)\mapsto\binom{n}{n_1,\ldots,n_d}$

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}$,

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

where ${q:=n\mod d}$ in other words (Euclidean division)

$n=qd+r, \quad 0\leq r<d,$

and in particular, if ${n=qd}$ then

$m_{n,q}=m_{qd,d}=\frac{n!}{q!^d}.$

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,

$\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!}.$

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.

Application to simple random walk. 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

$\mathcal{M} \left(n,\sum_{x\in\{\pm e_1,\ldots,\pm e_d\}}\frac{1}{2d}\delta_x\right)$

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

$(x_1,\ldots,x_{2d})\mapsto (x_1-x_2,\ldots,x_{2d}-x_{2d-1}).$

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

$\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}$

Case ${d=1}$. 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^{2n}(0,0) =\frac{1}{2^{2n}}\frac{(2n)!}{n!^2} \sim \frac{1}{\sqrt{\pi n}},$

which is not sumable in ${n}$ and therefore the chain is recurrent.

Case ${d=2}$. The Vandermonde convolution identity for binomial coefficients

$\binom{n+m}{r}=\sum_{k=0}^r\binom{n}{k}\binom{m}{r-k}$

gives

$\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}$

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.

Case ${d=3}$. The multinomial formula gives

$\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}$

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^{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}},$

thus

$\sum_mP^{6m}(0,0)<\infty.$

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

$\sum_nP^{2n}(0,0)=\sum_{k=0,1,2}\sum_mP^{6m+2k}(0,0)<\infty$

and therefore the chain is transcient.

Case ${d\geq3}$. We have

$\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}$

We have

$\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}$

where ${m_n=m_{n,d}}$ is the maximal value of the multinomial coefficient

$\binom{n}{n_1,\ldots,n_d}=\frac{n!}{n_1!\cdots n_d!}$

on

$\{(n_1,\ldots,n_d)\in\mathbb{N}^d:n_1+\cdots+n_d=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

$\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}$

Now the value of ${m_d}$ and the Stirling formula give, as ${q\rightarrow\infty}$,

$\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}}.$

But ${d\geq3}$ and thus ${\sum_qq^{-d/2}<\infty}$, which gives

$\sum_nP^{2n}(0,0)<\infty,$

and therefore the chain is transcient.