В теории вероятностей , случайное рекурсивное дерево является корневым дерево выбирается случайно равномерно из рекурсивных дерев с заданным числом вершин.
Определение и поколение
В рекурсивном дереве с вершины, вершины помечены номерами из к , а метки должны уменьшаться на любом пути к корню дерева. Эти деревья неупорядочены в том смысле, что нет определенного порядка дочерних элементов каждой вершины. В случайном рекурсивном дереве все такие деревья равновероятны.
В качестве альтернативы случайное рекурсивное дерево можно сгенерировать, начав с единственной вершины, корня дерева, помеченной , а затем для каждой последующей метки из к выбор случайной вершины с меньшей меткой в качестве родительской. Если каждый из вариантов является однородным и независимым от других вариантов, результирующее дерево будет случайным рекурсивным деревом.
Характеристики
С большой долей вероятности самый длинный путь от корня до листа -вершинное случайное рекурсивное дерево имеет длину . [1] Максимальное количество потомков любой вершины, т. Е. Степени, в дереве, с большой вероятностью,. [2] ожидается , расстояние от-й вершиной от корня является й номер гармоники , из которой следует , по линейности ожидания , что сумма всех длин путей корень до вершины-есть, с высокой вероятностью,. [3] Ожидаемое количество листьев на дереве:с отклонением , поэтому с большой вероятностью количество листьев равно . [4]
Приложения
Чжан (2015) перечисляет несколько применений случайных рекурсивных деревьев для моделирования явлений, включая распространение болезней, пирамидальные схемы , эволюцию языков и рост компьютерных сетей. [4]
Рекомендации
- ^ Pittel, Б. (1994), "Обратите внимание на высотах случайных рекурсивных деревьев и случайных м -ичный деревьев поиска", Случайные структуры и алгоритмы , 5 (2): 337-347, DOI : 10.1002 / rsa.3240050207 , МР 1262983
- ^ Го, Уильям; Шмутц, Эрик (2002), "Предельное распределение максимальной степени случайного рекурсивного дерева", Журнал вычислительной и прикладной математики , 142 (1): 61-82, DOI : 10.1016 / S0377-0427 (01) 00460-5 , MR 1910519
- ^ Добров, Роберт П .; Заливка, Джеймс Аллен (1999), "Общая длина пути для случайных рекурсивных деревьев", Комбинаторика, Вероятность и вычисления , 8 (4): 317-333, DOI : 10,1017 / S0963548399003855 , МР 1723646
- ^ а б Чжан, Yazhe (2015), "О количестве листьев в случайном рекурсивном дерево", бразильский журнал вероятностей и статистика , 29 (4): 897-908, DOI : 10,1214 / 14-BJPS252 , МР 3397399