EINIGE KOMMENTARE

ZU EINER BIN–PACKING AUFGABE

VON W. KNÖDEL

Helmut Prodinger

Institut für Algebra und Diskrete Mathematik Technische Universität Wien, A-1040 Wien, Austria

Abstract. W. Knödel 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ödels 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.

Herrn Professor W. Knödel zum 65. Geburtstag (20.5.1991) gewidmet

1. Einleitung

W. Knödel [5], [7], vgl. auch [8] betrachtete ein bin–packing Problem, welches zu einem Irrfahrten–Problem (”random walk”) äquivalent ist:

Fig. 1

Unter der Annahme, daß alle 3^{n} Wege der Länge n, die vom Zustand 0 ausgehen, gleich wahrscheinlich sind, ist die mittlere Nummer des erreichten Zustands zu bestimmen, wobei dem Spezialzustand β die Nummer 2 zuzuordnen ist. (In Knödels Formulierung die ”Nummer” \frac{1}{2}, aber das ist völlig analog zu behandeln, und die asymptotischen Ergebnisse stimmen im Hauptterm überein.)

In dieser Arbeit können alle lokalen und asymptotischen Entwicklungen im Prinzip hergeschrieben werden; aus Gründen der Kürze begnügen wir uns jedoch stets mit dem Hauptterm und deuten weitere Terme durch ”+ … ” an.

Typeset by AMS-TEX

Satz 1. [Knödel] Die mittlere ”Nummer” E_{n} des erreichten Zustands nach n Schritten ist asymptotisch

2\sqrt{\frac{n}{3π}} + …. □

Im Kapitel 2 wird eine Herleitung dieses Ergebnisses skizziert.

Hier sind wir, motiviert von der Interpretation der Irrfahrten, am Parameter H_{n} interessiert, nämlich der maximalen erreichten Nummer während eines Weges der Länge n, vgl. z.B. [2] und [6] (”Höhe”).

Satz 2. Die mittlere Höhe H_{n}, die nach n zufälligen Schritten erreicht wurde, ist asymptotisch

\sqrt{\frac{πn}{3}} + …. □

Das Kapitel 2 ist der Herleitung dieses (schwierigeren) Problems gewidmet.

Als Vergleich wollen wir noch die entsprechenden Resultate angeben für den Fall, der im Studium der Irrfahrten eher üblich ist, nämlich dem in Figur 2 dargestellten.

Fig. 2

Dieser Fall ensteht durch Fortlassung des Zustands β. Natürlich ist die Gesamtanzahl der Wege der Länge n, durch die man dividieren muß, nicht mehr 3^{n}. Bezeichnen wir die entsprechenden Parameter mit Ẽ_{n} und H̃_{n}, dann gilt

Satz 3.

Ẽ_{n} ∼ \sqrt{\frac{πn}{3}} + …. □

Satz 4.

H̃_{n} ∼ 2(log 2)\sqrt{πn} + …. □

Die numerischen Konstanten, die jeweils als Faktor von \sqrt{n} auftreten, sind

\frac{2}{\sqrt{3π}} = 0, 6514 …  \sqrt{\frac{π}{3}} = 1, 0233 …
\sqrt{\frac{π}{3}} = 1, 0233 …  2(log 2)\sqrt{π} = 2, 4571 …

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ähe ihrer dominanten Singularitäten gewonnen. Um dieses Verhalten zu ermitteln, bedient man sich der Mellin–Transformation; deren Umkehrtransformation ist nämlich ein komplexes Kurvenintegral, das asymptotisch durch die Residuen angegeben werden kann. Diese Vorgangsweise ist etwa in [3] und [4] beschrieben.

2. Analysis

Sei für i = 0, 1, … oder i = β

φ_{i}(x) = ∑_{n≥0} [ \begin{matrix}Anzahl der Pfade der Länge n, \\ die von 0 nach i führen \end{matrix}] x^{n},

und

φ_{i,h}(x) = ∑_{n≥0} [ \begin{matrix}Anzahl der Pfade der Länge n, \\ die von 0 nach i führen \\ und Höhe ≤ h haben \end{matrix}] x^{n}.

Das System der φ_{i}’s wird durch folgende Matrix–Gleichung beschrieben.

