Slumpmässigt rekursivt träd

I sannolikhetsteorin är ett slumpmässigt rekursivt träd ett rotat träd som väljs enhetligt slumpmässigt från de rekursiva träden med ett givet antal hörn.

Definition och generation

I ett rekursivt träd med $n$ hörn, märks hörnen med siffrorna från $1$ till $n$ , och etiketterna måste minska längs vilken väg som helst till trädets rot. Dessa träd är oordnade, i den meningen att det inte finns någon särskiljande ordning av barnen i varje vertex. I ett slumpmässigt rekursivt träd är alla sådana träd lika sannolika.

Alternativt kan ett slumpmässigt rekursivt träd genereras genom att starta från en enda vertex, roten av trädet, märkt ${\displaystyle 1} ,$ och sedan för varje successiv etikett från $2$ till $n$ att välja en slumpmässig vertex med en mindre etikett för att vara dess förälder. Om vart och ett av valen är enhetligt och oberoende av de andra valen, kommer det resulterande trädet att vara ett slumpmässigt rekursivt träd.

Egenskaper

Med hög sannolikhet har den längsta vägen från roten till bladet i ett $n$ -vertex slumpmässigt rekursivt träd längden $e\log n$ . Det maximala antalet barn av någon vertex, dvs grad, i trädet är, med hög sannolikhet, $(1\pm o(1))\log _{ 2}n$ . Det förväntade avståndet för ${\displaystyle k}:$ e vertexet från roten är det ${\displaystyle k}:$ e övertonstalet , från vilket det följer av förväntanslinjäritet att summan av alla rot-till-vertex-väglängder är, med hög sannolikhet, $(1\pm o(1))n\log n$ . Det förväntade antalet löv i trädet är $n/2$ med varians $n/12$ , så med hög sannolikhet är antalet löv $(1\pm o(1))n/2$ .

Ansökningar

Zhang (2015) listar flera tillämpningar av slumpmässiga rekursiva träd i modelleringsfenomen, inklusive sjukdomsspridning, pyramidspel , språkutvecklingen och tillväxten av datornätverk.