Linear Probing

[Philippe Flajolet <Philippe.Flajolet@inria.fr>]

Thanks to Helmut for pointing to the brand new note by Don.
It is now an item under the Research pages.

Here are a few technical comments (from a letter of July 18, 1997).

Consider the distribution of total displacement (=contruction time)
in linear probing.
Thus, Knuth, Viola, and Poblete have an analysis of
variance and a way to determine all moments.
Now, I claim that if you plot the histograms of the distribution for
large n, you'll see a common shape appearing. I'd like to call this
limit distribution the "Airy distribution".

Roughly, we know from Knuth that the distribution of total displacement
in LP tables is the same as the distribution of inversions in trees, and
this in turn is such that its binomial moments are determined by the
counting of connected graphs of small "excess" (=#edges-#nodes). But by
a note of Spencer [relating connected graphs and walks], we infer
further that the tree-inversion distribution is the same as the
distribution of area in nonnegative random walks (RW) that was analysed
asymptotically by Louchard in connection with Brownian motion. This in
turn, by results of Takacs, is the same in the asymptotic limit as the
distribution of path length in random trees.

Therefore, we have a major ring of combinatorial distributions that are
all asymptotically equivalent:

	Displacement in LP     <====>   Inversion in trees
                               <====>    Area in walks
                               <====>    Path length in trees

I propose to call this distribution the Airy distribution (Ai) as it is
expressible in terms of the Airy function. It is related to connected
graphs by the equivalence
	
	Binomial Moments [Ai]   <====> # Connected graphs/excess.


For nonfull tables (fixed filling ratio), I believe there is a Gaussian
limit distribution.

I hope to report soon on this.

Patricio, Alfredo. Are you on-line?

	Cheers,

	Philippe

---------------------------------------------------
Philippe Flajolet
Algorithms Project, INRIA Rocquencourt
F-78153 Le Chesnay (France)
Tel: +33 (1) 39.63.56.26 / 39.63.54.43 [secr.]
Fax: +33 (1) 39.63.53.87
E-mail: Philippe.Flajolet@inria.fr
WWW: http://www-rocq.inria.fr/algo/flajolet/index.html
 +++ANALYSIS of ALGORITHMS pages:
http://www-rocq.inria.fr/algo/AofA/index.html
---------------------------------------------------