( \begin{matrix}1 − x & −x & −x \\ −x & 1 − x \\ −x & −x & 1 − x & −x \\ & & −x & 1 − x & −x \\ & & ... & −x & 1 − x & −x \\ & & & ... & ... & ... \end{matrix} ) ( φ_{0} ; φ_{β} ; φ_{1} ; φ_{2} ; φ_{3} ; ⋮ ) = ( 1 0 0 0 0 ⋮ )

Die φ_{i,h}’s erfüllen ein ”abgeschnittenes” System mit h + 2 Zeilen; dies gilt nur für h ≥ 2, die Werte h = 0 und h = 1 müssen extra behandelt werden.

Außerdem sei

Φ_{h}(x) = ∑_{i} φ_{i,h}(x)

die erzeugende Funktion, wo das Ende nicht festgelegt ist. i durchläuft im Normalfall die Werte 0, 1, … und β.

Die Berechnung der φ_{i,h}’s erfolgt mit der Cramerschen Regel. Dazu sei zunächst a_{h}(x) die folgende Determinante (h die Anzahl der Zeilen):

a_{h}(x) = | \begin{matrix}1 − x & −x \\ −x & 1 − x & −x \\ & −x & 1 − x & −x \\ & ... & ... & ... \end{matrix} | ,

Durch Entwicklung etwa nach der ersten Zeile erhält man

a_{h} = (1 − x)a_{h−1} − x^{2}a_{h−2}, a_{0} = 1, a_{1} = 1 − x,

und daher

\begin{aligned}a_{h}(x) = \frac{1}{\sqrt{1 − 2x − 3x^{2}}} & [ (\frac{1 − x + \sqrt{1 − 2x − 3x^{2}}}{2} )^{h+1} \\ & − (\frac{1 − x − \sqrt{1 − 2x − 3x^{2}}}{2} )^{h+1} ] \end{aligned}

Dieser Ausdruck erinnert an Motzkin–Bäume, und die Substitution x = v/(1 + v + v^{2}) ist in diesem Kontext hilfreich. Man beachte, daß die Singularität, die in der Einleitung erwähnt wurde, x = \frac{1}{3} ist; in der v–Sprechweise ist sie v = 1. Man erhält

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^{2}a_{h−1} = \frac{1}{1 + v} \frac{1 + v^{2h+3}}{(1 + v + v^{2})^{h−1}} .

Durch Cramers Regel zur Auflösung des linearen Gleichungssystems folgt nun für h ≥ 2

\begin{aligned}φ_{0,h} & = \frac{(1 − x)a_{h}}{b_{h}} = \frac{1 + v^{2}}{1 − v} \frac{1 − v^{2h+2}}{1 + v^{2h+3}} , \\ φ_{β,h} & = \frac{xa_{h}}{b_{h}} = \frac{v}{1 − v} \frac{1 − v^{2h+2}}{1 + v^{2h+3}} , \\ φ_{i,h} & = \frac{x^{i}a_{h−i}}{b_{h}} = \frac{1 + v + v^{2}}{1 − v} v^{i} \frac{1 − v^{2h−2i+2}}{1 + v^{2h+3}} , i ≥ 1. \end{aligned}

Die Sonderfälle sind

φ_{0,1} = \frac{1 + v^{2}}{1 − v + v^{2}} , φ_{1,1} = \frac{v}{1 − v + v^{2}} , φ_{0,0} = \frac{1 + v + v^{2}}{1 + v^{2}} .

Die erzeugenden Funktionen ohne Höheneinschränkung ergeben sich auch analytisch für h → ∞:

φ_{0} = \frac{1 + v^{2}}{1 − v} , φ_{β} = \frac{v}{1 − v} , φ_{i} = \frac{v^{i}(1 + v + v^{2})}{1 − v}, i ≥ 1.

Man errechnet durch Summation

Φ_{h}(x) = \frac{1 + v + v^{2}}{(1 − v)^{2}} \frac{(1 − v^{h+1})(1 − v^{h+2})}{1 + v^{2h+3}} h ≥ 2,

sowie

Φ_{1}(x) = \frac{1 + v + v^{2}}{1 − v + v^{2}} , Φ_{0}(x) = \frac{1 + v + v^{2}}{1 + v^{2}} .

h → ∞ ergibt die erzeugende Funktion aller Wege:

\frac{1 + v + v^{2}}{(1 − v)^{2}} = \frac{1}{1 − 3x}.

Sei nun

F (x) = ∑_{h≥0} [\frac{1}{1 − 3x} − Φ_{h}(x)] ,

