Random Sieves and Generalized Leader-election Procedures

Abstract

A random sieve of the set of positive integers N is an infinite sequence of nested subsets N = S0 ⊃ S1 ⊃ S2 ⊃ · · · such that Sk is obtained from Sk−1 by removing elements of Sk−1 with the indices outside Rk and enumerating the remaining elements in the increasing order. Here R1 , R2 , . . . is a sequence of independent copies of an infinite random set R ⊂ N. We prove general limit theorems for Sn and related functionals, as n → ∞.