Motivation
Galton Waston Tree is a basic model in probability theory and sometimes we call it branching process. This model can be taught in the introductory course of probability in Polytechnique during Tronc Commun, but its background is so profound that we can find it in so much domain in applied mathematics and pure mathematics, some examples for the former is the biological process like the gene and, however, some example for the later is the recent breakthrough in maths and physics like random mapping theory. In fact, we start from the BGW model and develop the continuous random tree, a continuous version as the convergence of the tree, and at last is the most fashionable object.As I have passion to continue the study in this field, I will devote a series of blog in this domain. This first introduction comes from the talk given by Igor Kortchmeski last week.
Definition
The BGM process is can be defined as a tree. In each generation, the parent gives birth to its children and the law of production follows a random variable uniformly and independently. Usually we study the situation that the expectation of the production is finite and it is logical in reality.The first problem comes from the biology: when the population will distinct? The answer is that when the expectation of production is less than 1, the population will die necessarily but even though this expectation is larger than 1, there is still a probability that the population die out. Then precise study of this problem relied the study by the generated function, who is in form of iterations.
Simulation of uniform tree
The second problem is how many generated tree without label? A famous formula of Cayley is n^(n-2). This can also be solved by BGW model and in fact our BGW model can simulate this process given certain probability of production. If the probability of production is like a geometry law, this gives a uniform ordered and root fixed tree, but if it follow the law of Poisson, it is the simulation of uniform non-labelled but root fixed tree. The technique detail will be given in the next section.Characterization
In the lecture, Igor introduced two method to code the tree: one by the function of contour and the other by the random walk. The first one, each step is the height of the vertex in the tree in order of the depth first search and in the second one, we assign each move the law of production. Then the process of production becomes the process of random walk. This is nature since we can always consider the number of population in a given and then the number denote the random walk. The second method by random walk has incredible power: since we understand well the random walk and it can calculate many property like the number of non-labelled tree, which we have introduced int the previous section.
Some further study like the asymptotic growth of number of tree can be approximated by the local limit theorem, a extended version of central limit theorem. Until here we have presented almost all the content in this lecture and I will write some notes by simple description of these beautiful maths.
