FURTHER RESULTS ON A PROBLEM OF KNÖDEL

CONCERNING

THE ANALYSIS OF BIN-PACKING

Helmut Prodinger

Department of Algebra and Discrete Mathematics University of Technology of Vienna, A-1040 Vienna, Austria

Abstract. Assume that inputs of size \frac{1}{4} , \frac{2}{4} , \frac{3}{4} , or 1 might occur with equal probabilities. If they are put into boxes of size 1 by the strategy best fit, there remains some empty space. This quantity has been evaluated asymptotically for n random insertions.

1. Introduction

W. Knödel [2] has considered buckets of size 1 and inputs of size \frac{1}{3}, \frac{2}{3}, 1 which occur with equal probabilities (\frac{1}{3} each). The strategy to fill the buckets is best fit ; in his instance a certain number of totally full buckets might occur, plus a certain number m of buckets filled with \frac{2}{3}. If m = 0 one bucket filled \frac{1}{3} is also possible.

The random variable of interest is E_{n}, i.e. the empty space after n random insertions; it is \frac{m}{3} or, eventually, \frac{2}{3}. The present author [4] has sharpened the original analysis [2] and has shown

E_{n} ∼ \frac{4}{3\sqrt{3}}\sqrt{\frac{n}{π}}.

Let us call the described problem the case 3.

In this note we want to present the analysis of the case 4.

However, we want to mention that a generalization is not at all obvious and definitely requires other methods. The case 4 is much more complex than the case 3, but (concerning the occuring states) one-dimensional, so that the generating functions of interest are related to context-free grammars and are henceforth algebraic. So we can use the method of Darboux to estimate the coefficients. As a general reference for this technique we mention [1]. For 5 or more this changes drastically.

We propose here to show:

Typeset by AMS-TEX

Discussions with Jean-Marc Steyaert are gratefully acknowledged.

Theorem. Let E_{n} be the empty space after n random insertions in the case-4-model. Then

E_{n} ∼ \frac{1}{4}\sqrt{\frac{n}{π}}.

We ran simulations, each based on 200 experiments of n insertions. We report here the ratio of the average empty space (experiment) over the leading term of the average empty space (theory):

n = 100  1.231
n = 500  1.053
n = 1000  1.080
n = 2000  0.898
n = 3000  1.038
n = 5000  0.970
n = 20000  1.025
n = 100000  1.040

2. The Analysis

The following figure explains the situation quite easily:

Here, q_{i} stands for i buckets, filled \frac{3}{4}, and p_{i} for i buckets filled \frac{3}{4}, plus one bucket, filled \frac{1}{2}. The state β stands for one bucket filled \frac{1}{4}. Each arrow must thought to be labelled with a (formal) variable x. From each state there are exactly 4 arrows starting, according to the four possible inputs \frac{1}{4}, \frac{2}{4}, \frac{3}{4}, 1. Observe that the loops have not been drawn in the figure.

However, for the computation, it is easier to neglect the loops at each state for a moment. In terms of generating functions that means that a function f(x) (without the loops) turns into \frac{1}{1−x}f(\frac{x}{1−x}) (with the loops).

FURTHER RESULTS ON A PROBLEM OF KNÖDEL CONCERNING THE ANALYSIS OF BIN-PACKING3

The transposed of the transition matrix is:

q_{0} β p_{0} q_{1} p_{1} q_{2} p_{2} ⋯
q_{0}  x x x
β x
p_{0} x x  x
q_{1} x x x  x x
p_{1}  x x  x
q_{2}  x  x ...
p_{2}  x x
⋮ ... ...

or

( \begin{matrix}B_{0} & C_{0} \\ D_{0} & B & C \\ & D & B & C \\ & & D & B & C \\ & & & ... & ... & ... \end{matrix} )

with

B = ( \begin{matrix}0 & x \\ x & 0 \end{matrix} ) , C = D = ( \begin{matrix}x & 0 \\ 0 & x \end{matrix} ) ,

and

B_{0} = ( \begin{matrix}0 & x & x \\ x & 0 & 0 \\ x & x & 0 \end{matrix} ) , C_{0} = ( \begin{matrix}x & 0 \\ 0 & 0 \\ 0 & x \end{matrix} ) , D_{0} = ( \begin{matrix}x & x & x \\ 0 & 0 & x \end{matrix} ) .

In [3] there is a method to get the generating functions in such a situation automatically:

Consider first

Z_{1} = C Z_{1} D Z_{1} + B Z_{1} + ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) .

Now, by symmetry, we may write

Z_{1} = ( \begin{matrix}f & g \\ g & f \end{matrix} )

