%Lecture Notes in Mathematics

\vsize =19.58 cm
\hsize =13.33 cm
%\nologo
\input amstex
\documentstyle{amsppt}

\topmatter
\title
FURTHER RESULTS ON A PROBLEM OF KN\"ODEL\\
CONCERNING\\
THE ANALYSIS OF BIN-PACKING
\endtitle
\author
Helmut Prodinger
\endauthor
\affil
Department of Algebra and Discrete Mathematics\\
University of Technology of Vienna, A-1040 Vienna, Austria
\endaffil
\address
\flushpar Technische Universit\"at Wien\newline 
Wiedner Hauptstra{\ss}e 8-10\newline
A-1040 Wien\newline  AUSTRIA
\endaddress
\thanks{Discussions with Jean-Marc Steyaert are gratefully acknowledged.}
\endthanks
\abstract
Assume that inputs of size $\frac 14$, $\frac 24$, $\frac 34$, or 1 might
occur with equal probabilities. If they are put into boxes of size 1 by
the strategy {\it best fit}, there remains some {\it empty space}. This
quantity has been evaluated asymptotically for $n$ {\it random insertions}.
\endabstract
\endtopmatter

\document

\heading
1. Introduction
\endheading

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

The random variable of interest is $E_n$, i.e. the empty space after $n$
random insertions; it is $\frac m3$ or, eventually, $\frac 23$.
The present author \cite 4
 has sharpened the original analysis \cite 2 and has shown
$$
E_n \sim \frac 4{3\sqrt3} \sqrt{ \frac n{\pi}} .
$$
Let us call the described problem the {\it case 3}.

In this note we want to present the analysis of the {\it case 4}.

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

We propose here to show:
\proclaim{Theorem}
Let $E_n$ be the empty space after n random insertions in the case-4-model.
Then
$$
E_n \sim \frac 14 \sqrt{\frac n{\pi}}.
$$
\endproclaim

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):
$$
\alignat 2
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\\
 &&&\\
 &&&
\endalignat
$$

\heading
2. The Analysis
\endheading

The following figure explains the situation quite easily:

\vskip 5 cm

Here, $q_i$ stands for $i$ buckets, filled $\frac 34$, and $p_i$ for 
$i$ buckets filled $\frac 34$, plus one bucket, filled $\frac 12$. The state
$\beta$ stands for one bucket filled $\frac 14$. 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 14$, $\frac 24$, $\frac 34$, $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).

The {\it transposed} of the {\it transition matrix} is:
$$
\matrix
    & q_0 & \beta\  & p_0 & q_1 & p_1 & q_2 & p_2 & \cdots \\
q_0 &     & x       & x   & x   &     &     &      \\
\beta & x &         &     &     &     &     &      \\
p_0 & x   & x       &     &     & x   \\
q_1 & x   & x       & x   &     & x   & x   \\
p_1 &     &         & x   & x   &     &     & x   \\
q_2 &     &         &     & x   &     &     & x   & \ddots \\
p_2 &     &         &     &     & x   & x   \\
\vdots &  &         &     &     &     & \ddots &  & \ddots
\endmatrix
$$
or
$$
\pmatrix B_0 & C_0 \\
         D_0 & B   & C \\
             & D   & B   & C \\
             &     & D   & B   & C \\
             &     &     & \ddots &\ddots &\ddots \\
\endpmatrix
$$
with
$$
B=\pmatrix 0 & x \\
           x & 0 \endpmatrix, \  
C=D=\pmatrix x & 0\\
             0 & x \endpmatrix,
$$
and
$$
B_0 =  \pmatrix 0 & x & x \\ 
                x & 0 & 0 \\ 
                x & x & 0 
\endpmatrix ,\ 
C_0=\pmatrix x & 0 \\ 
             0 & 0 \\ 
             0 & x \endpmatrix ,\ 
D_0=\pmatrix x & x & x \\ 
             0 & 0 & x \endpmatrix .
$$

