Pruned discrete random samples

Abstract

Let Xi, i N, be independent and identically distributed random variables with values in N0. We transform ('prune') the sequence {X1, ⋯ , Xn}, n N, of discrete random samples into a sequence {0, 1, 2, ⋯ , Yn}, n ? N, of contiguous random sets by replacing Xn+1 with Yn+1 if Xn+1 > Yn. We consider the asymptotic behaviour of Yn as n. Applications include path growth in digital search trees and the number of tables in Pitman's Chinese restaurant process if the latter is conditioned on its limit value. © 2013 Applied Probability Trust.