We study the behaviour of prudent, perimeter and quasi-prudent self-avoiding walks and polygons in both two and three dimensions, as well as some solvable subsets. Our analysis combines exact solutions of some simpler cases, careful asymptotic analys

The well-know needle experiment of Buffon can be regarded as an analog (i.e., continuous) device that stochastically “computes” the number 2/π ≐ 0.63661, which is the experiment's probability of success. Generalizing the experiment and simplifying the computational framework, we consider probability distributions, which can be produced perfectly, from a discrete source of unbiased coin flips. We describe and analyse a few simple Buffon machines that generate geometric, Poisson, and logarithmic-series distributions. We provide human-accessible Buffon machines, which require a dozen coin flips or less, on average, and produce experiments whose probabilities of success are expressible in terms of numbers such as . Generally, we develop a collection of constructions based on simple probabilistic mechanisms that enable one to design Buffon experiments involving compositions of exponentials and logarithms, polylogarithms, direct and inverse trigonometric functions, algebraic and hypergeometric functions, as well as functions defined by integrals, such as the Gaussian error function.

We consider the sequence comparison problem, also known as “ hidden ” pattern problem, where one searches for a given subsequence in a text (rather than a string understood as a sequence of consecutive symbols). A characteristic parameter is the number of occurrences of a given pattern w of length m as a subsequence in a random text of length n generated by a memoryless source. Spacings between letters of the pattern may either be constrained or not in order to define valid occurrences. We determine the mean and the variance of the number of occurrences, and establish a Gaussian limit law and large deviations. These results are obtained via combinatorics on words, formal language techniques, and methods of analytic combinatorics based on generating functions. The motivations to study this problem come from an attempt at finding a reliable threshold for intrusion detections, from textual data processing applications, and from molecular biology.

: Csisz'ar and Shields have recently proved that the minimax redundancy for a class of renewal processes is \\Theta( p n) where n is the block length. This interesting result provides a first non-trivial bound on redundancy for a non-parametric family of processes. The present paper provides a precise estimate up to the constant term of the redundancy rate for such sources. The asymptotic expansion is derived by complex--analytic methods that include generating function representations, Mellin transforms, singularity analysis and saddle point estimates. This work places itself within the framework of analytic information theory. Keywords. Analytic information theory, redundancy, Mellin transform, saddle point method, singularity analysis. Unit'e de recherche INRIA Rocquencourt Domaine de Voluceau, Rocquencourt, BP 105, 78153 LE CHESNAY Cedex (France) T'el'ephone : (33) 01 39 63 55 11 -- T'el'ecopie : (33) 01 39 63 53 Variations analytiques sur le taux de redondance des processus de...

Cauchy coefficient integrals and Hankel contours provide a natural generalization of Stirling numbers for unrestricted complex values of their arguments. Many classical identities survive such an extension.

A direct generating function construction is given for cycles of combinatorial structures.

The lattice reduction algorithm of Gauss is shown to have an average-case complexity that is asymptotic to a constant. The analysis makes use of elementary properties of continued fractions and of linear fractional transformations.>

This work presents a class of methods by which one can translate, on a term-by-term basis, an asymptotic expansion of a function around a dominant singularity into a corresponding asymptotic expansion for the Taylor coefficients of the function. This approach is based on contour integration using Cauchy’s formula and Hankel-like contours. It constitutes an alternative to either Darboux’s method or Tauberian theorems that appears to be well suited to combinatorial enumerations, and a few applications in this area are outlined.

New, improved algorithms are proposed for regulating access to a multiple-access channel, a common channel shared by many geographically distributed computing stations. A conflict of multiplicity n occurs when n stations transmit simultaneously to the channel. As a result, all stations receive feedback indicating whether n is 0, 1, or ≥2. If n = 1, the transmission succeeds; whereas if n ≥ 2, all the transmissions fail. Algorithms are presented and analyzed that allow the conflicting stations to compute a stochastic estimate n * of n , cooperatively, at small cost, as a function of the feedback elicited during its execution. An algorithm to resolve a conflict among two or more stations controls the retransmissions of the conflicting stations so that each eventually transmits singly to the channel. Combining one of our estimation algorithms with a tree algorithm (of Capetanakis, Hayes, and Tsybakov and Mikhailov) then leads to a hybrid algorithm for conflict resolution. Several efficient combinations are possible, the most efficient of which resolves conflicts about 20 percent faster on average than any of the comparable algorithms reported to date.

A precise analysis of partial match retrieval of multidimensional data is presented. The structures considered here are multidimensional search trees ( k -d-trees) and digital tries ( k -d-tries), as well as structures designed for efficient retrieval of information stored on external devices. The methods used include a detailed study of a differential system around a regular singular point in conjunction with suitable contour integration techniques for the analysis of k -d-trees, and properties of the Mellin integral transform for k -d-tries and extendible cell algorithms.

We study the number of registers required for evaluating arithmetic expressions formed with any set of unary and binary operators. Our approach consists in a singularity analysis of intervening generating functions combined with a use of (complex) Mellin inversion. We illustrate it first by rederiving the known results about binary trees and then extend it to the fully general case of unary–binary trees. The method used, as mentioned in the conclusion, is applicable to a wide class of combinatorial sums.

