Carry propagation

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

Helmut asks about problems related to the analysis of carry propagation
(Knuth, 1978). There is a nice general result by Xavier Gourdon along
these lines.

	First consider the problem of the longest run of 1's in a random string
that starts with a 0. By splitting a string before each zero, we see
that it is a sequence of blocks of the form 011...1. The analysis of
Knuth may be rephrased as that of the largest block.

	This suggests a generalization. Take any sequence of basic objects
called "blocks" and ask for the statistics of the largest block.
Examples are the largest root subtree in a random plane tree, 
the largest tree in a random mapping, the largest summand in a random
integer composition, etc.

	We are then dealing with restrictions of a generating function of the
form F(z)=1/(1-G(z)). Xavier's result says that the size of the largest
G-block in a random F-sequence is logarithmic (on average, with high
probability) whenever G(z) reaches the value 1 on the positive real axis
before it becomes singular. (This is called, after Michele Soria, a
supercritical sequence schema). Xavier also has results about other
cases and about set constructions. Questions like the size of the
largest cycle in a random permutation (of Shepp & LLoyd fame), largest
degree of an irreducible factor in  arandom polynomial, etc.




-- 
---------------------------------------------------
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
---------------------------------------------------