مساله ی پروسه منشعب شونده!

منبع: http://www.cs.nthu.edu.tw/~wkhon/random12/lecture/lecture5.pdf

مساله یه پروسه است که خودش که تموم میشه یه تعداد رندمی از خودش رو شروع می کنه! :))

فرض کنید هر نسخه از این برنامه، n تا نسخه از خودش رو با احتمال p هر کدوم رو شروع می کنه. (دوجمله ای n و p)

تعداد متوسط کپی های ساخته شده توسط یک پروسه چقدره؟

حل:

ایده: (به قول نویسنده اصلی!) نسل ها

در نسل i، پروسه ها توسط پروسه های نسل i-1 ساخته شده اند، متغیر تصادفی yi را تعداد پروسه های نسل i تعریف می کنیم، طبق چیزی که سوال داده توزیع دوجمله ای n و p است.

پس حاصل جمع کل اینها هم یه متغیر با توزیع دوجمله ای است که میانگینش میشه

E(y) = n0p+n1p+n2p+...

ni = تعداد پروسه های نسل i

رابطه ی بین ni ها این طوریه:

ni = np*n(i-1)

(با احتمال شرطی ثابت کرده)

پس اگر np >1 باشه که بینهایت میشه، وگرنه میشه

1/(1-np)

می تونست بگه آزمایش برنولیه:

E(#repeat until success) = 1/p(success)

p(success) = 1-np

p(fail) = np

چون فقط میانگین رو می خواست به دست بیاره، می تونست فقط فکر کنه که np تا پروسه دارن هر بار ساخته میشن!