قدم زدن تصادفی: گرافهای نامتناهی و قدم‌زدن چندگانه

گفته یک آدم مست ممکنه راهش را پیدا کنه، اما یک پرنده‌ی مست ممکنه هیچ وقت راهش را پیدا نکنه!

https://www.cs.bris.ac.uk/Research/Algorithms/events/BAD16/Slides/sauerwald.pdf

یک کران پایین با استفاده از مسئله‌ی جمع کردن کوپن داده (باید از همه‌ی انواع کوپن داشته باشید، باید چند تا بخرید تا با احتمال بالایی برنده بشوید؟):

https://en.wikipedia.org/wiki/Coupon_collector%27s_problem

ثابت کرده که برای گسترگرافها کمتره. (البته الآن مقاله‌ای که من ارائه می‌دهم برای یک گسترگرافه و ثابت کرده لگاریتم n تقسیم بر توان ۲ گسترش گراف است.)

چیزی که انگار هیچ کس در نظر نگرفته این است که گذشتن همزمان چند نفر از یک رأس کار خوبی نیست. البته این به اسم intersection time ازش حرف زده.