EPIDEMICS WITH TWO LEVELS OF MIXING: THE EXACT MOMENTS

HELMUT PRODINGER

In [1], the probabilities

\binom{n − 1}{k − 1}p(pk)^{k−2}(1 − pk)^{n−k}, (1 ≤ k ≤ n)

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.

It is somehow more appealing to change k to k − 1 and n to n + 1, i. e. to consider the probabilities

\binom{n}{k}p(p + pk)^{k−1}(1 − p − pk)^{n−k}, (0 ≤ k ≤ n).

We will compute the sum

∑_{k=0}^{n} \binom{n}{k}(p + pk)^{k}(1 − p − pk)^{n−k};

in this way, we can compute the expectation by a simple linear combination. Let us consider

S := ∑_{k=0}^{n} \binom{n}{k}(r + tk)^{k}(q + t(n − k))^{n−k};

with this notation we are closer to the notation in [3]. Because the sum S is a convolution, it is natural to consider the exponential generating function

∑_{k≥0}(r + tk)^{k} \frac{z^{k}}{k!} .

From [3] we learn that it is related to the function

E(z) = ∑_{k≥0}(tk + 1)^{k−1} \frac{z^{k}}{k!} ,

which is also given implicitly by

z = E^{−t} log E.

Thus (formula (5.61))

∑_{k≥0}(r + tk)^{k} \frac{z^{k}}{k!} = \frac{E^{r}}{1 − ztE^{t}} .

Likewise,

∑_{k≥0}(q + tk)^{k} \frac{z^{k}}{k!} = \frac{E^{q}}{1 − ztE^{t}} .

Thus

S = n![z^{n}]\frac{E^{q+r}}{(1 − ztE^{t})^{2}} .

In order to extract this coefficient, we set E = 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

\frac{S}{n!} = \frac{1}{2πi} ∮ \frac{dz}{z^{n+1}} \frac{E^{q+r}}{(1 − ztE^{t})^{2}}

= \frac{1}{2πi} ∮ \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)}

= ∑_{k=0}^{n} \frac{(q + r + nt)^{k}}{k!} t^{n−k}.

In our application, we have r = t = p and q = 1 − p − tn, whence

S = n! ∑_{k=0}^{n} \frac{p^{n−k}}{k!} = ∑_{k=0}^{n} n\underline{k} p^{k}.

The functions

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}} + …

are known as the generalized Q–functions of Ramanujan. (See the recent papers [4] and [2] and the references therein.) With this notation, we have

S = Q_{0}(\frac{1}{p}, n).

It is interesting to note that Maple knows this function E(z); it expresses it as

E(z) = e^{−W (−zt)/t},

with the Lambert W (z) function, defined by the relation W e^{W} = z.

In order to get higher moments also, we start from the exponential generating function

E(z)^{r} = ∑_{k≥0} r(r + tk)^{k−1} \frac{z^{k}}{k!}

(formula (5.60) in [3]). 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

z(zD)^{s}E(z)^{t} = \frac{polynomial in u}{(1 − tu)^{2s−1}} .

Reading off the coefficients in the convolution can now be done as before, and this brings the general Q–functions into the game.

References

[1] F. Ball, D. Mollison and G. Scalia–Tomba. Epidemics with two levels of mixing. Annals of Applied Probability, 7 (1997), pp. 46–89.

[2] P. Flajolet, P. Poblete, and A. Viola . On the Analysis of Linear Probing Hashing. Algorithmica (to appear), (1998).

[3] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics (Second Edition). Addison Wesley, 1994.

[4] D. E. Knuth. Linear Probing and Graphs. Algorithmica (to appear), (1998).

Institut für Algebra und Diskrete Mathematik, Technical University of Vienna, Wiedner Hauptstrasse 8-10, A-1040 Vienna, Austria.

 E-mail address: Helmut.Prodinger@tuwien.ac.at