تحلیل احتمالاتی و الگوریتم‌های تصادفی: توضیح مسئله استخدام

چرا تصادف وارد تحلیل الگوریتم می‌شود

زمان‌های اجرای بدترین‌حالت، بهترین‌حالت، و حالت‌میانگین که پیش‌تر در این مجموعه بحث شد، همگی فرض می‌کنند خود الگوریتم به‌طور قطعی رفتار می‌کند، و هر تغییری صرفاً از ورودی می‌آید. وضعیت متفاوتی وقتی پیش می‌آید که یا توزیع ورودی ناشناخته باشد یا یک الگوریتم عمداً انتخاب‌های تصادفی در حین اجرای خودش انجام دهد. هر دو وضعیت به ابزارهای Probabilistic Analysis (تحلیل احتمالاتی) نیاز دارند.

مسئله استخدام: یک مثال انگیزاننده

یک شرکت را در نظر بگیرید که کاندیدها را یکی‌یکی برای یک موقعیت مصاحبه می‌کند، همیشه بهترین کاندید فعلی که تاکنون دیده استخدام می‌کند و استخدام‌شده قبلی را اخراج می‌کند. هر مصاحبه هزینه کمی دارد، اما هر استخدام هزینه به‌طور قابل‌توجهی بیشتری دارد، چون شامل کاغذبازی، آموزش، و مزایای پایان‌کار برای فردی است که جایگزین می‌شود. پرسش این است: هزینه کل استخدام مورد انتظار در سراسر کل فرآیند چقدر است؟

HIRE-ASSISTANT(n):
  best = کاندید 0 (یک جانگه‌دار، رتبه‌بندی‌شده بدترین)
  برای i = 1 تا n:
      کاندید i را مصاحبه کن
      اگر کاندید i از best بهتر باشد:
          best = کاندید i
          کاندید i را استخدام کن

اگر کاندیدها به بدترین ترتیب ممکن برسند — از قبل از بدترین به بهترین مرتب‌شده — هر کاندید تکی استخدام می‌شود، که به n استخدام منجر می‌شود، یک بدترین‌حالت پرهزینه. اما اگر ترتیب کاندیدها تصادفی باشد، به‌طور میانگین استخدام‌های بسیار کمتری مورد انتظار است، چون یک ترتیب ورود تصادفی بعید می‌کند که بسیاری کاندید متوالی هرکدام یک رکورد جدید بزنند.

دو رویکرد برای مدیریت ترتیب ورودی‌ها

دو راه متمایز برای استدلال درباره این تصادف وجود دارد، و مهم است آن‌ها را با هم اشتباه نگیریم.

• Probabilistic Analysis of a Deterministic Algorithm (تحلیل احتمالاتی یک الگوریتم قطعی): فرض کن خود ورودی از یک توزیع احتمالی می‌آید (مانند یک ترتیب یکنواخت تصادفی از کاندیدها)، و زمان اجرای مورد انتظار یک الگوریتم ثابت و غیرتصادفی را روی آن توزیع ورودی تحلیل کن.
• Randomized Algorithms (الگوریتم‌های تصادفی): خود الگوریتم در حین اجرا انتخاب‌های تصادفی می‌کند (مانند به‌طور تصادفی به‌هم‌ریختن ترتیب کاندیدها پیش از پردازش آن‌ها، صرف‌نظر از ترتیبی که واقعاً رسیده‌اند)، که کارایی مورد انتظار خوب را برای هر ورودی تضمین می‌کند، چون تصادف از الگوریتم می‌آید نه یک فرض درباره ورودی.

رویکرد دوم معمولاً در عمل قدرتمندتر و قابل‌اعتمادتر است، چون هر وابستگی به فرضیات درباره اینکه ورودی‌ها در دنیای واقعی چگونه توزیع شده‌اند را حذف می‌کند، که ممکن است برقرار نباشد. یک Randomized Algorithm برای مسئله استخدام صرفاً کاندیدها را به‌طور تصادفی جایگشت می‌کند پیش از اجرای همان رویه، و همان هزینه مورد انتظار خوب را صرف‌نظر از ترتیب اصلی ورودی تضمین می‌کند.

متغیرهای تصادفی نشانگر: یک ابزار تحلیلی قدرتمند

محاسبه مستقیم یک مقدار مورد انتظار می‌تواند وقتی بسیاری رویداد متعامل درگیر باشند پیچیده باشد. Indicator Random Variables (متغیرهای تصادفی نشانگر) تکنیکی زیبا فراهم می‌کنند که چنین محاسباتی را به‌طور چشمگیری ساده می‌کند، به‌ویژه وقتی با خطی‌بودن امید ریاضی ترکیب شود.

