Случайное рекурсивное дерево - Random recursive tree

В теория вероятности, а случайное рекурсивное дерево это укоренившееся дерево выбранный равномерно случайно от рекурсивные деревья с заданным количеством вершин.

Определение и поколение

В рекурсивном дереве с ${ displaystyle n}$ вершины, вершины помечены номерами из ${ displaystyle 1}$ к ${ displaystyle n}$ , и метки должны уменьшаться на любом пути к корню дерева. Эти деревья неупорядочены в том смысле, что нет определенного порядка дочерних элементов каждой вершины. В случайном рекурсивном дереве все такие деревья равновероятны.

В качестве альтернативы случайное рекурсивное дерево можно сгенерировать, начав с единственной вершины, корня дерева, помеченной ${ displaystyle 1}$ , а затем для каждой последующей метки из ${ displaystyle 2}$ к ${ displaystyle n}$ выбор случайной вершины с меньшей меткой в качестве родительской. Если каждый из вариантов является однородным и независимым от других вариантов, результирующее дерево будет случайным рекурсивным деревом.

Характеристики

С большой долей вероятности самый длинный путь от корня до листа ${ displaystyle n}$ -вершинное случайное рекурсивное дерево имеет длину ${ Displaystyle е журнал п}$ .^[1]Максимальное количество потомков любой вершины, то есть степени, в дереве с большой вероятностью равно ${ Displaystyle (1 pm о (1)) журнал _ {2} п}$ .^[2]В ожидал расстояние до ${ displaystyle k}$ -й вершиной от корня является ${ displaystyle k}$ th номер гармоники, откуда следует линейность ожидания что сумма всех длин пути от корня до вершины с большой вероятностью ${ Displaystyle (1 pm о (1)) п журнал п}$ .^[3]Ожидаемое количество листьев на дереве ${ displaystyle n / 2}$ с отклонение ${ displaystyle n / 12}$ , поэтому с большой вероятностью количество листьев равно ${ Displaystyle (1 pm о (1)) п / 2}$ .^[4]

Приложения

Чжан (2015) перечисляет несколько применений случайных рекурсивных деревьев для моделирования явлений, включая распространение болезней, схемы пирамиды, эволюция языков и рост компьютерных сетей.^[4]

Рекомендации

^ Питтель, Борис (1994), "Замечание о высоте случайных рекурсивных деревьев и случайных $м$ -арочные деревья поиска », Случайные структуры и алгоритмы, 5 (2): 337–347, Дои:10.1002 / RSA.3240050207, МИСТЕР 1262983
^ Го, Уильям; Шмутц, Эрик (2002), "Предельное распределение для максимальной степени случайного рекурсивного дерева", Журнал вычислительной и прикладной математики, 142 (1): 61–82, Дои:10.1016 / S0377-0427 (01) 00460-5, МИСТЕР 1910519
^ Добров, Роберт П .; Заливка, Джеймс Аллен (1999), "Общая длина пути для случайных рекурсивных деревьев", Комбинаторика, теория вероятностей и вычисления, 8 (4): 317–333, Дои:10.1017 / S0963548399003855, МИСТЕР 1723646
^ ^а ^б Чжан, Яжэ (2015), «О количестве листьев в случайном рекурсивном дереве», Бразильский журнал вероятностей и статистики, 29 (4): 897–908, Дои:10.1214 / 14-BJPS252, МИСТЕР 3397399

[p-1] Питтель, Борис (1994), "Замечание о высоте случайных рекурсивных деревьев и случайных $м$ -арочные деревья поиска », Случайные структуры и алгоритмы, 5 (2): 337–347, Дои:10.1002 / RSA.3240050207, МИСТЕР 1262983

[gs-2] Го, Уильям; Шмутц, Эрик (2002), "Предельное распределение для максимальной степени случайного рекурсивного дерева", Журнал вычислительной и прикладной математики, 142 (1): 61–82, Дои:10.1016 / S0377-0427 (01) 00460-5, МИСТЕР 1910519

[df-3] Добров, Роберт П .; Заливка, Джеймс Аллен (1999), "Общая длина пути для случайных рекурсивных деревьев", Комбинаторика, теория вероятностей и вычисления, 8 (4): 317–333, Дои:10.1017 / S0963548399003855, МИСТЕР 1723646

[z-4] а ^б Чжан, Яжэ (2015), «О количестве листьев в случайном рекурсивном дереве», Бразильский журнал вероятностей и статистики, 29 (4): 897–908, Дои:10.1214 / 14-BJPS252, МИСТЕР 3397399

[1]

[2]

[3]

[4]