In \cite{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+ \pmatrix 1 & 0 \\ 0 & 1 \endpmatrix .
$$
Now, by symmetry, we may write
$$
Z_1= \pmatrix f & g \\ g & f \endpmatrix 
$$
and so
$$
\pmatrix f & g \\ g & f \endpmatrix 
=
C\,\pmatrix f & g \\ g & f \endpmatrix \,
D\,
\pmatrix f & g \\ g & f \endpmatrix
+B\,
\pmatrix f & g \\ g & f \endpmatrix
+ \pmatrix 1 & 0 \\ 0 & 1 \endpmatrix.
$$
From this we get the following two equations for $f(x)$ and $g(x)$:
$$
\aligned
f&=x^2(f^2+g^2)+xg+1 \\
g&=2x^2fg +xf
\endaligned
$$
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
$$
\aligned
F&=x^2F^2+xF+1 \\
G&=x^2G^2-xG+1
\endaligned
$$
The generating function
$$
M(x)=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}
$$
is well-known from {\it Motzkin-statistics}. With this notation we may
write
$$
F(x)=M(x),\ G(x)=M(-x)
$$
$$
\aligned
f&=\frac 12 \Big( M(x)+M(-x) \Big)\\
g&=\frac 12 \Big( M(x)-M(-x) \Big).
\endaligned
$$

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:
$$
\aligned
a_1 \ \ \ : \ q_0 &\to q_0 \\
a_2 \ \ \ : \ q_0 &\to \beta \\
a_3 \ \ \ : \ q_0 &\to p_0 \\
b_i \ \ \ : \ q_0 &\to q_{i+1} \\
c_i \ \ \ : \ q_0 &\to p_{i+1}
\endaligned
$$
Also, let
$$
S(0)=\pmatrix a_1 \\ a_2 \\ a_3 \endpmatrix
\ \ \ \text{and} \ \ 
T(i)=\pmatrix b_i \\ c_i \endpmatrix 
\ \text{for} \ \ i \ge 0.
$$
Then we have the following equations for the generating functions of
interest:
$$
\aligned
\pmatrix a_1 \\ a_2 \\ a_3 \endpmatrix
=S(0)&=
x^2 \, 
\pmatrix 1 & 0 \\ 0 & 0 \\ 0 & 1 \endpmatrix
\pmatrix f & g \\ g & f \endpmatrix
\pmatrix 1 & 1 & 1 \\ 0 & 0 & 1 \endpmatrix
\pmatrix a_1 \\ a_2 \\ a_3 \endpmatrix \\
&+x \,
\pmatrix 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \endpmatrix
\pmatrix a_1 \\ a_2 \\ a_3 \endpmatrix
+\pmatrix 1 \\ 0 \\ 0 \endpmatrix
\endaligned
$$
$$
T(i)=\pmatrix b_i \\ c_i \endpmatrix 
=x^i \,
\pmatrix f & g \\ g & f \endpmatrix ^i \,
\pmatrix 1 & 1 & 1 \\ 0 & 0 & 1 \endpmatrix
\pmatrix a_1 \\ a_2 \\ a_3 \endpmatrix
\ \ \ \ \ (i \ge 0)
$$
An easy proof by induction shows that
$$
\pmatrix f & g \\ g & f \endpmatrix ^i 
= \frac 12
\pmatrix
M(x)^i+M(-x)^i &
M(x)^i-M(-x)^i \\
M(x)^i-M(-x)^i &
M(x)^i+M(-x)^i
\endpmatrix .
$$

The function $\varphi (x)$, representing the {\it average empty space} may be
expressed by these functions as follows:
$$
4 \,
\varphi (x)=
3 \,
a_2 + 2\,a_3 + \sum_{i \ge 0} (i+1) \, b_i + \sum_{i \ge 0} (i+3)\, c_i.
$$

Let us write the equations for $a_1, a_2, a_3$ once again:
$$
\aligned
a_1&=x^2 \big[f \, a_1 + f \, a_2 + f \, a_3 + g \, a_3\big]+x(a_2+a_3)+1 \\
a_2&=x \, a_1 \\
a_3&=x^2 \big[g \, a_1 + g \, a_2 + g \, a_3 + f \, a_3\big] + x(a_1 + a_2)
\endaligned
$$

From now on we restrict ourselves to local expansions around $ x \sim \frac 13$.
Actually, there is another one at $x=- \frac 13$. However we must, as
mentioned earlier, perform $f(x) \to \frac 1{1-x}f( \frac x{1-x})$;
then $\frac 13$ shifts to $\frac 14$, whereas $ - \frac 13$ shifts away.

