Brownian motion and algorithm complexity

The Brownian motion is shown to be a useful tool in analysing some sorting and tree manipulation algorithms.     

An asymptotic series for an integral

The Ramanujan Journal - Let $$f(z)=\sum _{n=0}^{\infty }a_{n}{\mathbf {e}}(nz),g(z)=\sum _{n=0}^{\infty }b_{n}{\mathbf {e}}(nz)\ ({\mathbf {e}}(z)=e^{2\pi \sqrt{-1}z})$$ be holomorphic modular...     

Hashing techniques,a global approach

A new method for more equitable comparison of various hash table techniques is presented. It is applied to some popular techniques: open addressing, coalescent chaining and separate chaining. Another method, indexed sub-tables, is also examined with more details and shown to present some interesting features.     

Trie size in a dynamic list structure

This article considers a classical binary tree implementation of a set of keys: the trie. The trie size properties in a static environment are well known: The size is asymptotically Gaussian when the number of keys is large. In this article we analyze the trie in a dynamic environment, where the trie is allowed to grow and shrink in a probabilistic way. It appears that the trie size can be described by a stochastic process which is asymptotically Gaussian non-Markovian. This also allows the complete asymptotic analysis of the trie size maximum and the trie size integrated cost. © 1994 John Wiley & Sons, Inc.     

Advancing in the presence of a demon

We study a parameter that contains approximate counting, i.e., the level reached after n random increments, driven by geometric probabilities, and insertion costs for tries as special cases. We are able to compute all moments of this parameter in a semi-automatic fashion. This is another showcase of the machinery developed in an earlier paper of these authors. Roughly speaking, it works when the underlying distributions are distributed according to the Gumbel distribution, or something similar. G. Louchard visited this center in June 2006 and thanks for its hospitality.     

Phase transition for Parking blocks,Brownian excursion and coalescence

In this paper, we consider hashing with linear probing for a hashing table with m places, n items (n < m), and ? = m ? n empty places. For a noncomputer science‐minded reader, we shall use the metaphore of n cars parking on m places: each car c_i chooses a place p_i at random, and if p_i is occupied, c_i tries successively p_i + 1, p_i + 2, until it finds an empty place. Pittel [42] proves that when ?/m goes to some positive limit β < 1, the size B of the largest block of consecutive cars satisfies 2(β ? 1 ? log β)B = 2 log m ? 3 log log m + Ξ_m, where Ξ_m converges weakly to an extreme‐value distribution. In this paper we examine at which level for n a phase transition occurs between B = o(m) and m ? B = o(m). The intermediate case reveals an interesting behavior of sizes of blocks, related to the standard additive coalescent in the same way as the sizes of connected components of the random graph are related to the multiplicative coalescent. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 76–119, 2002     

Random 0-1 rectangular matrices: a probabilistic analysis

Carlitz considered in [5] $r \times n$ matrices with entries being zero or one and the number of changes, i.e., the number of (horizontally or vertically) adjacent entries which are different. We extend these results in many ways. For instance, we exhibit that the limiting distribution is Gaussian and get explicit formulæ for some moments even in the general instance of d dimensions (instead of just two).     

Analysis of a Recurrence Related to Critical Nonhomogeneous Branching Processes

Abstract

Some classes of controlled branching processes (with nonhomo-geneous migration or with nonhomo-geneous state-dependent immigration) lead in the critical case to a recurrence for the extinction probabilities. Under some additional conditions it is known that this recurrence depends on some parameter β and converges for 0 < β < 1. Now we show that the recurrence does converge for all positive values of the parameter β, which leads to an extension of some limit theorems for the corresponding branching processes. We also give a generalization of the recurrence and an asymptotic analysis of its behavior.