EINIGE KOMMENTARE ZU EINER BIN–PACKING AUFGABE VON W. KNÖDEL 5

dann ist die gesuchte mittlere Höhe 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

F (x) = ∑_{h≥2} \frac{(1 + v + v^{2})(1 + v)v^{h+1}}{(1 − v)^{2}(1 + v^{2h+3})} + …

= \frac{(1 + v + v^{2})(1 + v)}{(1 − v)^{2}}v^{−1/2} ∑_{h≥3} \frac{v^{h+ \frac{1}{2}}}{1 + v^{2h+1}} + …

= \frac{(1 + v + v^{2})(1 + v)}{(1 − v)^{2}}v^{−1/2} ∑_{h≥0} \frac{v^{h+ \frac{1}{2}}}{1 + v^{2h+1}} + ….

Nun sei (mit v = e^{−t})

\begin{aligned}G(v) & = ∑_{h≥0} \frac{v^{h+ \frac{1}{2}}}{1 + v^{2h+1}} = ∑_{h≥0} e^{−t(h+ \frac{1}{2} )} ∑_{j≥0}(−1)^{j}e^{−j(2h+1)t} \\ & = ∑_{h,j≥0}(−1)^{j}e^{− \frac{t}{2} (2h+1)(2j+1)}. \end{aligned}

Wir berechnen die Mellin–Transformierte dieses Ausdrucks (vgl. [3], [4] für eine Darstellung).

\begin{aligned}G^{∗}(s) & = 2^{s}Γ(s) ∑_{h,j≥0}(−1)^{j}(2h + 1)^{−s}(2j + 1)^{−s} \\ & = 2^{s}Γ(s)ζ(s)(1 − 2^{−s})β(s). \end{aligned}

Dabei ist (Notation von [1])

β(s) = 1 − \frac{1}{3^{s}} + \frac{1}{5^{s}} − \frac{1}{7^{s}} + − …;

man kann β(s) auch mit der Hurwitzschen ζ–Funktion ausdrücken,

β(s) = 4^{−s} (ζ(s, \frac{1}{4}) − ζ(s, \frac{3}{4})) .

Die Mellinsche Umkehrformel sagt

G(v) = \frac{1}{2πi} ∫_{\frac{3}{2} −i∞}^{\frac{3}{2} +i∞}Γ(s)ζ(s)(2^{s} − 1)β(s)t^{−s}ds.

Um die angekündigte lokale Entwicklung zu erhalten, verschiebt man die Integrationsgerade nach links und sammelt die Residuen. Der erste Pol ist bei s = 1 (von der ζ–Funktion); er ist einfach, und das Residuum ist

β(1)\frac{1}{t} = \frac{π}{4t}.

Also

G(v) ∼ \frac{π}{4t},

und daher (1 − v ∼ t)

F (x) ∼ \frac{3 · 2}{t^{2}} · 1 · \frac{π}{4t} + ⋯ = \frac{3π}{2} \frac{1}{t^{3}} + ….

Da t ∼ \sqrt{3}\sqrt{1 − 3x}, heißt das

F (x) ∼ \frac{π}{2\sqrt{3}} \frac{1}{(1 − 3x)^{3/2}} ,

und weiter

[x^{n}]F (x) ∼ 3^{n} \frac{π}{2\sqrt{3}} \frac{n^{1/2}}{Γ(\frac{3}{2})} = 3^{n} \begin{matrix}√ & \overline{πn} \\ √ & \overline{3} \end{matrix} ,

was nach Division durch 3^{n} den Satz 2 ergibt.

Knödels Resultat folgt sofort: Da

φ_{i} = \frac{v^{i}(1 + v + v^{2})}{1 − v},

folgt

\begin{aligned}∑_{i≥0} iφ_{i} + 2φ_{β} & = \frac{1 + v + v^{2}}{1 − v} \frac{v}{(1 − v)^{2}} + … \\ & = \frac{3}{t^{3}} + … ∼ \frac{1}{\sqrt{3}}(1 − 3x)^{−3/2} + …; \end{aligned}

der Koeffizient von [x^{n}] darin ist asymptotisch

3^{n} \frac{1}{\sqrt{3}} \frac{1}{Γ(\frac{3}{2})}n^{1/2} = 3^{n} 2 \sqrt{\frac{n}{3π}} ;

