Access Restriction

Author Gardy, Danièle
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract We survey some problems that appear in the analysis of different problems in Computer Science, and show that they can be cast in a common framework (occupancy urn models) and admit an uniform treatment. 1 Introduction Although data structures such as trees and graphs are ubiquitous in Computer Science, and may well be the most frequent models in the analysis of data structures and algorithms, a small but interesting number of problems relative to random allocations can be cast in a common discrete probabilistic framework, known as urn models. Roughly speaking, we have a certain number of urns, into which we throw balls (we may be allowed to remove them), and we are interested in some parameter of the model, such as the total number of balls, or the fraction of urns satisfying some property. When we have a single urn, and balls of different colors, that we may draw from or add to the urn, we have variations on the so-called Polya urn model. Such models have proved useful for analyzing ...
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Publisher Date 1998-01-01