Several algorithms have been proposed which build search trees using digital properties of the search keys. A general approach to the study of the average case performance of such algorithms is discussed, with particular attention to the analysis of the digital search tree structures of Coflman and Eve. Specifically, the method leads to the solution of a problem left open by Knuth, finding the average number of nodes in digital search trees with both sons null. The paper may be of interest as a survey and tutorial treatment of the analysis of the three primary digital tree search methods: digital search trees, radix search tries, and Patricia tries.

An exact analysis is given of the main parameters that characterize the properties of the Capetanakis-Tsybakov-Mikhailov collision resolution algorithm with the free-access (continuous input) protocol. In particular, the distributions of the collision resolution interval, the delay experienced by a packet, and the state of the top level of the stack that is maintained by the algorithm are determined.

The throughput characteristics of contention-based random-access systems (RAS's) which useQ-ary tree algorithms (whereQ \geq 2is the number of groups into which contending users are split) of the Capetanakis-Tsybakov-Mikhailov-Vvedenskaya type are analyzed for an infinite population of identical users generating packets according to a Poisson process. Both free and blocked channel-access protocols are considered in combination withQ-ary collision resolution algorithms that exploit either binary ("collision/no collision") or ternary ("collision/ success / idle") feedback. For the resulting RAS's, functional equations for transformed generating functions of the first two moments of the collision resolution interval length are obtained and solved. The maximum stable throughput as a function ofQis given. The results of a packet-delay analysis are also given, and the analyzed RAS's are compared among themselves and with the slotted ALOHA system in terms of both system throughput and packet delay. It is concluded that the "practical optimum" RAS (in terms of ease of implementation combined with good performance) uses free (i.e., immediate) channel access and ternary splitting (i.e.,Q = 3) with binary feedback.

We present here a class of probabilistic algorithms with which one can estimate the number of distinct elements in a collection of data (typically a large file stored on disk) in a single pass, using only 0(1) auxiliary storage and 0(1) operations per element. We precisely quantify the accuracy-storage trade-offs: for instance a typical accuracy of about 5% can be achieved using only 256 binary words, even for very large files. The algorithms are totally insensitive to the replicative structure of the elements in the file. They are particularly adapted to data base systems in the context of query optimization and can be implemented in a decentralized manner (thus making them also useful for distributed data base applications).

This paper describes general evaluation methods for "partial-match retrieval" in multikey record files. An expected cost analysis is given for some of the major multidimensional tree structures which have been proposed in the data base and graphics literature.

We study a restricted programming language over tree structures. For this language, we give systematic translation rules which map programs into complexity descriptors. The descriptors are in the form of generating functions of average costs. Such a direct approach avoids the recourse to recurrences; it therefore simplifies the task of analyzing algorithms in the class considered and permits analysis of structurally complex programs. It also allows for a clear discussion of analytic properties of complexity descriptors whose singularities are related to the asymptotic behavior of average costs. Algorithms that are analyzed in this way include: formal differentiation, tree matching, tree embedding and simplification of expressions in a diversity of contexts. Some general results relating (average case) complexity properties to structural properties of programs in the class can also be derived in this framework.

The average height of a binary tree With n internal nodes is shown to be asymptotic to 2√πn. More generally, the average height of a tree in a simple family S with n nodes is asymptotic to c(S) √πn where c(S) is a number (usually algebraic) which can be explicitly determined from S. These results are achieved by means of a detailed singularity analysis of corresponding generating functions.

Delange has demonstrated an elegant method for computing the sum of all of the digits used when the first n nonnegative integers are expressed in base $q \geqq 2$. We show that his method can be adapted to unusual number systems such as Gray code and balanced ternary and can also be adapted to count the occurrences of each digit separately. As an application, we consider Sedgewick’s analysis of Batcher’s odd-even merge, and use our results about Gray code to provide an alternative, and perhaps more direct,derivation of the asymptotics of the average case.

This paper presents the average case performance analysis of dynamic data structures subjected to arbitrary sequences of insert, delete and query operations. To such sequences of operations are associated, for each data type, a specific continued fraction and a familly of orthogonal polynomials : Tchebycheff for stacks, Laguerre for dictionaries, Hermite for priority queues, Meixner for linear lists and Charlier for symbol tables. We define a notion of integrated cost of a data structure as the average cost over all possible sequences of operations. Our main result is an explicit expression, for each of these data structures, of the generating function for integrated costs as a linear integral transform of the generating functions for individual operation costs. We use the result to explicitly compute integrated costs of various efficient data structure implementations.

We introduce a notion of integrated cost of a dictionary, as average cost of sequences of search, insert and delete operations. We express generating functions of these sequences in terms of continued fractions; from this we derive an explicit integral expression of integrated costs for three common representations of dictionaries.

Let An be the average number of registers required for evaluating arithmetic expressions of size n, or, equivalently, the minimal stack needed for exploring binary trees with n nodes. We give explicit expressions for An and related quantities and show that: An = log4(n) + C + E(log4n) + o(1) where C = 1/2 - γ + 2/2 log2 + log2Π 0.292 and E is continuous, periodic with period 1, with average value 0 and amplitude less than .05.