Return to Answer

typo corrected

Source Link

edited Mar 21, 2018 at 21:06

3.3k
11
15

Here is an approach via Lagrange inversion.

Let $N$ denote the time of the first repeat, and let $T(z)$ (the ``tree function'') be the formal power series satisfying $T(z)=z\,e^{T(z)}$.

If $F$ is a formal power series the coefficients of $G(z):=F(T(z))$ are given by (Lagrange inversion) $$[z^0]G(z)=[z^0] F(z) \mbox{ , } [z^k]G(z)=\tfrac{1}{k} [y^{k-1}] F^\prime(y)\,e^{ky} =[y^k](1-y)F(y)\,e^{ky}\mbox{ for } k\geq 1\;.$$ In particular
$$[z^m] T(z)^k=\frac{k}{m} \frac{m^{m-k}}{(m-k)!}\mbox{ and } \frac{1}{1-T(z)}=\sum_{n\geq 0}\frac{n^{n}}{n!}z^n$$ Using the first relation it is easily seen that the generating function of $N$ may be written as $$\mathbb{E} t^N=\frac{m!}{m^m} [z^m]\frac{t}{1- tT(z)}$$ Thus the binomial moments $\mathbb{E}{N \choose k}$ of $N$ can be obtained as $$\mathbb{E}{N \choose k} = \frac{m!}{m^m} [z^m t^k]\frac{1+t}{1- (1+t)T(z)}=\frac{m!}{m^m} [z^m ]\frac{T(x)^{k-1}}{(1- T(z))^{k+1}}$$ Differentiation shows that $z\,T^\prime(z)= \frac{T(z)}{1-T(z)}$. Therefore \begin{align*} \mathbb{E}{N \choose 2} &=\frac{m!}{m^m} [z^m ]\frac{T(z)}{(1- T(z))^{3}}\\ &=\frac{m!}{m^m} [z^{m-1} ]\frac{T^\prime(z)}{(1- T(z))^{2}}\\ &=\frac{m!}{m^m} [z^{m-1} ]\big(\frac{1}{1- T(z)}\big)^\prime\\ &=\frac{m!}{m^m} m\,[z^{m} ]\frac{1}{1- T(z)} =m\end{align*} (I don't know who first observed that.) Similarly \begin{align*} \mathbb{E}{N \choose 4} &=\frac{m!}{m^m} [z^m ]\frac{T(z)^3}{(1- T(z))^{5}}\\ &=\frac{m!}{m^m} [z^{m-1} ] T^\prime(z)\frac{T(z)^2}{(1- T(z))^{4}}\\ &=\frac{m!}{m^m} [z^{m-1} ]\big(\frac{1}{1- T(z)}-\frac{2}{3}\frac{1}{(1-T(z))^2}+\frac{1}{3}\frac{T(z)}{(1-T(z))^3}\big)^\prime\\ &=\frac{m!}{m^m} m\,[z^{m}]\big(\frac{1}{1- T(z)}-\frac{2}{3}\frac{1}{(1-T(z))^2}+\frac{1}{3}\frac{T(z)}{(1-T(z))^3}\big)\\ &=\frac{m^2}{3} +m -\frac{2}{3}\,\mathbb{E}(N)\end{align*}\begin{align*} \mathbb{E}{N \choose 4} &=\frac{m!}{m^m} [z^m ]\frac{T(z)^3}{(1- T(z))^{5}}\\ &=\frac{m!}{m^m} [z^{m-1} ] T^\prime(z)\frac{T(z)^2}{(1- T(z))^{4}}\\ &=\frac{m!}{m^m} [z^{m-1} ]\big(\frac{1}{1- T(z)}-\frac{2}{3}\frac{1}{(1-T(z))^2}+\frac{1}{3}\frac{T(z)}{(1-T(z))^3}\big)^\prime\\ &=\frac{m!}{m^m} m\,[z^{m}]\big(\frac{1}{1- T(z)}-\frac{2}{3}\frac{1}{(1-T(z))^2}+\frac{1}{3}\frac{T(z)}{(1-T(z))^3}\big)\\ &=\frac{m^2}{3} +m -\frac{2}{3} m\,\mathbb{E}(N)\end{align*} Clearly other binomial moments can be treated in the same way.

Here is an approach via Lagrange inversion.

Let $N$ denote the time of the first repeat, and let $T(z)$ (the ``tree function'') be the formal power series satisfying $T(z)=z\,e^{T(z)}$.

If $F$ is a formal power series the coefficients of $G(z):=F(T(z))$ are given by (Lagrange inversion) $$[z^0]G(z)=[z^0] F(z) \mbox{ , } [z^k]G(z)=\tfrac{1}{k} [y^{k-1}] F^\prime(y)\,e^{ky} =[y^k](1-y)F(y)\,e^{ky}\mbox{ for } k\geq 1\;.$$ In particular
$$[z^m] T(z)^k=\frac{k}{m} \frac{m^{m-k}}{(m-k)!}\mbox{ and } \frac{1}{1-T(z)}=\sum_{n\geq 0}\frac{n^{n}}{n!}z^n$$ Using the first relation it is easily seen that the generating function of $N$ may be written as $$\mathbb{E} t^N=\frac{m!}{m^m} [z^m]\frac{t}{1- tT(z)}$$ Thus the binomial moments $\mathbb{E}{N \choose k}$ of $N$ can be obtained as $$\mathbb{E}{N \choose k} = \frac{m!}{m^m} [z^m t^k]\frac{1+t}{1- (1+t)T(z)}=\frac{m!}{m^m} [z^m ]\frac{T(x)^{k-1}}{(1- T(z))^{k+1}}$$ Differentiation shows that $z\,T^\prime(z)= \frac{T(z)}{1-T(z)}$. Therefore \begin{align*} \mathbb{E}{N \choose 2} &=\frac{m!}{m^m} [z^m ]\frac{T(z)}{(1- T(z))^{3}}\\ &=\frac{m!}{m^m} [z^{m-1} ]\frac{T^\prime(z)}{(1- T(z))^{2}}\\ &=\frac{m!}{m^m} [z^{m-1} ]\big(\frac{1}{1- T(z)}\big)^\prime\\ &=\frac{m!}{m^m} m\,[z^{m} ]\frac{1}{1- T(z)} =m\end{align*} (I don't know who first observed that.) Similarly \begin{align*} \mathbb{E}{N \choose 4} &=\frac{m!}{m^m} [z^m ]\frac{T(z)^3}{(1- T(z))^{5}}\\ &=\frac{m!}{m^m} [z^{m-1} ] T^\prime(z)\frac{T(z)^2}{(1- T(z))^{4}}\\ &=\frac{m!}{m^m} [z^{m-1} ]\big(\frac{1}{1- T(z)}-\frac{2}{3}\frac{1}{(1-T(z))^2}+\frac{1}{3}\frac{T(z)}{(1-T(z))^3}\big)^\prime\\ &=\frac{m!}{m^m} m\,[z^{m}]\big(\frac{1}{1- T(z)}-\frac{2}{3}\frac{1}{(1-T(z))^2}+\frac{1}{3}\frac{T(z)}{(1-T(z))^3}\big)\\ &=\frac{m^2}{3} +m -\frac{2}{3}\,\mathbb{E}(N)\end{align*} Clearly other binomial moments can be treated in the same way.

Here is an approach via Lagrange inversion.

Let $N$ denote the time of the first repeat, and let $T(z)$ (the ``tree function'') be the formal power series satisfying $T(z)=z\,e^{T(z)}$.

If $F$ is a formal power series the coefficients of $G(z):=F(T(z))$ are given by (Lagrange inversion) $$[z^0]G(z)=[z^0] F(z) \mbox{ , } [z^k]G(z)=\tfrac{1}{k} [y^{k-1}] F^\prime(y)\,e^{ky} =[y^k](1-y)F(y)\,e^{ky}\mbox{ for } k\geq 1\;.$$ In particular
$$[z^m] T(z)^k=\frac{k}{m} \frac{m^{m-k}}{(m-k)!}\mbox{ and } \frac{1}{1-T(z)}=\sum_{n\geq 0}\frac{n^{n}}{n!}z^n$$ Using the first relation it is easily seen that the generating function of $N$ may be written as $$\mathbb{E} t^N=\frac{m!}{m^m} [z^m]\frac{t}{1- tT(z)}$$ Thus the binomial moments $\mathbb{E}{N \choose k}$ of $N$ can be obtained as $$\mathbb{E}{N \choose k} = \frac{m!}{m^m} [z^m t^k]\frac{1+t}{1- (1+t)T(z)}=\frac{m!}{m^m} [z^m ]\frac{T(x)^{k-1}}{(1- T(z))^{k+1}}$$ Differentiation shows that $z\,T^\prime(z)= \frac{T(z)}{1-T(z)}$. Therefore \begin{align*} \mathbb{E}{N \choose 2} &=\frac{m!}{m^m} [z^m ]\frac{T(z)}{(1- T(z))^{3}}\\ &=\frac{m!}{m^m} [z^{m-1} ]\frac{T^\prime(z)}{(1- T(z))^{2}}\\ &=\frac{m!}{m^m} [z^{m-1} ]\big(\frac{1}{1- T(z)}\big)^\prime\\ &=\frac{m!}{m^m} m\,[z^{m} ]\frac{1}{1- T(z)} =m\end{align*} (I don't know who first observed that.) Similarly \begin{align*} \mathbb{E}{N \choose 4} &=\frac{m!}{m^m} [z^m ]\frac{T(z)^3}{(1- T(z))^{5}}\\ &=\frac{m!}{m^m} [z^{m-1} ] T^\prime(z)\frac{T(z)^2}{(1- T(z))^{4}}\\ &=\frac{m!}{m^m} [z^{m-1} ]\big(\frac{1}{1- T(z)}-\frac{2}{3}\frac{1}{(1-T(z))^2}+\frac{1}{3}\frac{T(z)}{(1-T(z))^3}\big)^\prime\\ &=\frac{m!}{m^m} m\,[z^{m}]\big(\frac{1}{1- T(z)}-\frac{2}{3}\frac{1}{(1-T(z))^2}+\frac{1}{3}\frac{T(z)}{(1-T(z))^3}\big)\\ &=\frac{m^2}{3} +m -\frac{2}{3} m\,\mathbb{E}(N)\end{align*} Clearly other binomial moments can be treated in the same way.

Source Link

created Mar 21, 2018 at 20:46

esg

3.3k
11
15

Here is an approach via Lagrange inversion.

Let $N$ denote the time of the first repeat, and let $T(z)$ (the ``tree function'') be the formal power series satisfying $T(z)=z\,e^{T(z)}$.

If $F$ is a formal power series the coefficients of $G(z):=F(T(z))$ are given by (Lagrange inversion) $$[z^0]G(z)=[z^0] F(z) \mbox{ , } [z^k]G(z)=\tfrac{1}{k} [y^{k-1}] F^\prime(y)\,e^{ky} =[y^k](1-y)F(y)\,e^{ky}\mbox{ for } k\geq 1\;.$$ In particular
$$[z^m] T(z)^k=\frac{k}{m} \frac{m^{m-k}}{(m-k)!}\mbox{ and } \frac{1}{1-T(z)}=\sum_{n\geq 0}\frac{n^{n}}{n!}z^n$$ Using the first relation it is easily seen that the generating function of $N$ may be written as $$\mathbb{E} t^N=\frac{m!}{m^m} [z^m]\frac{t}{1- tT(z)}$$ Thus the binomial moments $\mathbb{E}{N \choose k}$ of $N$ can be obtained as $$\mathbb{E}{N \choose k} = \frac{m!}{m^m} [z^m t^k]\frac{1+t}{1- (1+t)T(z)}=\frac{m!}{m^m} [z^m ]\frac{T(x)^{k-1}}{(1- T(z))^{k+1}}$$ Differentiation shows that $z\,T^\prime(z)= \frac{T(z)}{1-T(z)}$. Therefore \begin{align*} \mathbb{E}{N \choose 2} &=\frac{m!}{m^m} [z^m ]\frac{T(z)}{(1- T(z))^{3}}\\ &=\frac{m!}{m^m} [z^{m-1} ]\frac{T^\prime(z)}{(1- T(z))^{2}}\\ &=\frac{m!}{m^m} [z^{m-1} ]\big(\frac{1}{1- T(z)}\big)^\prime\\ &=\frac{m!}{m^m} m\,[z^{m} ]\frac{1}{1- T(z)} =m\end{align*} (I don't know who first observed that.) Similarly \begin{align*} \mathbb{E}{N \choose 4} &=\frac{m!}{m^m} [z^m ]\frac{T(z)^3}{(1- T(z))^{5}}\\ &=\frac{m!}{m^m} [z^{m-1} ] T^\prime(z)\frac{T(z)^2}{(1- T(z))^{4}}\\ &=\frac{m!}{m^m} [z^{m-1} ]\big(\frac{1}{1- T(z)}-\frac{2}{3}\frac{1}{(1-T(z))^2}+\frac{1}{3}\frac{T(z)}{(1-T(z))^3}\big)^\prime\\ &=\frac{m!}{m^m} m\,[z^{m}]\big(\frac{1}{1- T(z)}-\frac{2}{3}\frac{1}{(1-T(z))^2}+\frac{1}{3}\frac{T(z)}{(1-T(z))^3}\big)\\ &=\frac{m^2}{3} +m -\frac{2}{3}\,\mathbb{E}(N)\end{align*} Clearly other binomial moments can be treated in the same way.