COMMENTS ON THE ANALYSIS OF

PARAMETERS IN A RANDOM GRAPH MODEL

Helmut Prodinger

Technical University of Vienna Department of Algebra and Discrete Mathematics

Abstract. Using generating functions and classical identities due to Euler and Gauss we can extend and simplify some of the results in the paper “Performance Considerations on a Random Graph Model for Parallel Processing”, RAIRO Theoretical Informatics and Applications 27 (1993), 367–388 by Afrati and Stafylopatis.

1. Introduction

In the paper [1] a random (acyclic) graph model is considered. The nodes are {1, …, n}; each new node k will have a directed edge to each of the earlier ones {1, …, k − 1} with a fixed probability p and will be accordingly put into a certain level. The parameter of interest is the number of levels, and in particular its average value. This model being too complicated, the authors introduce two simplified models, serving as “lower bound” and “upper bound”. We don’t want to describe them here but rather give some comments about how to analyze them.

In both instances the authors ask for explicit solutions of their recursions. We answer both questions in the affirmative. Also, we find surprising alternative representations of the appearing constants, due to theorems of Euler and Gauss, from the theory of partitions. Apart from the concrete results we feel that the presented analysis might be interesting in itself and useful for related questions.

For the necessary background we naturally refer to the paper [1] and only state the recursions that we are considering in the next two sections. We reverse the order and start we the easier “lower bound”.

To simplify the authors’ notation, we use q := 1 − p, where p is a probability, throughout this note. It is amazing that this “q”, denoting a probability and the formal variable “q”, used in so-called q–series [2] fit together so well!

Let us sketch the methods. The recursions will be solved by setting up ordinary generating functions. This gives immediately an expression for the generating function in the easy case, whereas in the difficult case the generating function must be extracted by iterations. In both instances we arrive at something like 1/(1 − z)^{2} multiplied by a function which is analytic in a larger area than |z| < 1. Thus the asymptotic behaviour of the coefficients of interest is given by n times a constant,

Typeset by AMS-TEX

This note was written while the author was visiting the Algo project of INRIA, Rocquencourt and encountered an especially warm hospitality there. Interesting and valuable discussions with Philippe Flajolet are gratefully acknowledged

which is just the value of the extra factor at z = 1. It is then possible to rewrite these constants as infinite products instead of infinite sums. The advantage of these representations is that their behaviour for q → 1 is quite easy to obtain, as opposed to the sum representations.

For all these mathematical methods we refer without further comments to the brilliant survey [4].

Finally we want to give a flavour of the quantitative results that are obtained in the next two sections. Typically, we might expect α · n levels for large n, where the constant α is depending of the probability p and of the model, α_{1} referring to the lower bound model and α_{2} referring to the upper bound model. For instance, in the symmetric case p = q = \frac{1}{2} we find α_{1} = 0.56546 … and α_{2} = 0.60914 ….

The behaviour of these constants for p → 0 (or q → 1) is of special interest, as it describes the behaviour of what is known as sparse graphs. It turns out that α_{1} ∼ \frac{p}{e−2}, whereas α_{2} ∼ \sqrt{\frac{2p}{π}}. More precise information is available, sharpening the results of [1]. So the two models show a different behaviour; one constant depending linearly, the other being like a square root of the (small) parameter p.

2. The “upper bound”

The recursion of the upper bound model is (equation (13) of [1])

P (n, 1) = ∑_{k=1}^{n−1} P (n − k, 1)q^{\binom{k}{2}}(1 − q^{k})  n ≥ 2; P (1, 1) = 1.  (1)

With these quantities one is interested in the “mean length”

\overline{L_{2}(n)} := ∑_{k=1}^{n} P (k, 1).  (2)

By additionally defining P (0, 1) = 0 we can extend the range of the summation in (1) from 0 to n.

Since the recursion has the flavour of a convolution, it is extremely natural to use generating functions: Set

f(z) := ∑_{n≥0} P (n, 1)z^{n},  (3)

then (1) translates into

f(z) − z = f(z) · ∑_{k≥0} q^{\binom{k}{2}}(1 − q^{k})z^{k}.  (4)

Set

ψ(z) := ∑_{k≥0} q^{\binom{k+1}{2}}z^{k},  (5)

then we find

∑_{k≥0} q^{\binom{k}{2}}(1 − q^{k})z^{k} = 1 − (1 − z)ψ(z)  (6)

and thus

f(z) = \frac{z}{(1 − z)ψ(z)}.  (7)

We find the sought quantity P (n, 1) as the coefficient of z^{n} in this (explicit!) function f(z), which we denote, as usual, by [z^{n}]f(z). Furthermore,

\overline{L_{2}(n)} = [z^{n}]\frac{1}{1 − z} · f(z) = [z^{n}]\frac{z}{(1 − z)^{2}} · \frac{1}{ψ(z)}.  (8)

Since ψ(z) is analytic at z = 1, we see from (8) by singularity analysis [3] that

\overline{L_{2}(n)} = \frac{n}{ψ(1)} + \frac{ψ′(1)}{ψ(1)} + exponentially small terms.  (9)

