ランダム再帰木

確率論において、ランダム再帰木とは、与えられた数の頂点を持つ再帰木の中から一様にランダムに選ばれた根付き木のことである。

再帰ツリーでは${\displaystyle n}$頂点、頂点には番号が付けられています。${\displaystyle 1}$に${\displaystyle n}$また、ラベルは木の根までのどの経路でも減少していく必要があります。これらの木は、各頂点の子に明確な順序付けがないという意味で、順序付けされていません。ランダム再帰木では、このような木はすべて同じ確率で発生します。

あるいは、単一の頂点（木の根）から始めて、ラベル付けされたランダムな再帰木を生成することもできます。${\displaystyle 1}$そして、各ラベルについて${\displaystyle 2}$に${\displaystyle n}$ラベルの小さいランダムな頂点を親として選択します。それぞれの選択が均一で、他の選択とは独立している場合、結果として得られるツリーはランダム再帰ツリーになります。

高い確率で、${\displaystyle n}$-頂点ランダム再帰木の長さは${\displaystyle e\log n}$[ ^{1 ]} ツリー内の任意の頂点の子の最大数、つまり次数は、高い確率で^、${\displaystyle (1\pm o(1))\log _{2}n}$[ ^{2 ]} 予想^される距離${\displaystyle k}$根から数番目の頂点は${\displaystyle k}$番目の調和数から、期待の線形性により、すべての根から頂点への経路長の合計は、高い確率で次のようになることがわかります。${\displaystyle (1\pm o(1))n\log n}$[ ^{3 ]} 木の葉の期待数^は${\displaystyle n/2}$分散付き${\displaystyle n/12}$葉の数は高い確率で${\displaystyle (1\pm o(1))n/2}$[ ^{4 ]​}

Zhang (2015)は、病気の蔓延、ねずみ講、言語の進化、コンピュータネットワークの成長などの現象をモデル化する際のランダム再帰ツリーのいくつかの応用例を挙げている。 ^{[ 4 ]}