The Complete Solution of the Competitive Rank Selection Problem

Two decision-makers A and B observe sequentially a given permutation of n uniquely rankable options. A and B have one choice each (without recall) and both must make a choice. At each step only the relative ranks are known, and A has the priority of choice. At the end the (absolute) ranks are compared and the winner is the one who has chosen the better rank. Extending results by Enns and Ferenstein [6] and Berry et al. [1] this article gives, for both A and B , the optimal strategy and the corresponding winning probabilities. We show in particular that the limiting winning probabilities for A and B do exist, which closes a most important gap in the work of previous authors. This also provides an algorithm for numerically computing the limiting value of these probabilities. Although our proof is analytic in a strong sense, it is interesting to see that it would have been very hard to assemble it without the help of computer algebra. The reason is that the functions we have to investigate display subranges of indices which contrast considerably with respect to error terms when certain terms are replaced by approximations, and that computations were very helpful to locate those ranges where a particularly fine tuning of error estimates turned out to be indispensable. Received October 1997; revised March 15, 1998.     

On the average redundancy rate of the Lempel-Ziv code

In this paper, we settle a long-standing open problem concerning the average redundancy r_n of the Lempel-Ziv'78 (LZ78) code. We prove that for a memoryless source the average redundancy rate attains asymptotically Er_n=(A+δ(n))/log n+ O(log log n/log² n), where A is an explicitly given constant that depends on source characteristics, and δ(x) is a fluctuating function with a small amplitude. We also derive the leading term for the kth moment of the number of phrases. We conclude by conjecturing a precise formula on the expected redundancy for a Markovian source. The main result of this paper is a consequence of the second-order properties of the Lempel-Ziv algorithm obtained by Jacquet and Szpankowski (1995). These findings have been established by analytical techniques of the precise analysis of algorithms. We give a brief survey of these results since they are interesting in their own right, and shed some light on the probabilistic behavior of pattern matching based data compression     

Average profile and limiting distribution for a phrase size in theLempel-Ziv parsing algorithm

Consider the parsing algorithm developed by Lempel and Ziv (1978) that partitions a sequence of length n into variable phrases (blocks) such that a new block is the shortest substring not seen in the past as a phrase. In practice, the following parameters are of interest: number of phrases, the size of a phrase, the number of phrases of given size, and so forth. In this paper, we focus on the size of a randomly selected phrase, and the average number of phrases of a given size (the so-called average profile of phrase sizes). These parameters can be efficiently analyzed through a digital search tree representation. For a memoryless source with unequal probabilities of symbols generation (the so-called asymmetric Bernoulli model), we prove that the size of a typical phrase is asymptotically normally distributed with mean and variance explicitly computed. In terms of digital search trees, we prove the normal limiting distribution of the typical depth (i.e., the length of a path from the root to a randomly selected node). The latter finding is proved by a technique that belongs to the toolkit of the “analytical analysis of algorithms”, and it seems to be novel in the context of data compression     

The brownian excursion area: a numerical analysis

Using an explicit expression for the Laplace transform of the Brownian excursion area generating function, a numerical analysis gives moments, density, and distribution function. An asymptotic formula is given for small argument.     

Asymptotics of the Moments of Extreme-Value Related Distribution Functions

The asymptotic cost of many algorithms and combinatorial structures is related to the extreme-value Gumbel distribution exp(-exp(-x)). The following list is not exhaustive: Trie, Digital Search Tree, Leader Election, Adaptive Sampling, Counting Algorithms, trees related to the Register Function, Composition of Integers, some structures represented by Markov chains (Column-Convex Polyominoes, Carlitz Compositions), Runs and number of distinct values of some multiplicity in sequences of geometrically distributed random variables. Sometimes we can start from an exact (discrete) probability distribution, sometimes from an asymptotic analysis of the discrete objects (e.g., urn models) before establishing the relationship with the Gumbel distribution function. Also some Markov chains are either exactly and directly given by the structure itself, or as a limiting Markov process. The main motivation of the paper is to compute the asymptotic distribution and the moments of the random variables in question. The moments are usually given by a dominant part and a small fluctuating part. We use Laplace and Mellin transforms and singularity analysis and aim for a unified treatment in all cases. Furthermore, our goal is a purely mechanical computation of dominant and fluctuating components, with the help of a computer algebra system. We provide each time the first three moments, but the treatment is (almost) completely automatic. We need some real analysis for the approximations and apart from that only easy complex analysis; simple poles and a few special functions.     

Interpretation of hyperspectral remote-sensing imagery by spectrum matching and look-up tables

A spectrum-matching and look-up-table (LUT) methodology has been developed and evaluated to extract environmental information from remotely sensed hyperspectral imagery. The LUT methodology works as follows. First, a database of remote-sensing reflectance (Rrs) spectra corresponding to various water depths, bottom reflectance spectra, and water-column inherent optical properties (IOPs) is constructed using a special version of the HydroLight radiative transfer numerical model. Second, the measured Rrs spectrum for a particular image pixel is compared with each spectrum in the database, and the closest match to the image spectrum is found using a least-squares minimization. The environmental conditions in nature are then assumed to be the same as the input conditions that generated the closest matching HydroLight-generated database spectrum. The LUT methodology has been evaluated by application to an Ocean Portable Hyperspectral Imaging Low-Light Spectrometer image acquired near Lee Stocking Island, Bahamas, on 17 May 2000. The LUT-retrieved bottom depths were on average within 5% and 0.5 m of independently obtained acoustic depths. The LUT-retrieved bottom classification was in qualitative agreement with diver and video spot classification of bottom types, and the LUT-retrieved IOPs were consistent with IOPs measured at nearby times and locations.     

Analytic Variations on the Airy Distribution

The Airy distribution (of the ``area' type) occurs as a limit distribution of cumulative parameters in a number of combinatorial structures, like path length in trees, area below walks, displacement in parking sequences, and it is also related to basic graph and polyomino enumeration. We obtain curious explicit evaluations for certain moments of the Airy distribution, including moments of orders -1 , -3 , -5 , etc., as well as +\frac13 , -\frac53 , -\frac 11 3 , etc. and -\frac73 , -\frac 13 3 , -\frac 19 3 , etc. Our proofs are based on integral transforms of the Laplace and Mellin type and they rely essentially on ``non-probabilistic' arguments like analytic continuation. A by-product of this approach is the existence of relations between moments of the Airy distribution, the asymptotic expansion of the Airy function \Ai(z) at +∈fty , and power symmetric functions of the zeros -α _k of \Ai(z) . Received June 6, 2000; revised February 17, 2001.     

Robust variations of interpolation search: An asymptotic analysis

The Brownian Motion is used as a tool in analysing several variations of Interpolation Search when applied to non-uniform distributions. Asymptotic distributions, mean and variance are obtained for the number of probes before success.