The quantity ψ(1) can be evaluated by a formula of Gauss [2, (2.2.13)]:

ψ(1) = ∑_{n≥0} q^{\binom{n+1}{2}} = ∏_{m≥1} \frac{1 − q^{2m}}{1 − q^{2m−1}} .  (10)

In [1] the behaviour of

\frac{α_{2}}{p} := \frac{1}{(1 − q)ψ(1)} = ∏_{m≥1} \frac{1 − q^{2m+1}}{1 − q^{2m}}  (11)

is considered for q → 1. With the product representation this is very simple. We substitute q = e^{−x}, take the logarithm and call the resulting function g(x):

g(x) = ∑_{m≥1} log (1 − e^{−(2m+1)x}) − ∑_{m≥1} log (1 − e^{−2mx}).  (12)

We compute its Mellin transform,

g^{∗}(s) = −Γ(s)ζ(s + 1)( − 1 + ζ(s)(1 − 2^{1−s})),  (13)

and find, by virtue of the inversion formula,

g(x) = \frac{1}{2πi} ∫_{2−i∞}^{2+i∞}g^{∗}(s)x^{−s}ds.  (14)

Now we shift the integral to the left and collect the residues of the integrand to get the desired asymptotic expansion of g(x) for x → 0. Then we can go back to exp(g(x)) and replace the variable x by − log q. All this can be done by MAPLE:

\frac{1}{(1 − q)ψ(1)} = \sqrt{\frac{2}{−π log q}} · (1 − \frac{3}{8} log q + \frac{11}{384} log^{2} q + O(log^{3} q))

= \sqrt{\frac{2}{π}} \frac{1}{\sqrt{1 − q}} (1 − \frac{1}{8}(1 − q) + \frac{19}{284}(1 − q)^{2} + O ((1 − q)^{3}))

(15)

This is of course a quantitative refinement of the statement that \frac{α_{2}}{1−q} goes to infinity.

Theorem U. [Upper bound] The mean length \overline{L_{2}(n)} is the coefficient of z^{n} in

\frac{z}{(1 − z)^{2}} · ( ∑_{k≥0} q^{\binom{k+1}{2}}z^{k})^{−1};

it is asymptotically equivalent to

\overline{L_{2}(n)} ∼ n · ∏_{m≥1} \frac{1 − q^{2m−1}}{1 − q^{2m}} .

The behaviour of the “inverse of the efficiency” for q → 1 is given by

∏_{m≥1} \frac{1 − q^{2m+1}}{1 − q^{2m}} ∼ \sqrt{\frac{2}{π}} \frac{1}{\sqrt{1 − q}} (1 − \frac{1}{8}(1 − q) + \frac{19}{284}(1 − q)^{2} + O ((1 − q)^{2})) .

3. The “lower bound”

This time the recursion for the lower bound model looks like

P (n, 1) = ∑_{k=1}^{n−1} P (n − 1, k) (1 − q^{k}) + q^{2}P (n − 1, 1)  for n ≥ 3,  (16)

P (n, j) = P (n − 1, j − 1)q^{j−1}p + P (n − 1, j)q^{j+1}  for 2 ≤ j ≤ n − 2, (17)

with P (n, n − 1) = q^{\binom{n−1}{2}}p^{n−1} and P (n, n) = q^{\binom{n}{2}} for n ≥ 1. Note that (16) can be replaced by the condition ∑_{j=1}^{n} P (n, j) = 1 for all n.

We introduce for each j a generating function h_{j}(z) by

h_{j}(z) := ∑_{n≥j} P (n, j)z^{n}.  (18)

By a routine computation (16) and (17) are translated into

h_{1}(z) = \frac{1}{1 − pz − q^{2}z} (z − q^{2}z^{2} + z ∑_{k≥2} h_{k}(z) (1 − q^{k}))  (19)

and

h_{j}(z) = pq^{j−1}zh_{j−1}(z) + zq^{j+1}h_{j}(z) + q^{1+\binom{j}{2}}z^{j} (1 − zq^{j})  for j ≥ 2. (20)

We are interested in the function h_{1}(z) since it “contains” the interesting coefficients. Let us recall that the desired “mean length”

\overline{L_{1}(n)} = q^{2} + ∑_{k=1}^{n} P (k, 1) − q^{2} ∑_{k=1}^{n−1} P (k, 1)  (21)

can be obtained as

\overline{L_{1}(n)} = q^{2} + [z^{n}]\frac{1}{1 − z} h_{1}(z) − q^{2}[z^{n−1}]\frac{1}{1 − z} h_{1}(z).  (22)

From (20) we see

h_{j}(z) = a_{j}h_{j−1}(z) + b_{j}, with a_{j} = \frac{pq^{j−1}}{1 − zq^{j+1}} and b_{j} = \frac{q^{1+\binom{j}{2}}z^{j} (1 − zq^{j})}{1 − zq^{j+1}}. (23)

We can iterate this and thus express each h_{j}(z) by h_{1}(z):

h_{j}(z) = A_{j} ∑_{k=2}^{j} \frac{b_{k}}{A_{k}} + A_{j}h_{1}(z), where A_{k} = a_{2}a_{3} … a_{k}.  (24)

