We can also analyze the behavior of the system of balls-and-bins using
two or more choices in a quite different way. This method is referred
to as the \emph{fluid-limit} approach because it replaces the discrete
balls-and-bins system with a simpler approximation similar to those
that occur in fluid systems
\cite{mitzenmacher99:_study_balan_alloc_differ_equat}. The essential
idea is that we will express some property of a system of balls and
bins with a Markov chain, then consider the limit of the system as the
number of balls and bins approaches infinity. We can model the
limiting behavior of the Markov process as a differential equation.
Even though the actual number of bins is finite, the solution to the
differential equation is a close approximation to the behavior in the
finite-size case with high probability.

We give an example to better understand this approach. We will begin
by proving a result about the balls-and-bins problem with $d$
choices. 

\begin{theorem}
  Suppose we throw $m = cn$ balls into $n$ bins, where each ball is
  placed in the least-loaded of $d$ bins selected independently and
  uniformly at random. Define $y(c)$ to be the value satisfying
  \[ c = \sum_{i=0}^\infty \frac{y(c)^{id+1}}{id+1} \]
  (or 1, whichever
  is smaller).  Then the fraction of non-empty bins is within
  $\bigO{\sqrt{\frac{\log n}{n}}}$ of $y(c)$.
\end{theorem}

\begin{proof}
  Suppose $T$ balls have been thrown. Let $Y(T)$ be the number of
  non-empty bins at this time. Unless all of the bins selected for the
  next ball are among the $Y(T)$ ones that area already non-empty, a
  new bin will be made non-empty. This gives the recurrence for our
  Markov chain:
  \begin{equation}
    \Exp{Y(T-1) - Y(T)} = 1 - \left(\frac{Y(T)}{N}\right)^d
  \end{equation}
  or, if we let $t = \nicefrac Tn$ and $y(t) = \frac{Y(t)}{n}$,
  \begin{equation}
    \label{eq:empty-markov-scaled}
    \frac{\Exp{y(t + \nicefrac{1}{n}) - y(t)}}{\nicefrac{1}{n}} = 1 -
    \left(y(t)\right)^d
  \end{equation}

  The form of \eqref{eq:empty-markov-scaled} suggests that in
  the limit as $n \to \infty$, the solution approaches that of the
  differential equation
  \begin{equation}
    \label{eq:empty-diffeq}
    \der{y}{t} = 1 - y^d
  \end{equation}
  which we can express instead as
  \begin{equation}
    \label{eq:empty-diffeq-alt}
    \der{t}{y} = \frac{1}{1-y^d} = \sum_{i=0}^\infty y^{id}
  \end{equation}
  and easily solve by integration to see that
  \begin{equation}
    \label{eq:empty-diffeq-solution}
    t = \sum_{i=0}^\infty \frac{y(c)^{id+1}}{id+1}
  \end{equation}
  This solution is the result we wish to prove, if we take $t = c$.
  The missing ingredient in this proof is the proof that the solution
  to the differential equation in \eqref{eq:empty-diffeq} is
  actually close to the solution of the discrete process modeled by
  \eqref{eq:empty-markov-scaled}, with the high-probability
  error bound stated in the theorem. The proof of this claim is quite
  technical and so will not be presented here. It relies upon Kurtz's
  theorem \cite{kurtz70:_solut_markov} which --- very informally
  stated --- shows that for scaled Markov chains like
  \eqref{eq:empty-markov-scaled}, taking the limit as $n \to
  \infty$ does in fact describe the limiting behavior of the
  system. It also gives a Chernoff-like bound: the probability that
  the deviation is at least $\epsilon$ is $\bigO{e^{-nC(\epsilon)}}$
  for some function $C(\epsilon) =
  \bigTheta{\frac{1}{\epsilon^2}}$. This can be used to obtain the
  desired error bound.
\end{proof}

This method is quite flexible, and can be used for much more complex
analyses. For example, one can create a \emph{family} of differential
equations representing the fraction of bins that contain at least $i$
balls, for all $i$. The resulting differential equations cannot
readily be solved, but they can be analyzed to see that as $i$
increases, the fraction of bins containing at least $i$ decreases
doubly-exponentially. This leads to an alternate proof of the
now-familiar result that the heaviest-loaded bin contains $\bigO{\log
  \log n}$ balls, with high probability.

We will return to this technique later, when we use it in
Sections~\ref{sec:variations:memory}~and~\ref{sec:applications:load-balancing}
to prove other results.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "paper"
%%% End: