Urnas de Pólya y su conexión con los árboles aleatorios

Abstract

My work deals with Pólya urns and their connections to random trees widely used in computer science in order to structure data or analyse algorithms. In Pólya urns theory we study urns of colored balls with replacement schemes. We draw randomly balls and replace them adding others according to the scheme. Our main aim is to know the asymptotic distribution of each ball color. In random trees theory the main issues are to count the number of leaves, the tree size, etc... which give us an idea of the efficiency of an algorithm. The Pólya urns will help us to get asymptotic distributions of these tree characteristics, they provide an easy, elegant and global way to resolve these problems.