گراف جهت‌دار ‎$G$‎ با رئوس ‎$1‎, ‎2‎, ‎\dots‎, ‎n$‎ به این‌صورت ساخته شده است که به ازای هر دو راس ‎$i < j$‎ از ‎$i$‎ به ‎$j$‎ یال داریم. از راس یک شروع می‌کنیم. در هر حرکت یکی از یال‌های خروجی را به شکل تصادفی انتخاب می‌کنیم و آن را طی می‌کنیم. پیچیدگی تابعی ‎($\Theta$)‎ تعداد حرکاتی که لازم است انجام دهیم تا به احتمال حداقل ‎$1/2$‎ به ‎$n$‎ برسیم چند است.

• سوال قبل