\documentclass[12pt,a4paper,reqno]{amsart}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\makeatletter
\def\@theoremfont{\it}
\def\slanttheorems{\def\@theoremfont{\sl}}

\def\@begintheorem#1#2[#3]{%
\@theoremfont\trivlist \global\setbox0=\hbox{\bf
 #1}\global\setbox1=\hbox{\bf #2}\item[\hskip \labelsep{\bf #1\ #2.}]}
\let\@opargbegintheorem\relax
\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\slanttheorems

\newcommand{\datop}[2]{\genfrac{}{}{0pt}{}{#1}{#2}}
\newcommand{\hyp}[3]{{}_{2}\!F_{1}\!\left(\left.\datop{#1}{#2}\right| #3 \right)}
\newcommand{\hyps}[3]{{{}_{2}\!F_{1}}^{\!\!2}\!\left(\left.\datop{#1}{#2}\right| #3 \right)}

\newcommand{\theoremname}{Theorem}
\newcommand{\lemmaname}{Lemma}
\newcommand{\corollaryname}{Corollary}
\newcommand{\propositionname}{Proposition}
\newcommand{\definitionname}{Definition}
\newcommand{\conjecturename}{Conjecture}
\newcommand{\claimname}{Claim}
\newcommand{\of}{of\ }
\newtheorem{theorem}{\theoremname}[section]
\newtheorem{lemma}{\lemmaname}[section]
\newtheorem{corollary}{\corollaryname}[section]
\newtheorem{proposition}{\propositionname}[section]
\newtheorem{defn}{\definitionname}[section]
\newtheorem{conjecture}{\conjecturename}[section]
\newtheorem{claim}{\claimname}[section]


\def\EE{\mathcal{E}}
\def\poch#1#2{#1^{\underline{#2}}}
\setlength{\textwidth}{6in}
\setlength{\textheight}{9in}
\setlength{\topmargin}{0cm}
\setlength{\oddsidemargin}{0cm}
\setlength{\evensidemargin}{0cm}

\sloppy

\title[Epidemics with two levels of mixing:
The exact moments]{Epidemics with two levels of mixing:\\
The exact moments}

\author{ Helmut Prodinger}

\address{Institut f{\"u}r Algebra und Diskrete Mathematik, Technical University
of Vienna, Wiedner Hauptstrasse 8-10, A-1040 Vienna, Austria.}

\email{Helmut.Prodinger@tuwien.ac.at}

\begin{document}


\maketitle

In \cite{BaMoSc97}, the probabilities
\begin{equation*}   
\binom{n-1}{k-1}p(pk)^{k-2}(1-pk)^{n-k},\qquad  (1\le k \le n)
\end{equation*}
where considered in the study of an epidemics model
(the `inverse model,' p. 83).

It was stated that the direct computation of the expected value
is difficult. In the present note we will show how it can be
done. We also sketch how all moments can be obtained.

\bigskip



It is somehow more appealing to change $k$ to $k-1$ and $n$ 
to $n+1$, i.~e. to consider the probabilities
\begin{equation*}   
\binom{n}{k}p(p+pk)^{k-1}(1-p-pk)^{n-k},\qquad  (0\le k \le n).
\end{equation*} 
We will compute the sum
\begin{equation*}   
\sum_{k=0}^n\binom{n}{k}(p+pk)^{k}(1-p-pk)^{n-k};
\end{equation*}
in this way, we can compute the expectation
 by a simple linear combination.
 Let us consider 
\begin{equation*}   
S:=\sum_{k=0}^n\binom{n}{k}(r+tk)^{k}(q+t(n-k))^{n-k};
\end{equation*}
with this  notation we are closer to the notation in
\cite{GrKnPa94}.
Because the sum $S $ is a convolution, it is natural to
consider the exponential generating function
\begin{equation*}   
\sum_{k\ge0}(r+tk)^{k}\frac{z^k}{k!}.
\end{equation*}
From
 \cite{GrKnPa94} we learn that it is related to the 
function
\begin{equation*}   
\EE(z)=\sum_{k\ge0}(tk+1)^{k-1}\frac{z^k}{k!},
\end{equation*}
which is also given implicitly by
\begin{equation*}   
z=\EE^{-t}\log\EE.
\end{equation*}
Thus (formula (5.61))
\begin{equation*}   
\sum_{k\ge0}(r+tk)^{k}\frac{z^k}{k!}
=\frac{\EE^r}{1-zt\EE^t}.
\end{equation*}
Likewise, 
\begin{equation*}   
\sum_{k\ge0}(q+tk)^{k}\frac{z^k}{k!}
=\frac{\EE^q}{1-zt\EE^t}.
\end{equation*}
Thus 
\begin{equation*}   
S=n![z^n]\frac{\EE^{q+r}}{(1-zt\EE^t)^2}.
\end{equation*}
In order to extract this coefficient, we set $\EE=e^u$, i.~e.
$z=ue^{-tu}$ and use Cauchy's integral formula
(equivalently, the Lagrange inversion formula could be used).
Note that $dz=(1-tu)e^{-tu}du$. Now
\begin{align*}
\frac{S}{n!}&=\frac{1}{2\pi i}\oint\frac{dz}{z^{n+1}}
\frac{\EE^{q+r}}{(1-zt\EE^t)^2}\\
&=\frac{1}{2\pi i}\oint
\frac{(1-tu)e^{-tu}du}{u^{n+1}e^{-(n+1)tu}}\frac{e^{u(q+r)}}{(1-tu)^2}\\
&=[u^n]\frac{1}{1-tu}e^{u(q+r+nt)}\\
&=\sum_{k=0}^n\frac{(q+r+nt)^k}{k!}t^{n-k}.
\end{align*} 

In our application, we have $r=t=p$ and $q=1-p-tn$, whence
\begin{equation*}   
S=n!\sum_{k=0}^n\frac{p^{n-k}}{k!}=
\sum_{k=0}^n\poch nk \,p^k.
\end{equation*} 
The functions
\begin{equation*}   
Q_r(m,n)=\binom{r}{0}+\binom{r+1}{1}\frac{n}{m}
+\binom{r+2}{2}\frac{n(n-1)}{m^2}+
\binom{r+3}{3}\frac{n(n-1)(n-2)}{m^3}+\dots
\end{equation*}
are known  as the generalized $Q$--functions of Ramanujan.
(See the recent papers \cite{Knuth98} and \cite{FlPoVi98}
and the references therein.) With this notation, we have
\begin{equation*}   
S=Q_0(\tfrac{1}{p},n).
\end{equation*}

\smallskip 

It is interesting to note that Maple knows this function
$\EE(z)$; it expresses it as
\begin{equation*}   
\EE(z)=e^{-W(-zt)/t},
\end{equation*} 
with the Lambert $W(z)$ 
function, defined by the relation $We^W=z$.

\smallskip 

In order to get higher moments also, we start from the 
exponential generating function
\begin{equation*}   
\EE(z)^r=\sum_{k\ge0}r(r+tk)^{k-1}\frac{z^k}{k!}
\end{equation*}
(formula (5.60) in \cite{GrKnPa94}).
We have solved our problem when we know how this function
behaves under repeated applications of the operator
$zD$, since these differentiations (followed by multiplications)
bring in the extra powers of $k$  that are needed for the 
higher moments. 
We obtain an especially nice form if we specialise $r=t$
(as is the case in our instance) and also apply the operator
$z(zD)^s$. Furthermore we express everything in the variable
$u$ (as before). Recall that $z=ue^{-tu}$    and
$E(z)=e^u$. Then
\begin{equation*}   
z(zD)^s\EE(z)^t=\frac{\text{polynomial in $u$ }}{(1-tu)^{2s-1}}.
\end{equation*} 
Reading off the coefficients in the convolution can now be done
as before, and this brings the general $Q$--functions into the game.








\vspace{3em}

\begin{thebibliography}{99}


\bibitem{BaMoSc97} F. Ball, 
D. Mollison and G. Scalia--Tomba. 
Epidemics with two levels of mixing.
Annals of Applied Probability,
 7 (1997), pp. 46--89.

\bibitem{FlPoVi98} P. Flajolet, P. Poblete, and
     A. Viola . 
On the Analysis of Linear Probing Hashing.
Algorithmica (to appear),
(1998).



\bibitem{GrKnPa94} R.~L. Graham, D.~E. Knuth, and O.~Patashnik.
\newblock {\em Concrete Mathematics (Second Edition)}.
\newblock Addison Wesley, 1994.


\bibitem{Knuth98} D.~E. Knuth. 
Linear Probing and Graphs.
Algorithmica (to appear),
(1998).






				




 \end{thebibliography}





\end{document}
