Preprint C1444/2019
Topics in discrete probability: Analysis of the past and the future
Alan Anderson da Silva Pereira
Keywords: Random Trees; Chinese Restaurant Process; Discrete Probability

This thesis is concerned with problems about discrete structures that change with time. We study two problems in discrete models: random trees with uniform attachment and concentration in random partitions.

The first problem is about Archaeology of Random Tree with Uniform Attachment. Given an initial tree (seed tree) let us attach at each time a new vertex to a randomly chosen vertex of the current tree. If we let time grow until a big value n, and look the tree after this process, can we decide which vertices were in the seed tree? This is analyzed for three possible seed trees: a path, a star and a random tree. Techniques of Polya Urns and concentration inequalities were the main ingredients of the solution of these problems.

The second problem is about Generalized Chinese Restaurant Process: suppose we have a restaurant with infinitely many tables. At each time a new costumer enters in the restaurant and sits a table. The probability of choosing some previously occupied table depends on the number of costumers at the table and of some parameters, and the probability of choose a new table is the complementary probability. We study, in terms of the parameters, the growth of the number of occupied tables and the number of tables with k costumers. We showed that the the normalized number of occupied tables and the number of table with a fixed number of costumers concentrates near a convenient random variable.