Asymptotics of the occupancy scheme in a random environment and its applications to tries

Abstract

Consider m copies of an irreducible, aperiodic Markov chain Y taking values in a finite state space. The asymptotics as m tends to infinity, of the first time from which on the trajectories of the m copies differ, have been studied by Szpankowski (1991) in the setting of tries. We use a different approach and model the m trajectories by a variant of the occupancy scheme, where we consider a nested sequence of boxes. This approach will enable us to extend the result to the case when the transition probabilities are random. We moreover Show more