Случайное рекурсивное дерево

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

Определение и генерация

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

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

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

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

Приложения

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

Ссылки

^ Питтель, Борис (1994), «Примечание о высотах случайных рекурсивных деревьев и случайных $m$ -арных деревьев поиска», Random Structures & Algorithms , 5 (2): 337–347, doi : 10.1002/rsa.3240050207 , MR 1262983
^ Гох, Уильям; Шмутц, Эрик (2002), «Предельное распределение максимальной степени случайного рекурсивного дерева», Журнал вычислительной и прикладной математики , 142 (1): 61–82, Бибкод : 2002JCoAM.142...61G , doi : 10.1016 /S0377-0427(01)00460-5 , МР 1910519
^ Доброу, Роберт П.; Филл, Джеймс Аллен (1999), «Общая длина пути для случайных рекурсивных деревьев», Combinatorics, Probability and Computing , 8 (4): 317–333, doi : 10.1017/S0963548399003855 , MR 1723646 , S2CID 40574756
^ Jump up to: ^а ^б Чжан, Яже (2015), «О количестве листьев в случайном рекурсивном дереве», Бразильский журнал вероятностей и статистики , 29 (4): 897–908, doi : 10.1214/14-BJPS252 , MR 3397399

[p-1] Питтель, Борис (1994), «Примечание о высотах случайных рекурсивных деревьев и случайных $m$ -арных деревьев поиска», Random Structures & Algorithms , 5 (2): 337–347, doi : 10.1002/rsa.3240050207 , MR 1262983

[gs-2] Гох, Уильям; Шмутц, Эрик (2002), «Предельное распределение максимальной степени случайного рекурсивного дерева», Журнал вычислительной и прикладной математики , 142 (1): 61–82, Бибкод : 2002JCoAM.142...61G , doi : 10.1016 /S0377-0427(01)00460-5 , МР 1910519

[df-3] Доброу, Роберт П.; Филл, Джеймс Аллен (1999), «Общая длина пути для случайных рекурсивных деревьев», Combinatorics, Probability and Computing , 8 (4): 317–333, doi : 10.1017/S0963548399003855 , MR 1723646 , S2CID 40574756

[z-4] Jump up to: ^а ^б Чжан, Яже (2015), «О количестве листьев в случайном рекурсивном дереве», Бразильский журнал вероятностей и статистики , 29 (4): 897–908, doi : 10.1214/14-BJPS252 , MR 3397399

[1]

[2]

[3]

[4]