\magnification=\magstep1
\input amstex
\documentstyle{amsppt}
\TagsOnRight
\NoRunningHeads
\topmatter
\title
comments on the analysis of parameters in a random graph model
\endtitle
\author
Helmut Prodinger
\endauthor
\affil
Technical University of Vienna\\
Department of Algebra and Discrete Mathematics
\endaffil
\address
\noindent \flushpar Helmut Prodinger\newline
Technical University of Vienna\newline
Department of Algebra and Discrete Mathematics\newline
Wiedner Hauptstrasse 8--10\newline
A-1040 Vienna \newline
Austria
\endaddress
\thanks
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
\endthanks
\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 {\bf 27}
(1993), 367--388 by Afrati and Stafylopatis.
\endabstract
\endtopmatter
\def\afrati{1}
\def\andrews{2}
\def\flaodl{3}
\def\flavit{4}
\def\({\left(}
\def\){\right)}
\document
\head 1. Introduction\endhead
In the paper \cite\afrati\ a random (acyclic)
graph model is considered.
The nodes are $\{1,\dots,n\}$; each new node $k$ will have a directed edge
to each of the earlier ones
$\{1,\dots,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
\cite\afrati\ 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 \cite
\andrews\ fit together so well!
Let us sketch the methods. The recursions will be solved by setting up
{\sl 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, 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\to1$ 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 \cite\flavit.
\medskip
Finally we want to give a flavour of the quantitative results that are
obtained in the next two sections. Typically, we might expect $\alpha \cdot n$
levels for large $n$, where the constant $\alpha$ is depending
of the probability
$p$ and of the model, $\alpha_1$ referring to the lower bound model and
$\alpha_2$ referring to the upper bound model. For instance, in the symmetric
case $p=q=\frac12$ we find $\alpha_1=0.56546\dots$ and
$\alpha_2=0.60914\dots$\, .
The behaviour of these constants for $p\to0$ (or $q\to1$) is of special
interest, as it describes the behaviour of what is known as {\sl sparse
graphs\/}. It turns out that $\alpha_1\sim\frac p{e-2}$, whereas
$\alpha_2\sim\sqrt{\frac{2p}{\pi}}$.
More precise information is available, sharpening the results of
\cite\afrati.
So the two models show a different
behaviour; one constant depending linearly, the other being like a square
root of the (small) parameter $p$.
\head 2. The ``upper bound''\endhead
The recursion of the upper bound model is (equation \thetag{13} of
\cite\afrati)
$$
P(n,1)=\sum_{k=1}^{n-1}
P(n-k,1)
q^{\binom k2}(1-q^k)\qquad n\ge2; \quad P(1,1)=1.\tag1
$$
With these quantities one is interested in the ``mean length''
$$
\overline{L_2(n)}:=\sum_{k=1}^nP(k,1).\tag2
$$
By additionally defining $P(0,1)=0$ we can extend the range of the
summation in \thetag1 from $0$ to $n$.
Since the recursion has the flavour of a {\sl convolution\/}, it
is extremely natural to use {\sl generating functions\/}: Set
$$
f(z):=\sum_{n\ge0}P(n,1)z^n,\tag3
$$
then \thetag1 translates into
$$
f(z)-z=f(z)\cdot \sum_{k\ge0}q^{\binom k2}(1-q^k)z^k. \tag4
$$
Set
$$
\psi(z):=\sum_{k\ge0}q^{\binom {k+1}2}z^k,\tag5
$$
then we find
$$
\sum_{k\ge0}q^{\binom k2}(1-q^k)z^k=1-(1-z)\psi(z)\tag6
$$
and thus
$$
f(z)=\frac{z}{(1-z)\psi(z)}.\tag7
$$
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]\frac1{1-z}\cdot f(z)=
[z^n]\frac z{(1-z)^2}\cdot \frac 1{\psi(z)}.\tag8
$$
Since $\psi(z)$ is analytic at $z=1$, we see from \thetag8 by {\sl singularity
analysis\/} \cite\flaodl\ that
$$
\overline{L_2(n)}=\frac n{\psi(1)}+\frac{\psi'(1)}{\psi(1)}
+\text{exponentially small terms}.\tag9
$$
The quantity $\psi(1)$ can be evaluated by a formula of Gauss \cite{\andrews,
(2.2.13)}:
$$
\psi(1)=\sum_{n\ge0}q^{\binom{n+1}2}=\prod_{m\ge1}\frac{1-q^{2m}}{1-q^{2m-1}}.
\tag{10}
$$
In \cite\afrati\ the behaviour of
$$
\frac{\alpha_2}{p}:=\frac1{(1-q)\psi(1)}=
\prod_{m\ge1}\frac{1-q^{2m+1}}{1-q^{2m}}\tag{11}
$$
is considered for $q\to1$. 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)=\sum_{m\ge1}\log\left(1-e^{-(2m+1)x}\right)-
\sum_{m\ge1}\log\Big(1-e^{-2mx}\Big).\tag{12}
$$
We compute its {\sl Mellin transform\/},
$$
g^\ast(s)=-\Gamma(s)\zeta(s+1)\Big(-1+\zeta(s)\big(1-2^{1-s}\big)\Big),
\tag{13}
$$
and find, by virtue of the {\sl inversion formula},
$$
g(x)=\frac1{2\pi i}\int\limits_{2-i\infty}^{2+i\infty}g^*(s)x^{-s}ds.\tag{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\to 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:
$$\aligned
\frac1{(1-q)\psi(1)}&=
\sqrt{\frac{2}{-\pi \log q}}\cdot\left(1-\frac38\log q+\frac{11}{384}\log^2q+
O(\log^3q)\right)
\\
&=\sqrt{\frac 2{\pi}}\frac1{\sqrt{1-q}}
\(1-\frac18(1-q)+\frac{19}{284}(1-q)^2+O\((1-q)^3\)\)
\endaligned
\tag{15}
$$
This is of course a quantitative refinement of the statement that
$\frac{\alpha_2}{1-q}$ goes to infinity.
\proclaim{Theorem U} {\rm [Upper bound]}
The mean length $\overline{L_2(n)}$ is
the coefficient of $z^n$ in
$$
\frac z{(1-z)^2}\cdot\bigg(
\sum_{k\ge0}q^{\binom {k+1}2}z^k\bigg)^{-1};
$$
it is asymptotically equivalent to
$$
\overline{L_2(n)}\sim
n\cdot \prod _{m\ge 1} \frac{1-q^{2m-1}}{1-q^{2m}}.
$$
The behaviour of the ``inverse of the efficiency'' for $q\to1$ is given by
$$
\prod _{m\ge 1} \frac{1-q^{2m+1}}{1-q^{2m}}
\sim
\sqrt{\frac 2\pi}\frac1{\sqrt{1-q}}\(1-\frac18(1-q)+\frac{19}{284}(1-q)^2+O\((1-q)^2\)\).
$$
\endproclaim
\head 3. The ``lower bound''\endhead
This time the recursion for the lower bound model looks like
$$
P(n,1)=\sum_{k=1}^{n-1}P(n-1,k)\left(1-q^k\right)+q^2P(n-1,1)
\qquad\text{for}\ n\ge3,\tag16
$$
$$
P(n,j)=P(n-1,j-1)q^{j-1}p+P(n-1,j)q^{j+1}
\qquad\text{for} \ 2\le j\le n-2 , \tag17
$$
with $P(n,n-1)=q^{\binom{n-1}2}p^{n-1}$ and $P(n,n)=q^{\binom n2}$
for $n\ge1$.
Note that \thetag{16} can be replaced by the condition
$\sum_{j=1}^nP(n,j)=1$ for all $n$.
We introduce for each $j$ a generating function $h_j(z)$ by
$$
h_j(z):=\sum_{n\ge j}P(n,j)z^n.
\tag18
$$
By a routine computation \thetag{16} and \thetag{17} are translated into
$$
h_1(z)=\frac1{1-pz-q^2z} \bigg(z-q^2z^2+z\sum_{k\ge2}h_k(z)\left(1-q^k\bigg)
\right)
\tag19
$$
and
$$
h_j(z)=pq^{j-1}zh_{j-1}(z)+zq^{j+1}h_j(z)+q^{1+\binom j2}z^j\(1-zq^j\)
\qquad\text{for} \ j \ge2.\tag20
$$
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+\sum_{k=1}^{n}P(k,1)-q^2\sum_{k=1}^{n-1}P(k,1)
\tag21
$$
can be obtained as
$$
\overline{L_1(n)}=q^2+[z^n]\frac1{1-z}h_1(z)-q^2[z^{n-1}]\frac1{1-z}h_1(z).
\tag22
$$
From \thetag{20} we see
$$
h_j(z)=a_jh_{j-1}(z)+b_j, \ \text{with}\ a_j=
\frac{pq^{j-1}}{1-zq^{j+1}} \ \text{and}\ b_j=
\frac{q^{1+\binom j2}z^j\(1-zq^j\)}{1-zq^{j+1}} .
\tag23
$$
We can iterate this and thus express each $h_j(z)$ by $h_1(z)$:
$$
h_j(z)=A_j\sum_{k=2}^j\frac{b_k}{A_k}+A_jh_1(z),\ \text{where}\
A_k=a_2a_3\dots a_k.
\tag24
$$
We can now insert this into \thetag{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\sum_{k=2}^jb_k/A_k$,
then we find in this
way
$$
h_1(z)=
\frac{z-q^2z^2+z\sum_{k\ge2}\(1-q^k\)d_k}{1-pz-q^2z-z\sum_{k\ge2}\(1-q^k\)A_k}.
\tag25
$$
Let us now engage on asymptotics. In \cite\afrati\ it was implicitly
proved that
$$
h_j(z)\sim \frac{\pi(j)}{1-z}\qquad\ \text{as}\ z\to1,\tag26
$$
where
$$
\pi(j)=\frac{p^{j-1}q^{\binom j2}}{(1-q^3)\dots (1-q^{j+1})}\quad \text{and}
\quad
\frac1{\pi(1)}=
\sum_{j\ge1}\frac{p^{j-1}q^{\binom j2}}{(1-q^3)\dots (1-q^{j+1})}.\tag27
$$
We could refine this by setting
$$
h_j(z)\sim \frac{\pi(j)}{1-z}+\sigma(j),\tag28
$$
insert it into \thetag{20}, compare coefficients and thus express the numbers
$\sigma(j)$ by the $\pi(j)$'s. We omit this since the formul\ae\ are not
too nice.
But we can conclude, again by {\sl singularity analysis\/} that
$$
P(n,1)=\pi(1)+\text{exponentially small terms}\tag29
$$
and
$$
\overline{L_1(n)}=n\cdot\(1-q^2\)\pi(1)+q^2+\pi(1)+
\(1-q^2\)\sigma(1)+\text{exp. small terms}.
\tag30
$$
Let us now analyse the constant $\(1-q^2\)\pi(1)$ which is also called
$\alpha_1$ in \cite\afrati. By some simple computations we find that
$$
\frac1{\alpha_1}=
\frac 1p
\sum_{j\ge0}\frac{p^jq^{\binom j2}}{(1-q)\dots (1-q^j)}
-1-\frac{2q}p.\tag31
$$
This time we can use a formula of Euler \cite{\andrews, (2.2.26)}:
$$
\sum_{j\ge0}\frac{p^jq^{\binom j2}}{(1-q)\dots (1-q^j)}
=\prod_{k\ge0}\(1+pq^k\).\tag32
$$
From this representation the behaviour of $\alpha_1/p$ (needed in
\cite\afrati) for $q\to1$ is very easy to obtain. We consider its
reciprocal, which is
$$
\prod_{k\ge0}\(1+(1-q)q^k\)-1-q,\tag33
$$
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{\alpha_1}p=\frac1{e-2}-\frac{\frac e4-1}{(e-2)^2}(q-1)+O\((q-1)^2\),
\tag34
$$
but we could easily get as much terms as we please.
\proclaim{Theorem L} {\rm [Lower bound]}
The mean length $\overline{L_1(n)}$ is
given by
$$
\overline{L_1(n)}=q^2+[z^n]\frac1{1-z}h_1(z)-q^2[z^{n-1}]\frac1{1-z}h_1(z),
$$
where the function $h_1(z)$ is given by
$$
h_1(z)=
\frac{z-q^2z^2+z\sum_{k\ge2}\(1-q^k\)d_k}{1-pz-q^2z-z\sum_{k\ge2}\(1-q^k\)A_k}.
$$
Here,
$$
A_k=p^{k-1}q^{\binom k2}\bigg/\prod_{j=3}^{k+1}\(1-zq^j\)
$$
and
$$
d_k=A_k\sum_{j=2}^k\frac1{A_j}\frac{q^{1+\binom j2}z^j\(1-zq^j\)}{1-zq^{j+1}}.
$$
It is asymptotically equivalent to
$$
\overline{L_1(n)}\sim
n\cdot
\bigg(\frac1p\prod_{k\ge0}\(1+pq^k\)-1-\frac{2q}p\bigg)^{-1}.
$$
The behaviour of the ``inverse of the efficiency'' for $q\to1$ is given by
$$
\frac1p
\bigg(\frac1p\prod_{k\ge0}\(1+pq^k\)-1-\frac{2q}p\bigg)^{-1}\sim
\frac1{e-2}-\frac{\frac e4-1}{(e-2)^2}(q-1)+O\((q-1)^2\).
$$
\endproclaim
\Refs
\ref \no \afrati\paper Performance Considerations on a Random Graph Model for
Parallel Processing \by F.Afrati and A.Stafylopatis \jour RAIRO
Theoretical Informatics and Applications \vol 27\pages 367--388\yr 1993
\endref
\ref \no\andrews\book The Theory of Partitions \publ Addison--Wesley
\publaddr Reading, MA \yr 1976\by G.E.Andrews
\endref
\ref \no \flaodl\paper Singularity
Analysis of Generating Functions
\by P.Flajolet and A.Odlyzko \jour SIAM J.Discrete
Mathematics\vol3\yr1990\pages216--240
\endref
\ref \no \flavit
\by P.Flajolet and J.Vitter\paper Analysis of Algorithms and Data Structures
\inbook Handbook of Theoretical Computer Science, Vol. A: Algorithms and
Complexity. \ed J.van Leeuwen \yr1990\pages 431--524
\endref
\endRefs
\enddocument