back to the main page.

Recent preprints and publications by themes, with abstracts.
Under construction !

Analysis of Algorithms

Hashing with linear probing.

• Parking functions, empirical processes and the width of rooted labeled trees. (with J.F. MARCKERT). In preparation. (18p., ps.gz  518Ko)
  In this paper we give tight bounds for the moments of the width of rooted labeled trees with $n$ nodes, answering an open question of Odlyzko and Wilf (1987, Bandwidths and profiles of trees, J. Comb. Theory, Ser. B 42, 348-370). We use a well known one to one mapping between trees and parking functions, and a precise coupling between parking functions and empirical processes of mathematical statistics.

• Phase transition for parking blocks, Brownian excursion and coalescence (with Guy LOUCHARD).In preparation.
  updated Nov 15, 1999     (36p., ps.gz  220Ko, with figures)    dvi  (without  figures)  136Ko
  Preprint 99/34, Institut Elie Cartan (obsolete)     (34p., ps.gz  189Ko)
  In this paper, we consider hashing with linear probing for a hashing table with $n$ places $m(n)$ items, and $E(n)=n-m(n)$ empty places. For a non computer science-minded reader, we shall use the metaphore of $m(n)$ cars parking on $n$ 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 (1987) proves that when $E(n)/n$ goes to some positive limit $\alpha<1$, the size of the largest block of consecutive cars $B_n$ satisfies $B_n=A(\alpha)\log n+B(\alpha) \log\log n+C(\alpha)Z_n$, where $Z_n$ converges weakly to an extreme-value distribution. In this paper we examine at which level for $m(n)$ a phase transition occurs between $B_n=o(n)$ and $n-B_n=o(n)$. The intermediate case reveals an interesting behaviour of sizes of blocks, related to the standard additive coalescent of Aldous and Pitman. The main tool is a coupling between parking functions on one hand and empirical processes of mathematical statistics, on the other hand.

• A Vervaat-like path transformation for the reflected Brownian bridge conditioned on its local time at 0, (with Svante JANSON)  Preprint 99/39, Institut Elie Cartan.
  24p., ps.gz  160Ko    dvi  (without  figures)  93Ko
  Following previous works of Vervaat, Denisov, Bertoin and Pitman, among others ..., on the simple symmetric random walk, we use combinatorial properties to prove identities between various transformed sample paths of Brownian motion, but here parking replaces the simple symmetric random walk.

Majority problem.

• Determining the majority: the biased case, Annals of Applied Probability Vol. 7, No. 2, 1997, 523-544 (23 pages, ps.gz 624Ko)

• The average complexity of a coin-weighing problem (with Alonso, L., & Schott, R.), Random Structures Algorithms 9 (1&2), 1996, 1-14. (17 pages, ps.gz 712Ko)

• The chip problem (with Laurent ALONSO, Edward M REINGOLD and René SCHOTT) Prepublication de l'Institut Elie Cartan 1998-10-07. (ps.gz 138Ko)

  The ``chip problem" is a fault diagnosis problem in which we must determine which components (chips) in a system are defective, assuming the majority of them are good. Chips are tested as follows : Take two chips, say $x$ and $y$, and have $x$ report whether $y$ is good or bad. If $x$ is good, the answer is correct, but if $x$ is bad, the answer is unreliable and can be either wrong with probability $\alpha$ or right with probability $1-\alpha$. We show that the chip problem is closely related to a modified majority problem in the {\it worst case} and use this fact to obtain upper and lower bounds on algorithms for the chip problem. We show the limits of this relationship by showing that algorithms for the chip problem can violate lower bounds on {\it average performance} for the modified majority problem and we give an algorithm for the ``biased chip" problem (in which $p$ is the probability that a chip is bad) whose average performance is better than the average cost of the best algorithm for the biased majority problem. Key words: fault diagnosis ; algorithm analysis ; chip problem ; majority problem ; probabilistic algorithms
  
  

Optimal search.

• How many probes are needed to compute the maximum of a random walk ? Prepublication de l'Institut Elie Cartan 1997-(to appear in Stochastic Process. Appl.) (ps.gz 105Ko)
  

• A Stochastically Quasi-Optimal Algorithm (with J.F. MARCKERT and M. YOR) Prepublication de l'Institut Elie Cartan 99.3 (1999). (30 p. ps.gz 159Ko)

  Odlyzko (Search for the maximum of a random walk, Random Struct. Alg. 6 (1995), pp. 275-295) examines the efficiency of various strategies for searching in an unknown environment. He describes an average case quasi-optimal algorithm for the search of the maximum of a n-length symmetric random walk. In this paper, we prove that the same algorithm is also quasi-optimal for the stochastic order and we characterise the limit law of its cost: the limit cost has the same law as an unusual Brownian functional. Computing its moments two ways, we recover a surprising identity concerning Euler sums, due to Sitaramachandra Rao and rederived by residue computations in Flajolet & Salvy n. 148 .

• The harmonic average of heights of nodes of a tree (with J.F. MARCKERT and M. YOR).In preparation.

Resource allocation with applications to artificial intelligence.

• Real-time problem solving with contract algorithms (with S. ZILBERSTEIN and F. CHARPILLET ) to appear in IJCAI (1999). (ps.gz 70Ko)

Self organizing data-structures ; the move-to-front rule.

• Processus de Markov transitifs et marches aleatoires sur les groupes. [State-transitive Markov processes and random walks on groups] C.-R.-Acad.-Sci.-Paris-Ser.-I-Math. 312 (1991), no. 3, 291--296.
  extended english version (ps.gz 52Ko)
  We use the symmetry group GX of a Markov process X with state space S to find optimal self-organizing sequential search heuristics, in some cases in which GX acts transitively on S; we also characterize pairs (S,GX) such that S can be endowed with an algebraic structure making X a random walk on the group S, or a Brownian motion on the homogeneous space S. In both cases GX has to act transitively on S.