das ist Satz 1.

Nun wollen wir noch kurz das Modell entsprechend Figur 2 skizzieren: Es ist

φ_{i,h} = \frac{x^{i}a_{h−i}}{a_{h+1}} = v^{i}(1 + v + v^{2})\frac{1 − v^{2h−2i+2}}{1 − v^{2h+4}} ,

und

Φ_{h} = ∑_{i=0}^{h} φ_{i,h} = \frac{1 + v + v^{2}}{1 − v} \frac{(1 − v^{h+1})(1 − v^{h+2})}{1 − v^{2h+4}}.

EINIGE KOMMENTARE ZU EINER BIN–PACKING AUFGABE VON W. KNÖDEL 7

Die erzeugende Funktion aller Wege ist der Grenzwert für h → ∞:

\frac{1 + v + v^{2}}{1 − v} .

Man muß wie vorher

\begin{aligned}F (x) & = ∑_{h≥0} [\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}}] \\ & = \frac{(1 + v + v^{2})(1 + v)}{1 − v} ∑_{h≥1} \frac{v^{h}}{1 + v^{h}} + … \end{aligned}

betrachten. Sei wieder

G(v) = ∑_{h≥1} \frac{v^{h}}{1 + v^{h}};

die Transformierte ist (v = e^{−t})

G^{∗}(s) = Γ(s)ζ^{2}(s)(1 − 2^{1−s}).

Also

G(v) = \frac{1}{2πi} ∫_{\frac{3}{2} −i∞}^{\frac{3}{2} +i∞}Γ(s)ζ^{2}(s)(1 − 2^{1−s})t^{−s}ds.

Bei s = 1 gibt es einen einfachen Pol mit Residuum \frac{log 2}{t}. Daher

F (x) ∼ \frac{6}{t} · \frac{log 2}{t} + … = \frac{6 log 2}{t^{2}} + … = \frac{2 log 2}{1 − 3x} + ….

Der Koeffizient von x^{n} darin ist asymptotisch 3^{n}2 log 2. Diese Größe muß dividiert werden durch

[x^{n}]\frac{1 + v + v^{2}}{1 − v} ∼ [x^{n}]\frac{3}{t}

∼ [x^{n}]\sqrt{3}(1 − 3x)^{−1/2} ∼ \sqrt{3} 3^{n} \frac{n^{−1/2}}{Γ(\frac{1}{2})}

= 3^{n}\sqrt{\frac{3}{πn}} .

Das ergibt Satz 4. Für Satz 3 beobachtet man

φ_{i} = v^{i}(1 + v + v^{2})

und

∑_{i≥0} iφ_{i} = (1 + v + v^{2})\frac{v}{(1 − v)^{2}} ∼ \frac{3}{t^{2}} = \frac{1}{1 − 3x};

der Koeffizient von x^{n} darin ist asymptotisch 3^{n}. Wieder muß dieser Ausdruck durch 3^{n}\sqrt{\frac{3}{πn}} dividiert werden.

Literatur

1. M.Abramowitz, I.A.Stegun, Handbook of Mathematical Functions, Dover, New York, 1970.

2. N.G.De Bruijn, D.E.Knuth, and S.O.Rice, The average height of planted plane trees, Graph Theory and Computing, R.C.Read, Ed., Academic Press, New York – London, 1972, pp. 15–22.

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

4. P.Flajolet and J.S.Vitter, Average–Case Analysis of Algorithms and Data Structures, Handbook of Theoretical Computer Science, J. van Leeuwen, Ed., North-Holland, 1990.

5. W.Knödel, Über das mittlere Verhalten von on-line Packungsalgorithmen, EIK 19 (1983), 427–433.

6. W.Panny and H.Prodinger, The expected height of paths for several notions of height, Stud. Sci. Math. Hung. 20 (1985), 119–132.

7. H.Prodinger, Einige Bemerkungen zu einer Arbeit von W.Knödel über das mittlere Verhalten von on-line-Packungsalgorithmen, EIK 21 (1985), 3–7.

8. H.Prodinger, Further Results on a Problem of Knödel concerning the Analysis of Bin-Packing, Number–Theoretic Analysis, E.Hlawka, R. F. Tichy (Eds.) Lecture Notes in Mathematics 1452 (1990), 193–198.

Technische Universität Wien Wiedner Hauptstraße 8-10 A-1040 Wien AUSTRIA