Some combinatorial games on rooted multi-type Galton-Watson trees

Abstract: In a rooted multi-type Galton-Watson branching process, the root is assigned a colour from a finite set $\Sigma$ of colours according to some probability distribution P, and a vertex of the tree, conditioned on its colour $\sigma \in \Sigma$, gives birth to offspring according to some probability distribution $\chi_{\sigma}$ on $\mathbb{N}_{0}^{\Sigma}$. In particular, one may consider $\Sigma = \{{\rm red}, {\rm blue}\}$ and the resulting random tree, denoted T, can be viewed as a directed random graph if each edge is attributed a direction from parent to child. I consider the normal, misere and escape games on T, each played between P1 and P2, with P1 being allowed to move the token only along monochromatic directed edges and P2 being allowed to move the token only along non-monochromatic directed edges. I then investigate the probabilities of win, loss and (where pertinent) draw of each player as fixed points of distributional recursions, establish inequalities between win / loss / draw probabilities of the players across different games, seek possible phase transitions in win / loss / draw probabilities as the parameters involved in the offspring distributions are made to vary, study expected durations of the games etc.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).