• Optimality of move-to-front for self-organizing data structures with locality of references. Annals of Applied Probability Vol. 3, No. 4, 1993, 1219-1240 (ps.gz 94Ko)
  extended abstract

Others

Trees.

• Phase transition for parking blocks, Brownian excursion and coalescence (with Guy LOUCHARD).In preparation. (ps.gz 2112Ko)
  No trees in there, but this paper is related with the standard additive coalescent,which is built using the continuum random tree (see D. Aldous or J. Pitman 's Homepages for a lot of material concerning these matters). On the other hand, parking functions are in one to one correspondance with rooted labeled trees (Schutzenberger, Foata and Riordan, Knuth, Flajolet, Viola and Poblete).

• Parking functions, empirical processes and the width of rooted labeled trees. (with J.F. MARCKERT). In preparation. (18p., ps.gz 500Ko)

• The harmonic average of heights of nodes of a tree (with J.F. MARCKERT and M. YOR).In preparation.

• (with S. ALILI) Homogeneization or slow diffusion for random walks with random reflecting barriers, Tech. Rept. No. 27, Prépublications de l'Institut Elie Cartan, URA CNRS n° 750, Université de Nancy 1, (Nancy 1993). (ps.gz 61Ko)
  The main tool in this paper is the relation due to Dwass, between the local time of a random walk on one hand and Galton Watson processes on the other hand. In analysis of algorithm or in combinatorics, this is known as the correspondance between Bernoulli paths and general trees (see Sedgewick and Flajolet, Algorithms).

Brownian motion.

• Phase transition for parking blocks, Brownian excursion and coalescence (with Guy LOUCHARD).In preparation.

• A Stochastically Quasi-Optimal Algorithm (with J.F. MARCKERT and M. YOR) Prepublication de l'Institut Elie Cartan 99.3 (1999). (30 p. ps.gz 159Ko)

  Odlyzko (Search for the maximum of a random walk, Random Struct. Alg. 6 (1995), pp. 275-295) examines the efficiency of various strategies for searching in an unknown environment. He describes an average case quasi-optimal algorithm for the search of the maximum of a n-length symmetric random walk. In this paper, we prove that the same algorithm is also quasi-optimal for the stochastic order and we characterise the limit law of its cost: the limit cost has the same law as an unusual Brownian functional. Computing its moments two ways, we recover a surprising identity concerning Euler sums, due to Sitaramachandra Rao and rederived by residue computations in Flajolet & Salvy n. 148 .

• The harmonic average of heights of nodes of tree (with J.F. MARCKERT and M. YOR).In preparation.

• Slow diffusion for a Brownian motion with random reflecting barriers. Stochastic Process. Appl. 61 (1996), no. 1, 71-83. (ps.gz 45Ko)

• A Kolmogorov criterion and an invariance principle in Besov spaces (with B. BOUFOUSSI, & B. ROYNETTE), (ps.gz 53Ko) Tech. Rept. No. 24, Prépublications de l'Institut Elie Cartan, URA CNRS n° 750, Université de Nancy 1, (Nancy 1993).

Statistical physics.

• (with S. ALILI) Homogeneization or slow diffusion for random walks with random reflecting barriers, Tech. Rept. No. 27, Prépublications de l'Institut Elie Cartan, URA CNRS n° 750, Université de Nancy 1, (Nancy 1993). (ps.gz 61Ko)

• Slow diffusion for a Brownian motion with random reflecting barriers. Stochastic Process. Appl. 61 (1996), no. 1, 71-83. (ps.gz 45Ko)

• Processus associés à l'équation des milieux poreux (with S. BENACHOUR, B. ROYNETTE & P. VALLOIS). Ann. Scuola Norm. Sup. Pisa Cl. Sci. 23 (4), 1997, 793-832.

Random walks on groups.

• Processus de Markov transitifs et marches aleatoires sur les groupes. [State-transitive Markov processes and random walks on groups] C.-R.-Acad.-Sci.-Paris-Ser.-I-Math. 312 (1991), no. 3, 291--296.
  extended english version (same as above) (ps.gz 52Ko)

  
  We use the symmetry group GX of a Markov process X with state space S to find optimal self-organizing sequential search heuristics, in some cases in which GX acts transitively on S; we also characterize pairs (S,GX) such that S can be endowed with an algebraic structure making X a random walk on the group S, or a Brownian motion on the homogeneous space S. In both cases GX has to act transitively on S.

• An optimal random number generator on Zp. Statist.-Probab.-Lett. 7 (1989), no. 4, 307--309. (ps.gz 21Ko)
  On the basis of the random walk model for uniform random number generation considered by F. R. K. Chung, P. Diaconis and R. L. Graham [Ann. Probab. 15 (1987), no. 3, 1148--1165], the author exhibits a transformation f such that the rate of convergence of the law of the random variables Xn † f(Xn-1,an) (mod p) to the uniform law is optimal.

• Convergence d'un produit semi-markovien de matrices et simplicité du spectre de la limite [Convergence of a semi-markovian product of matrices], unpublished.

• Brocot sequences and random walks in SL(2,R) (with LETAC,-Gerard & MORA,-Marianne), in Probability measures on groups, VII (Oberwolfach, 1983), 36--48, Lecture Notes in Math., 1064, Springer, Berlin-New York, 1984.

Engineering.

• On a Stochastic Maintenance Problem with Multiple Constraints (with I. ILINA, M.C. PORTMANN & R. SCHOTT), being revised, to appear in Appl. Stoch. Models & Data Analysis. (ps.gz 37Ko)