زمان الگوریتم تصادفی

زمان الگوریتم تصادفی خودش یک متغیر تصادفی است که به انتخاب تصادفی وابسته است. در نتیجه زمانی که حساب می کنیم، متوسط بدترین زمان بین انتخابهای تصادفی مختلف است. (ما هیچ فرضی روی ورودی و تصادفی بودن آن نمی کنیم)

قضیه Yao's minimax: بدترین ورودی (worst case) را در نظر بگیرید. بهترین الگوریتم قطعی روی این ورودی جوابش همیشه از هر الگوریتم تصادفی بهتره.

این یک کران پایین برای زمان الگوریتم تصادفی میده. برای به دست آوردن این کران یک ورودی بد پیدا می کنیم (کرانی که پیدا می کنیم به بد بودن این ورودی بستگی داره) و ثابت می کنیم که هیچ الگوریتم قطعی نیست که بتونه برای این خوب کار کنه.

همین قضیه از دید نظریه بازی ها: یک بازی جمع صفر بین آلیس و باب، که آلیس هر بار یه الگوریتم قطعی رو بر می داره و باب یه ورودی رو بر می داره و هزینه هم هزینه ی اجرای الگوریتم با اون ورودیه. پس هر الگوریتم تصادفی یک حرکت آلیس میشه. طبق قضیه minimax ون نیومن، باب حتما یه حرکت تصادفی داره که حداقل به خوبی وقتی که آلیس فقط یک الگوریتم رو انجام بده، کار کنه. (یعنی باب می تونه ورودی رو انتخاب کنه که هیچ الگوریتم قطعی نتونه بهتر از این روی این ورودی جواب بده.)

برای سوال حل کردن با این باید به سری ورودی رو با یه احتمالی مشخص کنیم، بعد مینیمم زمان (یا هر هزینه ی دیگه ای که بود) رو به دست میاریم، بعد نتیجه می گیریم که هیچ الگوریتم تصادفی نمی تونه از این بهتر باشه. (برای هر ورودی ای!)