and so

( \begin{matrix}f & g \\ g & f \end{matrix} ) = C ( \begin{matrix}f & g \\ g & f \end{matrix} ) D ( \begin{matrix}f & g \\ g & f \end{matrix} ) + B ( \begin{matrix}f & g \\ g & f \end{matrix} ) + ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) .

From this we get the following two equations for f(x) and g(x):

\begin{aligned}f & = x^{2}(f^{2} + g^{2}) + xg + 1 \\ g & = 2x^{2}fg + xf \end{aligned}

For simplicity we substitute as follows:

F = f + g, G = f − g, f = \frac{F + G}{2}, g = \frac{F − G}{2}

The two equations turn now into

\begin{aligned}F & = x^{2}F^{2} + xF + 1 \\ G & = x^{2}G^{2} − xG + 1 \end{aligned}

The generating function

M(x) = \frac{1 − x − \sqrt{1 − 2x − 3x^{2}}}{2x^{2}}

is well-known from Motzkin-statistics. With this notation we may write

F (x) = M(x), G(x) = M(−x)

\begin{aligned}f & = \frac{1}{2}(M(x) + M(−x)) \\ g & = \frac{1}{2}(M(x) − M(−x)). \end{aligned}

The generating functions discussed so far refer to a transition graph which ”forgets” about the irregular beginning. To handle this, we proceed as follows: We introduce generating functions, all of them describing path’s starting in the state q_{0} and landing in a specified state. Symbolically:

\begin{aligned}a_{1} : q_{0} & → q_{0} \\ a_{2} : q_{0} & → β \\ a_{3} : q_{0} & → p_{0} \\ b_{i} : q_{0} & → q_{i+1} \\ c_{i} : q_{0} & → p_{i+1} \end{aligned}

Also, let

S(0) = ( \begin{matrix}a_{1} \\ a_{2} \\ a_{3} \end{matrix} ) and T (i) = ( \begin{matrix}b_{i} \\ c_{i} \end{matrix} ) for i ≥ 0.

Then we have the following equations for the generating functions of interest:

\begin{aligned}( \begin{matrix}a_{1} \\ a_{2} \\ a_{3} \end{matrix} ) = S(0) & = x^{2} ( \begin{matrix}1 & 0 \\ 0 & 0 \\ 0 & 1 \end{matrix} ) ( \begin{matrix}f & g \\ g & f \end{matrix} ) ( \begin{matrix}1 & 1 & 1 \\ 0 & 0 & 1 \end{matrix} ) ( \begin{matrix}a_{1} \\ a_{2} \\ a_{3} \end{matrix} ) \\ & + x ( \begin{matrix}0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \end{matrix} ) ( \begin{matrix}a_{1} \\ a_{2} \\ a_{3} \end{matrix} ) + ( \begin{matrix}1 \\ 0 \\ 0 \end{matrix} ) \end{aligned}

T (i) = ( \begin{matrix}b_{i} \\ c_{i} \end{matrix} ) = x^{i} ( \begin{matrix}f & g \\ g & f \end{matrix} )^{i} ( \begin{matrix}1 & 1 & 1 \\ 0 & 0 & 1 \end{matrix} ) ( \begin{matrix}a_{1} \\ a_{2} \\ a_{3} \end{matrix} ) (i ≥ 0)

An easy proof by induction shows that

( \begin{matrix}f & g \\ g & f \end{matrix} )^{i} = \frac{1}{2} ( \begin{matrix}M(x)^{i} + M(−x)^{i} & M(x)^{i} − M(−x)^{i} \\ M(x)^{i} − M(−x)^{i} & M(x)^{i} + M(−x)^{i} \end{matrix} ) .

The function φ(x), representing the average empty space may be expressed by these functions as follows:

4 φ(x) = 3 a_{2} + 2 a_{3} + ∑_{i≥0}(i + 1) b_{i} + ∑_{i≥0}(i + 3) c_{i}.

Let us write the equations for a_{1}, a_{2}, a_{3} once again:

\begin{aligned}a_{1} & = x^{2}[f a_{1} + f a_{2} + f a_{3} + g a_{3}] + x(a_{2} + a_{3}) + 1 \\ a_{2} & = x a_{1} \\ a_{3} & = x^{2}[g a_{1} + g a_{2} + g a_{3} + f a_{3}] + x(a_{1} + a_{2}) \end{aligned}

From now on we restrict ourselves to local expansions around x ∼ \frac{1}{3}. Actually, there is another one at x = −\frac{1}{3}. However we must, as mentioned earlier, perform f(x) → \frac{1}{1−x}f(\frac{x}{1−x}); then \frac{1}{3} shifts to \frac{1}{4}, whereas −\frac{1}{3} shifts away.

