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.
翻译:我们通过在线建议系统研究随机森林的组合。 森林的顶端以整数标注。 每个非正整整数$le 0 美元是树根。 以正正整数为标签的顶端依次附在正整数 $\ ge 1 美元上, 因此顶顶数的母体是 $n- ⁇ n 美元, 美元是 i. d.\ 随机变量, 以美元计值。 我们研究由此形成的森林的若干特征。 特别是, 我们为预期的树木大小、 森林树木数量、 树叶数量、 最大程度和森林的高度设定了界限。 我们显示, 对于正整数美元的所有分布, 森林含有最多一棵无限的树, 几乎可以肯定。 如果 $_ mathbb E}n < i. d. d.\ 随机变量以美元计值计值, 那么剩下的树木的总数是独一无二的, 如果 $xmab $ En2, 那么n\\ fin 树是固定的。