$$
\aligned
M(x)& \sim 3-3 \sqrt 3 \sqrt{1-3x} \\
M(-x)& \sim 6-3 \sqrt 3 \\
\pmatrix a_1 \\ a_2 \\ a_3 \endpmatrix
& \sim 
\frac 1{\sqrt{1-3x} } 
\pmatrix \frac 34 (\sqrt 3 -1) \\ \frac{\sqrt 3 -1}4 \\ 
\frac 12 \endpmatrix \\
\pmatrix b_0 \\ c_0 \endpmatrix
& \sim 
\frac 1{\sqrt{1-3x}} 
\pmatrix - \frac 52 + 2 \sqrt 3 \\ \frac 52 - \sqrt 3 \endpmatrix \\
T(i)& \sim \frac 1{2 \sqrt{1-3x}} 
\pmatrix \sqrt 3 + (3 \sqrt 3 -5)(2- \sqrt 3)^{i-1} \\
         \sqrt 3 - (3 \sqrt 3 -5)2 - \sqrt 3)^{i-1} 
\endpmatrix \ \ (i \ge 1)
\endaligned
$$
     

Now we come to our function $\varphi (x)$.
$$
4 \, \phi (x) \sim \sum_{i \ge 1 } i \, b_i + \sum_{i \ge 1 } i \, c_i
$$
Let us recall an elementary formula:
$$
\sum_{i \ge 1} i \, x^i = \frac x{(1-x)^2}
$$
$$
T(i) = \pmatrix b_i \\ c_i \endpmatrix
=x^{i} \, \pmatrix f & g \\ g & f \endpmatrix ^i
\pmatrix a_1 + a_2 + a_3 \\ a_3 \endpmatrix
$$ 
                     
Therefore we find
$$
\aligned
\sum_{i \ge 1 } i \, b_i &= 
\frac{a_1+a_2+2a_3}2 \sum_{i \ge 1 } i(xF)^i + 
\frac{a_1+a_2}2 \sum_{i \ge 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} \\
\sum_{i \ge 1 } i \, c_i &= 
\frac{a_1+a_2+2a_3}2 \sum_{i \ge 1 } i(xF)^i - 
\frac{a_1+a_2}2 \sum_{i \ge 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}.
\endaligned
$$

Henceforth
$$
\varphi \sim \frac{\sqrt 3}{12}\big(1-3x\big)^{-3/2}.
$$

Now we perform $f(x) \to \frac 1{1-x}f( \frac x{1-x})$, changing the
singularity of interest from $\frac 13$ to $\frac 14$. The transformed
$\varphi$-function behaves around $\frac 14$ like
$$
\aligned
\varphi(x) & \sim \frac{\sqrt 3}{12} 
                      \frac 1{1-x} \Big(1- \frac{3x}{1-x}\Big)^{-3/2} \\
        & \sim \frac{\sqrt 3}{12} \frac 43 
          \left(\frac{1-4x}{\frac 34}\right)^{-3/2} \\
        & \sim \frac 18 \big(1-4x\big)^{-3/2}.
\endaligned
$$
Let $[x^n] \varphi (x)$ denote, as usual, the coefficient of $x^n$ in
$\varphi (x)$. By {\it Darboux's technique}  we may write
$$
\aligned
E_n & \sim  4^{-n} \, \frac 18 \, [x^n] (1-4x)^{-3/2} \\
    & \sim  4^{-n} \, \frac 18 \, \frac{4^n \,
          n^{1/2}}{\Gamma (\frac 32)} \\
    &= \frac 18 \frac{\sqrt n}{\frac 12 \sqrt \pi} \\
    &= \frac 14 \sqrt{\frac n{\pi}} .
\endaligned
$$
This completes the proof.


\Refs

\ref \no 1 \by P.Flajolet and J.Vitter \paper Average-Case Analysis of
Algorithms and Data Structures \paperinfo in: Handbook of Theoretical
Computer Science, North-Holland, to appear 1990
\endref

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

\ref \no 3 \by W.Kuich and F.J.Urbanek \paper Infinite Linear
Systems and One Counter Languages \jour Theor.Comput.\linebreak Sci.
\yr 1983 \pages 95--126 \endref
  
\ref \no 4 \by H.Prodinger \paper Einige Bemerkungen zu einer Arbeit
von W.Kn\"odel \"uber das mittlere Verhalten von on--line--Packungsalgorithmen
 \jour EIK \yr 1985 \pages 3--7 \vol 21
\endref

\endRefs

\enddocument