We can now insert this into (19) and solve the linear equation for h_{1}(z). The obtained solution is admittedly not very nice, but it is explicit. Define d_{j} = A_{j} ∑_{k=2}^{j} b_{k}/A_{k}, then we find in this way

h_{1}(z) = \frac{z − q^{2}z^{2} + z ∑_{k≥2} (1 − q^{k}) d_{k}}{1 − pz − q^{2}z − z ∑_{k≥2} (1 − q^{k}) A_{k}} .  (25)

Let us now engage on asymptotics. In [1] it was implicitly proved that

h_{j}(z) ∼ \frac{π(j)}{1 − z}  as z → 1,  (26)

where

π(j) = \frac{p^{j−1}q^{\binom{j}{2}}}{(1 − q^{3}) … (1 − q^{j+1})} and \frac{1}{π(1)} = ∑_{j≥1} \frac{p^{j−1}q^{\binom{j}{2}}}{(1 − q^{3}) … (1 − q^{j+1})}. (27)

We could refine this by setting

h_{j}(z) ∼ \frac{π(j)}{1 − z} + σ(j),  (28)

insert it into (20), compare coefficients and thus express the numbers σ(j) by the π(j)’s. We omit this since the formulæ are not too nice.

But we can conclude, again by singularity analysis that

P (n, 1) = π(1) + exponentially small terms  (29)

and

\overline{L_{1}(n)} = n · (1 − q^{2}) π(1) + q^{2} + π(1) + (1 − q^{2}) σ(1) + exp. small terms. (30)

Let us now analyse the constant (1 − q^{2}) π(1) which is also called α_{1} in [1]. By some simple computations we find that

\frac{1}{α_{1}} = \frac{1}{p} ∑_{j≥0} \frac{p^{j}q^{\binom{j}{2}}}{(1 − q) … (1 − q^{j})} − 1 − \frac{2q}{p} .  (31)

This time we can use a formula of Euler [2, (2.2.26)]:

∑_{j≥0} \frac{p^{j}q^{\binom{j}{2}}}{(1 − q) … (1 − q^{j})} = ∏_{k≥0} (1 + pq^{k}) .  (32)

From this representation the behaviour of α_{1}/p (needed in [1]) for q → 1 is very easy to obtain. We consider its reciprocal, which is

∏_{k≥0} (1 + (1 − q)q^{k}) − 1 − q,  (33)

forget about the extra −1 − q, take the logarithm, expand it as a Taylor series, interchange the order of summation and expand. With the help of MAPLE we get

\frac{α_{1}}{p} = \frac{1}{e − 2} − \frac{\frac{e}{4} − 1}{(e − 2)^{2}} (q − 1) + O ((q − 1)^{2}) ,  (34)

but we could easily get as much terms as we please.

Theorem L. [Lower bound] The mean length \overline{L_{1}(n)} is given by

\overline{L_{1}(n)} = q^{2} + [z^{n}]\frac{1}{1 − z} h_{1}(z) − q^{2}[z^{n−1}]\frac{1}{1 − z} h_{1}(z),

where the function h_{1}(z) is given by

h_{1}(z) = \frac{z − q^{2}z^{2} + z ∑_{k≥2} (1 − q^{k}) d_{k}}{1 − pz − q^{2}z − z ∑_{k≥2} (1 − q^{k}) A_{k}} .

Here,

A_{k} = p^{k−1}q^{\binom{k}{2}}/ ∏_{j=3}^{k+1} (1 − zq^{j})

and

d_{k} = A_{k} ∑_{j=2}^{k} \frac{1}{A_{j}} \frac{q^{1+\binom{j}{2}}z^{j} (1 − zq^{j})}{1 − zq^{j+1}}.

It is asymptotically equivalent to

\overline{L_{1}(n)} ∼ n · (\frac{1}{p} ∏_{k≥0} (1 + pq^{k}) − 1 − \frac{2q}{p} )^{−1}.

The behaviour of the “inverse of the efficiency” for q → 1 is given by

\frac{1}{p}(\frac{1}{p} ∏_{k≥0} (1 + pq^{k}) − 1 − \frac{2q}{p} )^{−1} ∼ \frac{1}{e − 2} − \frac{\frac{e}{4} − 1}{(e − 2)^{2}} (q − 1) + O ((q − 1)^{2}) .

References

1. F.Afrati and A.Stafylopatis, Performance Considerations on a Random Graph Model for Parallel Processing, RAIRO Theoretical Informatics and Applications 27 (1993), 367–388.

2. G.E.Andrews, The Theory of Partitions, Addison–Wesley, Reading, MA, 1976.

3. P.Flajolet and A.Odlyzko, Singularity Analysis of Generating Functions, SIAM J.Discrete Mathematics 3 (1990), 216–240.

4. P.Flajolet and J.Vitter, Analysis of Algorithms and Data Structures, Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity. (J.van Leeuwen, ed.), 1990, pp. 431– 524.

Helmut Prodinger Technical University of Vienna Department of Algebra and Discrete Mathematics Wiedner Hauptstrasse 8–10 A-1040 Vienna Austria