论文标题
到达随机树边界的距离
The distance to the border of a random tree
论文作者
论文摘要
鉴于Galton-Watson的过程的总后代等于$ n $，我们研究了条件条件的Galton-Watson过程的渐近概率，即与$ N \ rightarrow \ rightarrow \ infty $相比，与边界更大或等于$ k $的边界的距离。 Rényi和Szekeres为Cayley Trees，De Bruijn，Knuth和Rice for Flajolet，Gao，Gao，Odlyzko和Richmond供二元树解决了一个类似于这一问题的问题。从某种意义上说，到边界的距离是双重的。这些距离中的第一个是从根到叶子的距离的最小值。第二个是从根到叶子的最大距离。这是两个极端的互补案例。
Given a Galton-Watson process conditioned to have total progeny equal to $n$, we study the asymptotic probability that this conditioned Galton-Watson process has distance to the border bigger or equal than $k$, as the number of nodes $n \rightarrow \infty$. A problem which is akin to this one was solved by Rényi and Szekeres for Cayley trees, de Bruijn, Knuth, and Rice for plane trees and Flajolet, Gao, Odlyzko, and Richmond for binary trees. The distance to the border is dual, in a certain sense, to the height. The first of these distances is the minimum of the distances from the root to the leaves. The second is the maximum of the distances from the root to the leaves. These are two extreme complementary cases.
