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.
2 Comments