<h2>Why Randomness Enters Algorithm Analysis</h2> <p>The worst-case, best-case, and average-case running times discussed earlier in this series all assume the algorithm itself behaves deterministically, and any variation comes purely from the input. A different situation arises when either the input distribution is unknown or an algorithm deliberately makes random choices during its own execution. Both situations require the tools of <code>Probabilistic Analysis</code>.</p> <h2>The Hiring Problem: A Motivating Example</h2> <p>Consider a company interviewing candidates one at a time for a position, always hiring the current best candidate seen so far and firing the previous hire. Each interview costs a small amount, but each hire costs significantly more, since it involves paperwork, onboarding, and severance for the person being replaced. The question is: what is the expected total hiring cost across the entire process?</p> <pre class="code-block"><code>HIRE-ASSISTANT(n): best = candidate 0 (a placeholder, ranked worst) for i = 1 to n: interview candidate i if candidate i is better than best: best = candidate i hire candidate i</code></pre><br> <p>If candidates arrive in the worst possible order — already sorted from worst to best — every single candidate is hired, resulting in <code>n</code> hires, a costly worst case. But if the order of candidates is random, far fewer hires are expected on average, since a random arrival order makes it unlikely that many consecutive candidates each set a new record.</p> <h2>Two Approaches to Handling the Order of Inputs</h2> <p>There are two distinct ways to reason about this randomness, and it is important not to confuse them.</p> <ul> <li><code>Probabilistic Analysis of a Deterministic Algorithm</code>: assume the input itself comes from some probability distribution (such as a uniformly random ordering of candidates), and analyze the expected running time of a fixed, non-random algorithm over that input distribution.</li> <li><code>Randomized Algorithms</code>: the algorithm itself makes random choices during execution (such as randomly shuffling the candidate order before processing them, regardless of the order they actually arrived in), guaranteeing good expected performance for any input, since the randomness comes from the algorithm rather than an assumption about the input.</li> </ul> <p>The second approach is generally more powerful and reliable in practice, since it removes any dependence on assumptions about how inputs are distributed in the real world, which may not hold. A <code>Randomized Algorithm</code> for the hiring problem simply permutes the candidates randomly before running the same procedure, guaranteeing the same good expected cost regardless of the input's original order.</p> <h2>Indicator Random Variables: A Powerful Analytical Tool</h2> <p>Computing an expected value directly can be complicated when many interacting events are involved. <code>Indicator Random Variables</code> provide an elegant technique that dramatically simplifies such calculations, especially when combined with the linearity of expectation.</p> <p>For an event <code>A</code>, define the indicator random variable:</p> <pre class="code-block"><code>I{A} = 1 if A occurs I{A} = 0 if A does not occur Key property: E[I{A}] = Pr{A}</code></pre><br> <p>The expected value of an indicator variable simply equals the probability of the event it indicates. This becomes powerful when combined with <code>Linearity of Expectation</code>, which states that the expected value of a sum of random variables equals the sum of their expected values, regardless of whether the variables are independent.</p> <pre class="code-block"><code>E[X1 + X2 + ... + Xn] = E[X1] + E[X2] + ... + E[Xn] This holds even when the Xi are NOT independent — a crucial and often surprising fact</code></pre><br> <h2>Applying Indicator Variables to the Hiring Problem</h2> <p>Let <code>Xi</code> be the indicator random variable for the event that candidate <code>i</code> is hired. The total number of hires is <code>X = X1 + X2 + ... + Xn</code>. By linearity of expectation:</p> <pre class="code-block"><code>E[X] = E[X1] + E[X2] + ... + E[Xn] = Σ Pr{candidate i is hired}</code></pre><br> <p>Candidate <code>i</code> is hired precisely when candidate <code>i</code> is the best among the first <code>i</code> candidates seen so far. If the candidates arrive in a uniformly random order, candidate <code>i</code> is equally likely to be the best, second-best, or any rank among the first <code>i</code> candidates, so:</p> <pre class="code-block"><code>Pr{candidate i is hired} = 1/i Therefore: E[X] = Σ (i=1 to n) 1/i = H(n) This is the Harmonic Series, and H(n) = Θ(ln n)</code></pre><br> <p>This remarkable result shows that, despite there being <code>n</code> candidates, the expected number of hires grows only logarithmically with <code>n</code>, a dramatic improvement over the worst-case scenario of <code>n</code> hires. This calculation, made simple through indicator variables, would be considerably more complex using direct probability calculations involving joint distributions.</p> <h2>Why This Technique Generalizes So Widely</h2> <p>The indicator random variable technique is not specific to the hiring problem; it is a general tool applicable whenever a quantity of interest can be expressed as a sum of simpler zero-or-one outcomes, even when those outcomes are correlated with each other. This makes it one of the most broadly useful techniques in the probabilistic analysis of algorithms, and it reappears throughout later topics in this series wherever expected running time needs to be computed.</p> <h2>Why Randomization Matters for Real-World Algorithm Design</h2> <p>Randomized algorithms are used throughout computer science specifically because they can guarantee good expected performance without needing any assumption about the distribution of real-world inputs, protecting against adversarial or unusually structured inputs that could otherwise trigger an algorithm's worst case. A prominent example, explored in depth later in this series, is randomized quicksort, where randomly shuffling the input before sorting protects against the specific input orderings that would otherwise trigger quicksort's quadratic worst case.</p>

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

زمان‌های اجرای بدترین‌حالت، بهترین‌حالت، و حالت‌میانگین که پیش‌تر در این مجموعه بحث شد، همگی فرض می‌کنند خود الگوریتم به‌طور قطعی رفتار می‌کند، و هر تغییری صرفاً از ورودی می‌آید. وضعیت متفاوتی وقتی پیش می‌آید که یا توزیع ورودی ناشناخته باشد یا یک الگوریتم عمداً انتخاب‌های تصادفی در حین اجرای خودش انجام دهد. هر دو وضعیت به ابزارهای 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 را فعال می‌کردند محافظت می‌کند.