\begin{aligned}M(x) & ∼ 3 − 3\sqrt{3}\sqrt{1 − 3x} \\ M(−x) & ∼ 6 − 3\sqrt{3} \\ ( \begin{matrix}a_{1} \\ a_{2} \\ a_{3} \end{matrix} ) & ∼ \frac{1}{\sqrt{1 − 3x}} ( \frac{3}{4}(\sqrt{3} − 1) ; \frac{\sqrt{3}−1}{4} ; \frac{1}{2} ) \\ ( \begin{matrix}b_{0} \\ c_{0} \end{matrix} ) & ∼ \frac{1}{\sqrt{1 − 3x}} ( \begin{matrix}−\frac{5}{2} + 2\sqrt{3} \\ \frac{5}{2} − \sqrt{3} \end{matrix} ) \\ T (i) & ∼ \frac{1}{2\sqrt{1 − 3x}} ( \begin{matrix}\sqrt{3} + (3\sqrt{3} − 5)(2 − \sqrt{3})^{i−1} \\ \sqrt{3} − (3\sqrt{3} − 5)2 − \sqrt{3})^{i−1} \end{matrix} ) (i ≥ 1) \end{aligned}

Now we come to our function φ(x).

4 ϕ(x) ∼ ∑_{i≥1} i b_{i} + ∑_{i≥1} i c_{i}

Let us recall an elementary formula:

∑_{i≥1} i x^{i} = \frac{x}{(1 − x)^{2}}

T (i) = ( \begin{matrix}b_{i} \\ c_{i} \end{matrix} ) = x^{i} ( \begin{matrix}f & g \\ g & f \end{matrix} )^{i} ( \begin{matrix}a_{1} + a_{2} + a_{3} \\ a_{3} \end{matrix} )

Therefore we find

∑_{i≥1} i b_{i} = \frac{a_{1} + a_{2} + 2a_{3}}{2} ∑_{i≥1} i(xF)^{i} + \frac{a_{1} + a_{2}}{2} ∑_{i≥1} i(xG)^{i}

= \frac{a_{1} + a_{2} + 2a_{3}}{2} \frac{xF}{(1 − xF)^{2}} + \frac{a_{1} + a_{2}}{2} \frac{xG}{(1 − xG)^{2}}

∑_{i≥1} i c_{i} = \frac{a_{1} + a_{2} + 2a_{3}}{2} ∑_{i≥1} i(xF)^{i} − \frac{a_{1} + a_{2}}{2} ∑_{i≥1} i(xG)^{i}

= \frac{a_{1} + a_{2} + 2a_{3}}{2} \frac{xF}{(1 − xF)^{2}} − \frac{a_{1} + a_{2}}{2} \frac{xG}{(1 − xG)^{2}} .

Henceforth

φ ∼ \frac{\sqrt{3}}{12}(1 − 3x)^{−3/2}.

Now we perform f(x) → \frac{1}{1−x}f(\frac{x}{1−x}), changing the singularity of interest from \frac{1}{3} to \frac{1}{4}. The transformed φ-function behaves around \frac{1}{4} like

φ(x) ∼ \frac{\sqrt{3}}{12} \frac{1}{1 − x}(1 − \frac{3x}{1 − x})^{−3/2}

∼ \frac{\sqrt{3}}{12} \frac{4}{3} (\frac{1 − 4x}{\frac{3}{4}})^{−3/2}

∼ \frac{1}{8}(1 − 4x)^{−3/2}.

Let [x^{n}]φ(x) denote, as usual, the coefficient of x^{n} in φ(x). By Darboux’s technique we may write

E_{n} ∼ 4^{−n} \frac{1}{8} [x^{n}](1 − 4x)^{−3/2}

∼ 4^{−n} \frac{1}{8} \frac{4^{n} n^{1/2}}{Γ(\frac{3}{2})}

= \frac{1}{8} \begin{matrix}√ & \overline{n} \\ \frac{1}{2} & \sqrt{π} \end{matrix}

= \frac{1}{4}\sqrt{\frac{n}{π}}.

This completes the proof.

References

1. P.Flajolet and J.Vitter, Average-Case Analysis of Algorithms and Data Structures, in: Handbook of Theoretical Computer Science, North-Holland, to appear 1990.

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

3. W.Kuich and F.J.Urbanek, Infinite Linear Systems and One Counter Languages, Theor.Comput. Sci. (1983), 95–126.

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

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