Discrete Mathematics & Theoretical Computer Science, Vol 12, No 2 (2010)

Font Size:  Small  Medium  Large

Asymptotic results for silent elimination

Guy Louchard, Helmut Prodinger


Following the model of Bondesson, Nilsson, and Wikstrand, we consider randomly filled urns, where the probability of falling into urn i is the geometric probability (1-q)qi-1. Assuming n independent random entries, and a fixed parameter k, the interest is in the following parameters: Let T be the smallest index, such that urn T is non-empty, but the following k are empty, then: XT= number of balls in urn T, ST= number of balls in urns with index larger than T, and finally T itself.

Full Text: PDF PostScript