%In Computing
%Figures of random walks are missing. Too bad!







\input amstex
\documentstyle{amsppt}



\NoBlackBoxes
\topmatter
\title
EINIGE KOMMENTARE \\ ZU EINER BIN--PACKING AUFGABE \\
VON W. KN\"ODEL
\endtitle
\author
Helmut Prodinger
\endauthor
\affil
Institut f\"ur Algebra und Diskrete Mathematik\\
Technische Universit\"at Wien, A-1040 Wien, Austria
\endaffil
\address{Technische Universit\"at Wien\newline 
Wiedner Hauptstra{\ss}e 8-10\newline
A-1040 Wien\newline  AUSTRIA}
\endaddress
\abstract{ 
W. Kn\"odel has considered a bin--packing problem which can
be seen within the context of random walks. The height of a random
walk is a well studied parameter which can also be defined  in 
Kn\"odels model. Its average is computed and shown to be of order
$\sqrt n$. The methods include singularity analysis of generating
functions as well as
Mellin transforms.
}
\endabstract
\endtopmatter


\document

\centerline{{\it Herrn Professor W. Kn\"odel}}
\centerline{{\it zum 65. Geburtstag (20.5.1991)
gewidmet}}

\heading
1. Einleitung
\endheading

W. Kn\"odel \cite5, \cite7, vgl. auch \cite8 betrachtete ein
{\it bin--packing} Problem, welches zu einem Irrfahrten--Problem
("random walk") \"aquivalent ist:

\vskip 4 cm

\centerline{Fig. 1}
\bigskip

Unter der Annahme, da\ss\  alle $3^n$ Wege der L\"ange $n$, die vom
Zu\-stand 0 ausgehen, gleich wahrscheinlich sind, ist die mittlere 
Nummer des erreichten Zustands zu bestimmen, wobei dem Spezialzustand
$\beta$ die Nummer 2 zuzuordnen ist. (In Kn\"odels Formulierung die "Nummer"
$\frac 12$, aber das ist v\"ollig analog zu behandeln, und die asymptotischen
Ergebnisse stimmen im Hauptterm \"uberein.)

In dieser Arbeit k\"onnen alle lokalen und asymptotischen Entwicklungen
im Prinzip hergeschrieben werden; aus Gr\"unden der K\"urze begn\"ugen wir uns 
jedoch stets mit dem Hauptterm und deuten weitere Terme durch
"$+\dots$" an.

\proclaim{Satz 1} {\rm [Kn\"odel]}
Die mittlere "Nummer" $E_n$ des erreichten Zustands nach $n$
Schritten ist asymptotisch
$$
2\sqrt{\frac{n}{3\pi}}+\dots \ . \qed
$$
\endproclaim

Im Kapitel 2 wird eine Herleitung dieses Ergebnisses skizziert.

Hier sind wir, motiviert von der Interpretation der Irrfahrten, am
Parameter $H_n$ interessiert, n\"amlich der {\it maximalen} erreichten
Nummer w\"ahrend eines Weges der L\"ange $n$, vgl. z.B. \cite 2 und 
\cite 6 ("H\"ohe").

\proclaim{Satz 2}
Die mittlere H\"ohe $H_n$, die nach  $n$
zuf\"alligen Schritten erreicht wurde, ist asymptotisch
$$
\sqrt{\frac{\pi n}{3}}+\dots \ . \qed
$$
\endproclaim

Das Kapitel 2 ist der Herleitung dieses (schwierigeren) Problems ge\-widmet.

Als Vergleich wollen wir noch die entsprechenden Resultate angeben f\"ur den 
Fall, der im Studium der Irrfahrten eher \"ublich ist, n\"amlich dem in
Figur 2 dargestellten.

\vskip 2.5 cm

\centerline{Fig. 2}
\bigskip

Dieser Fall ensteht durch Fortlassung des Zustands $\beta$. Nat\"urlich ist
die Gesamtanzahl der Wege der L\"ange $n$, durch die man dividieren mu\ss, 
nicht mehr $3^n$. Bezeichnen wir die entsprechenden Parameter mit
$\widetilde{E_n}$ und $\widetilde{H_n}$, dann gilt

\proclaim{Satz 3} $$\widetilde{E_n}\sim \sqrt{\frac{\pi n}{3}}+\dots\ .
  \qed
$$
\endproclaim

\proclaim{Satz 4} $$\widetilde{H_n}\sim 2(\log 2)\sqrt{\pi n}+\dots\ .
 \qed
$$
\endproclaim

Die numerischen Konstanten, die jeweils als Faktor von $\sqrt n$ 
auftreten, sind
$$
\alignat 2
\frac{2}{\sqrt{3\pi}}&=0,6514\dots &
\sqrt{\frac{\pi}{3}}&=1,0233\dots\\
\sqrt{\frac{\pi}{3}}&=1,0233\dots &\qquad
2(\log 2)\sqrt\pi&=2,4571\dots
\endalignat
$$

Diese Einleitung mag mit einem Hinweis auf die asymptotische Technik
abgeschlossen werden. Das asymptotische Verhalten wird stets
aus dem lokalen Verhalten der entsprechenden erzeugenden Funktionen
in der N\"ahe ihrer dominanten Singularit\"aten gewonnen. Um dieses
Verhalten zu ermitteln, bedient man sich der Mellin--Transformation;
deren Umkehrtransformation ist n\"amlich ein komplexes Kurvenintegral,
das asymptotisch durch die Residuen angegeben werden kann. Diese
Vorgangsweise ist etwa in \cite 3 und \cite 4 beschrieben.

\heading
2. Analysis
\endheading
 
Sei f\"ur $i=0,1,\dots$ oder $i=\beta$
$$
\varphi_i(x)=\sum_{n\ge 0}\ \ \left[\aligned 
&\text{Anzahl der Pfade der L\"ange $n$},\\
&\text{die von 0 nach $i$  f\"uhren}
\endaligned
\right]
\,x^n,
$$
und
$$
\varphi_{i,h}(x)=\sum_{n\ge 0}\ \ 
\left[
\aligned
&\text{Anzahl der Pfade der L\"ange $n$},\\
&\text{die von 0 nach $i$  f\"uhren}\\
&\text{und H\"ohe $\le h$ haben}
\endaligned
\right]
\,x^n.
$$

Das System der $\varphi_i$'s wird durch folgende Matrix--Gleichung
beschrie\-ben.
$$
\pmatrix 1-x&-x&-x&\\
-x&1-x\\
-x&-x&1-x&-x\\
&&-x&1-x&-x\\
&&\ddots&-x&1-x&-x\\
&&&\ddots&\ddots&\ddots
\endpmatrix
\pmatrix \varphi_0\\ \varphi_\beta\\ \varphi_1\\ 
\varphi_2\\  \varphi_3\\ \vdots 
\endpmatrix
=
\pmatrix 1\\0\\0\\ 0\\0\\\vdots \endpmatrix
$$
Die $\varphi_{i,h}$'s erf\"ullen ein "abgeschnittenes" System mit
$h+2$ Zeilen; dies gilt nur f\"ur $h\ge 2$, die Werte $h=0$ und
$h=1$ m\"ussen extra behandelt werden.

Au\ss erdem sei

$$
\Phi_h(x)=\sum_{i}\varphi_{i,h}(x)
$$
die erzeugende Funktion, wo das Ende nicht festgelegt ist. $i$ durchl\"auft
im Normalfall die Werte $0,1,\dots$ und $\beta$.

Die Berechnung der $\varphi_{i,h}$'s erfolgt mit der Cramerschen
Regel. Dazu sei zun\"achst 
$a_h(x)$ die folgende Determinante ($h$ die Anzahl der Zeilen):
$$
a_h(x)=\left|
\matrix 1-x&-x\\-x&1-x&-x\\&-x&1-x&-x\\&\ddots&\ddots&\ddots 
\endmatrix\right|,
$$
Durch Entwicklung etwa nach der
ersten Zeile 
erh\"alt man
$$
a_h=(1-x)a_{h-1}-x^2a_{h-2}, \quad a_0=1, \ a_1=1-x,
$$
und daher
$$
\aligned
a_h(x)=\frac{1}{\sqrt{1-2x-3x^2}}
&\Bigg[\left(\frac{1-x+\sqrt{1-2x-3x^2}}{2}\right)^{h+1}\\&-
\left(\frac{1-x-\sqrt{1-2x-3x^2}}{2}\right)^{h+1}
\Bigg]
\endaligned
$$
Dieser Ausdruck erinnert an {\it Motzkin--B\"aume}, und die Substitution
$x=v/(1+v+v^2)$ ist in diesem Kontext hilfreich. Man beachte, da\ss\  die 
Singularit\"at, die in der Einleitung erw\"ahnt wurde, $x=\frac 13$ ist; in der
$v$--Sprechweise ist sie $v=1$. Man erh\"alt
$$
a_h(x)=\frac{1}{1-v^2}\frac{1-v^{2h+2}}{(1+v+v^2)^h}.
$$
Nun sei $b_h(x)$ die Determinante des eigentlichen Systems
mit $h+2$ Zeilen; durch Entwicklung  nach der ersten Zeile ergibt sich
$$
b_h=(1-2x)a_h-x^2a_{h-1}
=\frac{1}{1+v}\frac{1+v^{2h+3}}{(1+v+v^2)^{h-1}}.
$$
Durch Cramers Regel zur Auf\/l\"osung des linearen Gleichungssystems
folgt nun f\"ur
$h\ge 2$
$$
\aligned
\varphi_{0,h}&=\frac{(1-x)a_h}{b_h}
=\frac{1+v^2}{1-v}\frac{1-v^{2h+2}}{1+v^{2h+3}},\\
\varphi_{\beta,h}&=\frac{xa_h}{b_h}=
\frac{v}{1-v}\frac{1-v^{2h+2}}{1+v^{2h+3}},\\
\varphi_{i,h}&=\frac{x^ia_{h-i}}{b_h}
=\frac{1+v+v^2}{1-v}\, v^i\, \frac{1-v^{2h-2i+2}}{1+v^{2h+3}}, \quad i\ge 1.
\endaligned
$$
Die Sonderf\"alle sind
$$
\varphi_{0,1}=\frac{1+v^2}{1-v+v^2},\quad
\varphi_{1,1}=\frac{v}{1-v+v^2},\quad 
\varphi_{0,0}=\frac{1+v+v^2}{1+v^2}.
$$
Die erzeugenden Funktionen ohne H\"oheneinschr\"ankung ergeben sich
\linebreak
auch analytisch f\"ur $h \to\infty$:
$$
\varphi_{0}=\frac{1+v^2}{1-v},\quad
\varphi_{\beta}=\frac{v}{1-v},\quad
\varphi_{i}=\frac{v^i(1+v+v^2)}{1-v}, \quad i\ge 1. 
$$
Man errechnet durch Summation
$$
\Phi_h(x)=\frac{1+v+v^2}{(1-v)^2}\frac{(1-v^{h+1})(1-v^{h+2})}{1+v^{2h+3}}
\quad h\ge 2,
$$
sowie
$$
\Phi_1(x)=\frac{1+v+v^2}{1-v+v^2},\quad
\Phi_0(x)=\frac{1+v+v^2}{1+v^2}.
$$
$h\to \infty$ ergibt die erzeugende Funktion {\it aller} Wege:
$$
\frac{1+v+v^2}{(1-v)^2}=\frac{1}{1-3x}.
$$
Sei nun
$$
F(x)=\sum_{h\ge 0}\left[\frac{1}{1-3x}-\Phi_h(x)\right],
$$
dann ist die gesuchte mittlere H\"ohe $E_n$
$$
3^{-n}[x^n]F(x),
$$
wo $[x^n]F(x)$ den Koeffizienten von $x^n$ in $F(x)$
bezeichnet.
Man errechnet nun
$$
\aligned
F(x)&=\sum_{h\ge 2}\frac{(1+v+v^2)(1+v)v^{h+1}}{(1-v)^2(1+v^{2h+3})}+\dots\\
&=\frac{(1+v+v^2)(1+v)}{(1-v)^2}v^{-1/2}\sum_{h\ge 3}
\frac{v^{h+\frac 12}}{1+v^{2h+1}}+\dots\\
&=\frac{(1+v+v^2)(1+v)}{(1-v)^2}v^{-1/2}\sum_{h\ge 0}
\frac{v^{h+\frac 12}}{1+v^{2h+1}}+\dots\ .  
\endaligned
$$
Nun sei (mit $v=e^{-t}$)
$$
\aligned
G(v)&=\sum_{h\ge 0}
\frac{v^{h+\frac 12}}{1+v^{2h+1}}
=\sum_{h\ge 0}e^{-t(h+\frac 12)}
\sum_{j\ge 0}
(-1)^je^{-j(2h+1)t}\\
&=\sum_{h,j\ge 0}(-1)^je^{-\frac t2 (2h+1)(2j+1)}.
\endaligned
$$
Wir berechnen die Mellin--Transformierte dieses Ausdrucks
(vgl. \cite 3, \cite 4 f\"ur eine Darstellung).
$$
\aligned
G^*(s)&=2^s\Gamma(s)\sum_{h,j\ge 0}(-1)^j
(2h+1)^{-s}(2j+1)^{-s}\\
&=2^s\Gamma(s)\zeta(s)(1-2^{-s})\beta(s).
\endaligned
$$
Dabei ist (Notation von \cite 1)
$$
\beta(s)=1-\frac{1}{3^s}
+\frac{1}{5^s}-\frac{1}{7^s}+-\ \dots\ ;
$$
man kann
$\beta(s)$
auch mit der Hurwitzschen $\zeta$--Funktion ausdr\"ucken,
$$
\beta(s)=
4^{-s}\left(\zeta(s,\frac 14)-\zeta(s,\frac 34)\right).
$$
Die Mellinsche Umkehrformel sagt
$$
G(v)=\frac{1}{2\pi i}\int\limits_{\frac 32-i\infty}^{\frac 32+i\infty}
\Gamma(s)\zeta(s)(2^s-1)\beta(s)t^{-s}ds.
$$
Um die angek\"undigte lokale Entwicklung zu erhalten, verschiebt man die
Integrationsgerade nach links und sammelt die Residuen. Der erste Pol
ist bei $s=1$ (von der $\zeta$--Funktion); er ist einfach, und das
Residuum ist
$$
\beta(1)\frac 1t=\frac{\pi}{4t}.
$$
Also
$$
G(v)\sim\frac{\pi}{4t},
$$
und daher ($1-v\sim t$)
$$
F(x)\sim \frac{3\cdot 2}{t^2}\cdot 1\cdot\frac{\pi}{4t}+\dots
=\frac{3\pi}{2}
\frac{1}{t^3}+\dots\ .
$$
Da $t\sim \sqrt3\sqrt{1-3x}$, hei\ss t das
$$
F(x)\sim \frac{\pi}{2\sqrt3}\frac{1}{(1-3x)^{3/2}},
$$
und weiter
$$
[x^n]F(x)\sim 3^n  \frac{\pi}{2\sqrt3}
\frac{n^{1/2}}{\Gamma(\frac 32)}
=3^n\frac{\sqrt{\pi n}}{\sqrt3}\, ,
$$
was nach Division durch $3^n$ den Satz 2 ergibt.

Kn\"odels Resultat folgt sofort: Da
$$
\varphi_i=\frac{v^i(1+v+v^2)}{1-v},
$$
folgt
$$
\aligned
\sum_{i\ge 0}i\varphi_i +2\varphi_\beta&=
\frac{1+v+v^2}{1-v}\frac{v}{(1-v)^2}+\dots\\
&=\frac{3}{t^3}+\dots\ \sim\frac{1}{\sqrt3}(1-3x)^{-3/2}+\dots\ ;
\endaligned
$$
der Koeffizient von $[x^n]$ darin ist asymptotisch
$$
3^n\frac{1}{\sqrt3}\frac{1}{\Gamma(\frac 32)}n^{1/2}
=3^n\, 2\, \sqrt{\frac{n}{3\pi}}\, ;
$$
das ist Satz 1.

Nun wollen wir noch kurz das Modell entsprechend Figur 2 skizzieren: Es ist
$$
\varphi_{i,h}=\frac{x^ia_{h-i}}{a_{h+1}}
=v^i(1+v+v^2)\frac{1-v^{2h-2i+2}}{1-v^{2h+4}},
$$
und
$$
\Phi_h=\sum_{i=0}^h\varphi_{i,h}=
\frac{1+v+v^2}{1-v}\frac{(1-v^{h+1})(1-v^{h+2})}{1-v^{2h+4}}.
$$
Die erzeugende Funktion {\it aller} Wege ist der Grenzwert f\"ur
$h\to\infty$:
$$
\frac{1+v+v^2}{1-v}.
$$
Man mu\ss\ wie vorher
$$
\aligned
F(x)&=\sum_{h\ge 0}\left[
\frac{1+v+v^2}{1-v}-
\frac{1+v+v^2}{1-v}\frac{(1-v^{h+1})(1-v^{h+2})}{1-v^{2h+4}}\right]\\
&=\frac{(1+v+v^2)(1+v)}{1-v}\sum_{h\ge 1}\frac{v^h}{1+v^h}+\dots 
\endaligned
$$
betrachten. Sei wieder
$$
G(v)=\sum_{h\ge 1}\frac{v^h}{1+v^h};
$$
die Transformierte ist ($v=e^{-t}$)
$$
G^*(s)=\Gamma(s)\zeta^2(s)(1-2^{1-s}).
$$
Also
$$
G(v)=\frac{1}{2\pi i}\int\limits_{\frac 32-i\infty}^{\frac 32+i\infty}
\Gamma(s)\zeta^2(s)(1-2^{1-s})t^{-s}ds.
$$
Bei $s=1$ gibt es einen einfachen Pol mit Residuum
$\dfrac{\log 2}{t}$.
Daher
$$
F(x)\sim \frac 6t \cdot \frac{\log 2}{t}+\dots\ 
=\frac{6\log 2}{t^2}+\dots\ =\frac{2\log 2}{1-3x}+\dots\ .
$$
Der Koeffizient von $x^n$ darin ist asymptotisch
$3^n2\log 2$. Diese Gr\"o\ss e mu\ss\ dividiert werden durch
$$
\aligned
&[x^n]\frac{1+v+v^2}{1-v}\sim[x^n]\frac 3t\\
&\sim [x^n]\sqrt3 (1-3x)^{-1/2}\sim \sqrt3\,  3^n
\frac{n^{-1/2}}{\Gamma(\frac 12)}\\
&=3^n\sqrt{\frac{3}{\pi n}}\, .
\endaligned
$$
Das ergibt Satz 4. F\"ur Satz 3 beobachtet man
$$
\varphi_i=v^i(1+v+v^2)
$$
und
$$
\sum_{i\ge 0}i\varphi_i=(1+v+v^2)\frac{v}{(1-v)^2}
\sim\frac{3}{t^2}
=\frac{1}{1-3x};
$$
der Koeffizient von $x^n$ darin ist asymptotisch $3^n$. Wieder mu\ss\
dieser Ausdruck durch $3^n\sqrt{\frac{3}{\pi n}}$ dividiert werden.














\heading
Literatur
\endheading
\bigskip

\ref \no 1 \by M.Abramowitz, I.A.Stegun \book Handbook of Mathematical
Func\-tions \publ Dover \publaddr  New York \yr 1970 \endref

\ref \no 2 \by N.G.De Bruijn, D.E.Knuth, and S.O.Rice \paper The average
height of planted plane trees \inbook Graph Theory and Computing, 
R.C.Read, Ed. \pages 15--22 \publ Academic Press \publaddr New York -- London
\yr 1972
\endref

\ref \no 3 \by P.Flajolet and A.M.Odlyzko \paper Singularity Analysis
of Generating Functions \jour SIAM J. Disc. Math. \yr 1990 \vol 3
\pages 216--240
\endref

\ref \no 4\by P.Flajolet and J.S.Vitter \paper Average--Case Analysis
of Algorithms and Data Structures  \inbook  Handbook of 
Theoretical Computer Science, J. van Leeuwen, Ed. \publ North-Holland \yr 1990
\endref

\ref \no 5 \by W.Kn\"odel \paper \"Uber das mittlere Verhalten von on-line
Packungsalgorithmen
\jour EIK \yr 1983 \pages 427--433 \vol 19
\endref

\ref \no 6 \by W.Panny and H.Prodinger \paper The expected height 
of paths for several notions of height \jour Stud. Sci. Math. Hung.
\vol 20 \yr 1985 \pages 119--132
\endref
  
\ref \no 7 \by H.Prodinger \paper Einige Bemerkungen zu einer Arbeit
von W.Kn\"odel \"uber das mitt\-lere Verhalten von on-line-Packungsalgorithmen
 \jour EIK \yr 1985 \pages 3--7 \vol 21
\endref

\ref \no 8 \by H.Prodinger 
\paper Further Results on a Problem of Kn\"odel concerning  the 
Analysis of Bin-Packing 
\jour Number--Theoretic Analysis, E.Hlawka, R. F. Tichy (Eds.)
Lecture Notes in Mathematics \vol 1452
 \pages 193--198
 \yr 1990 
\endref



\enddocument