برای یک رویداد A، متغیر تصادفی نشانگر را تعریف کن:

I{A} = 1  اگر A رخ دهد
I{A} = 0  اگر A رخ ندهد

ویژگی کلیدی: E[I{A}] = Pr{A}

مقدار مورد انتظار یک متغیر نشانگر صرفاً برابر با احتمال رویدادی است که نشان می‌دهد. این وقتی با Linearity of Expectation (خطی‌بودن امید ریاضی) ترکیب شود قدرتمند می‌شود، که بیان می‌کند مقدار مورد انتظار مجموع متغیرهای تصادفی برابر با مجموع مقادیر مورد انتظارشان است، صرف‌نظر از اینکه متغیرها مستقل باشند یا نه.

E[X1 + X2 + ... + Xn] = E[X1] + E[X2] + ... + E[Xn]

این حتی وقتی Xi ها مستقل نباشند برقرار است —
یک واقعیت حیاتی و اغلب شگفت‌آور

به‌کارگیری متغیرهای نشانگر روی مسئله استخدام

فرض کن Xi متغیر تصادفی نشانگر برای رویداد استخدام کاندید i باشد. تعداد کل استخدام‌ها X = X1 + X2 + ... + Xn است. با خطی‌بودن امید ریاضی:

E[X] = E[X1] + E[X2] + ... + E[Xn]
     = Σ Pr{کاندید i استخدام می‌شود}

کاندید i دقیقاً وقتی استخدام می‌شود که کاندید i بهترین در میان i کاندید اول دیده‌شده باشد. اگر کاندیدها به ترتیب یکنواخت تصادفی برسند، کاندید i به‌طور برابر احتمال دارد بهترین، دومین‌بهترین، یا هر رتبه‌ای در میان i کاندید اول باشد، پس:

Pr{کاندید i استخدام می‌شود} = 1/i

بنابراین:
E[X] = Σ (i=1 تا n) 1/i = H(n)

این سری هارمونیک است، و H(n) = Θ(ln n)

این نتیجه قابل‌توجه نشان می‌دهد، با وجود n کاندید، تعداد استخدام‌های مورد انتظار فقط به‌صورت لگاریتمی با n رشد می‌کند، بهبود چشمگیری نسبت به سناریوی بدترین‌حالت n استخدام. این محاسبه، که با متغیرهای نشانگر ساده شد، با استفاده از محاسبات احتمال مستقیم شامل توزیع‌های مشترک به‌طور قابل‌توجهی پیچیده‌تر خواهد بود.

چرا این تکنیک این‌قدر گسترده تعمیم می‌یابد

تکنیک متغیر تصادفی نشانگر مخصوص مسئله استخدام نیست؛ یک ابزار عمومی قابل‌اعمال هروقت که یک کمیت مورد علاقه بتواند به‌صورت مجموعی از پیامدهای ساده‌تر صفر-یا-یک بیان شود، حتی وقتی آن پیامدها با هم مرتبط باشند. این آن را به یکی از گسترده‌ترین تکنیک‌های مفید در تحلیل احتمالاتی الگوریتم‌ها تبدیل می‌کند، و در سراسر موضوعات بعدی این مجموعه هرجا که زمان اجرای مورد انتظار باید محاسبه شود دوباره ظاهر می‌شود.

چرا تصادفی‌سازی برای طراحی الگوریتم دنیای واقعی اهمیت دارد

الگوریتم‌های تصادفی در سراسر علوم کامپیوتر استفاده می‌شوند به‌طور خاص چون می‌توانند کارایی مورد انتظار خوب را بدون نیاز به هیچ فرضی درباره توزیع ورودی‌های دنیای واقعی تضمین کنند، و در برابر ورودی‌های خصمانه یا به‌طور غیرمعمول ساختاریافته که در غیر این صورت می‌توانستند بدترین‌حالت یک الگوریتم را فعال کنند محافظت می‌کنند. یک مثال برجسته، که بعداً در این مجموعه به‌طور عمیق بررسی می‌شود، quicksort تصادفی است، جایی که به‌هم‌ریختن تصادفی ورودی پیش از مرتب‌سازی در برابر ترتیب‌های ورودی خاصی که در غیر این صورت بدترین‌حالت درجه‌دوم quicksort را فعال می‌کردند محافظت می‌کند.