نمونه سوال الگوریتم تصادفی (هارپلد)

https://sarielhp.org/teach/13/b_574_rand_alg/final/practice.pdf

لینک درس: https://sarielhp.org/teach/13/b_574_rand_alg/

نسخه‌ی تغییریافته‌ی جمع‌کننده‌ی کوپن (coupon collector)

http://phillong.info/misc/coupon.pdf
بار دیگر به من اثبات شد هیچی از الگوریتم تصادفی بلد نیستم.
شاید بد نباشد بشینم سوالهای کتاب متوانی را حل کنم. آنجا حساب کردن جمع آن جمله‌های آخر را به عنوان سوال دارد. باز آدم آنها را بلد باشد شاید بتواند این را حل کند.
من هر چی حل کردم رسید به یک جایی که نمی‌شد حسابش کرد.
برای رابطه بازگشتی هم سعی کردم مستقیم مال احتمال را به دست بیارم، در حالی که این مثلاً اومده جمع را در آورده.
سر همین که چرا می‌توانسته امید ریاضی جمع وزنها را برای حساب کردن امید ریاضی آن یکی به کار ببره هم فکر کردم تا فهمیدم چون مخرجش وابسته به آن نبوده ثابت به حساب می‌آمده و از امید ریاضی می‌شده که بیاریمش بیرون.

iccg 2020

http://iccg.aut.ac.ir/