In particular, if, then, which exactly says that If we write for the function defined on the non-negative integers such that To denote the two Galton-Watson processes. The main observation is that given two offspring distributions X and Y, such that (which recall means that the means are the same but X is more concentrated) then a number of distributions associated to the Galton-Watson trees for X and Y also satisfy convex ordering relations.Īs a warm-up, and because it was the original genesis, we first study heights. Nonetheless the interpretation via convex ordering feels perfect for a blog post, rather than being lost forever.Ĭonvex ordering for offspring distributions Happily, Serte has recently tied up all the corners of this project concerning the supercritical Galton-Watson forest, and interested readers can find her preprint here on the Arxiv. Also, as far as I understand, the approach outlined in this post didn’t provide strong enough bounds in this particular context. This is the question Serte was asking in our group meeting, in the setting where and the height k has a particular scaling.
What if instead we aren’t trying to obtain a bound uniformly across all offspring distributions with given mean, but instead across a subset of these distributions? How do we determine which distribution in maximises the probability of reaching height k? So neither case is especially interesting for now. įurthermore, if we’re studying all such offspring distributions, this is the best possible upper bound, by considering the offspring distribution given by with probability and zero otherwise.Ģ) In the critical or supercritical case, it is possible that the height is infinite with probability one. Note that in this setting, it is helpful to have in mind the classical notation for a Galton-Watson process, where typically, and is the sum of IID copies of the offspring distribution. I revisited it because of a short but open-ended question about trees posed in our research group meeting by Serte Donderwinkel, one of our high-flying doctoral students.įor a Galton-Watson tree, can one obtain upper bounds in probability on the height of the tree, uniformly across all offspring distributions with mean ? The previous post had been lying almost-complete but dormant for over two years. This blog was recently revived, via a post about convex ordering and its relevance to the problem of sampling with and without replacement that forms part of the potpourri of related results all sometimes referred to as Hoeffding’s inequality.
0 kommentar(er)
