Lavault <Christian.Lavault@lipn.univ-paris13.fr>
reply-to	Christian.Lavault@lipn.univ-paris13.fr
to	"\"Gérard H. E. Duchamp\"" <gheduchamp@gmail.com>
date	21 February 2009 18:27
subject	Re: Pas loin de chez nous et de bonne tenue
mailed-by	lipn.univ-paris13.fr
	
hide details 18:27
	
	
Reply
	
	

        J'avais oublié de te préciser que, bien évidemment, je peux t'envoyer titre et résumé en anglais.


    Oui, je veux bien, cela va me faciliter les choses.

    Amitiés,
    Gérard


--
Alors avec un peu de retard :

Title:
"Asymptotic analysis and convergence of some leader election algorithms"

Abstract:
We start with a set of $n$ players. With some probability $P(n,k)$,
we kill $n-k$ players; the other ones stay alive, and we repeat with
them. What is the distribution of the number $X_n$ of rounds before
getting only one player?  We present a probabilistic analysis of this
very general algorithm (expectation and moments of $X_n$), under some
conditions on the probability distributions $P(n,k)$ (if any),
including stochastic monotonicity and the assumption that roughly
a fixed proportion of the players survive in each round.
Applications of the general result include asymptotic analysis
of leader election algorithms where players are eliminated by
independent coin tosses.


Amitiés,
Christian