شجرة تكرارية عشوائية

في نظرية الاحتمالات ، الشجرة المتكررة العشوائية هي شجرة جذرية يتم اختيارها بشكل عشوائي منتظم من الأشجار المتكررة ذات عدد معين من الرؤوس.

في شجرة متكررة مع${\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}$الرأس رقم 1 من الجذر هو${\displaystyle k}$العدد التوافقي رقم 1 ، والذي يتبع منه، من خلال خطية التوقع، أن مجموع أطوال جميع المسارات من الجذر إلى الرأس هو، باحتمالية عالية،${\displaystyle (1\pm o(1))n\log n}$[ ^{3 ] العدد المتوقع} لأوراق الشجرة هو${\displaystyle n/2}$مع التباين${\displaystyle n/12}$لذا، باحتمالية عالية، يكون عدد الأوراق هو${\displaystyle (1\pm o(1))n/2}$[ ^{4 ]​}

يسرد تشانغ (2015) العديد من تطبيقات الأشجار المتكررة العشوائية في نمذجة الظواهر بما في ذلك انتشار الأمراض، ومخططات التسويق الهرمي ، وتطور اللغات، ونمو شبكات الحاسوب. ^{[ 4 ]}