论文标题
减法随机森林
Subtractive random forests
论文作者
论文摘要
在在线推荐系统的激励下，我们研究了一个随机森林家庭。森林的顶点被整数标记。每个非阳性整数$ i \ le 0 $都是树的根。由正整数标记的顶点$ n \ ge 1 $依次连接，以使顶点$ n $的父级是$ n-z_n $，其中$ z_n $是i.i.d. \ \随机变量，以$ \ mathbb n $为单位。我们研究了由此产生的随机森林的几个特征。特别是，我们建立了预期的树大小的范围，森林中的树木数，叶子的数量，最高程度和森林的高度。我们表明，对于$ z_n $的所有分布，森林最多都包含一棵无限的树。如果$ {\ mathbb e} z_n <\ infty $，则有一个独特的无限树，剩余树的总大小是有限的，如果$ {\ mathbb e} z_n^2 <\ infty $，则具有有限的期望值。如果$ {\ mathbb e} z_n = \ infty $，那么几乎肯定所有的树都是有限的。
Motivated by online recommendation systems, we study a family of random forests. The vertices of the forest are labeled by integers. Each non-positive integer $i\le 0$ is the root of a tree. Vertices labeled by positive integers $n \ge 1$ are attached sequentially such that the parent of vertex $n$ is $n-Z_n$, where the $Z_n$ are i.i.d.\ random variables taking values in $\mathbb N$. We study several characteristics of the resulting random forest. In particular, we establish bounds for the expected tree sizes, the number of trees in the forest, the number of leaves, the maximum degree, and the height of the forest. We show that for all distributions of the $Z_n$, the forest contains at most one infinite tree, almost surely. If ${\mathbb E} Z_n < \infty$, then there is a unique infinite tree and the total size of the remaining trees is finite, with finite expected value if ${\mathbb E}Z_n^2 < \infty$. If ${\mathbb E} Z_n = \infty$ then almost surely all trees are finite.
