{"title":"Chapter 7: Probability","description":"","content":"# Chapter 7: Probability\n\nYou are reading a massive log file that does not fit in memory. You need to pick 5 random lines where every line has an equal chance of being selected. You do not even know how many lines there are. How would you solve this?\n\nThis is the Reservoir Sampling problem, and it is elegant, practical, and a favorite in coding interviews. It combines a simple probability argument with a streaming algorithm that processes data in a single pass. Once you see the proof, it feels almost magical that it works.\n\nProbability shows up in DSA more than most people expect. From shuffling arrays fairly to analyzing the expected runtime of randomized quicksort, a solid grasp of probability fundamentals gives you tools that deterministic thinking alone cannot provide. In this chapter, we will build up from the basics, then dive into two classic algorithms that interviewers love: Reservoir Sampling and Fisher-Yates Shuffle.\n\n---\n\n## Why It Matters\n\nRandomized algorithms appear across systems and interviews alike. Understanding probability lets you reason about correctness and performance in ways that feel unintuitive at first but become second nature with practice.\n\n**In interviews**, you might be asked to:\n\n- Select k random elements from a stream of unknown size\n- Shuffle an array so that every permutation is equally likely\n- Explain why randomized quicksort has O(n log n) expected time\n- Design a random sampling system for A/B testing\n\n**In production systems**, probability drives:\n\n- **Load balancing**: Random assignment distributes requests evenly across servers\n- **A/B testing**: Randomly splitting users into control and experiment groups\n- **Randomized quicksort**: Choosing a random pivot avoids worst-case O(n^2) behavior on sorted input\n- **Skip lists**: Randomized data structures that provide O(log n) search without complex balancing logic\n\n**Interview Insight:** When an interviewer asks \"how would you pick a random element from a stream?\", they are testing whether you know Reservoir Sampling. This is one of those problems where knowing the algorithm makes you look brilliant, and not knowing it makes you struggle.\n\n---\n\n## Core Concepts\n\nBefore we get to the algorithms, let us establish the probability fundamentals you need.\n\n### Sample Space and Events\n\nThe **sample space** S is the set of all possible outcomes of an experiment. An **event** A is a subset of S. The probability of event A is:\n\n**P(A) = |A| / |S|** (when all outcomes are equally likely)\n\nFor example, rolling a fair die has S = {1, 2, 3, 4, 5, 6}. The event \"roll an even number\" is A = {2, 4, 6}, so P(A) = 3/6 = 1/2.\n\n### Addition Rule\n\nFor two events A and B:\n\n**P(A or B) = P(A) + P(B) - P(A and B)**\n\nIf A and B are mutually exclusive (they cannot both happen), this simplifies to P(A or B) = P(A) + P(B).\n\n### Multiplication Rule\n\nFor two events A and B:\n\n**P(A and B) = P(A) * P(B|A)**\n\nwhere P(B|A) is the probability of B given that A has occurred. If A and B are **independent** (knowing A does not change B's probability), this simplifies to P(A and B) = P(A) * P(B).\n\n### Probability Tree\n\nA probability tree is a useful way to visualize sequential random events. Here is an example for two coin flips:\n\n\n```mermaid\nflowchart TD\n S[\"Start\"]:::primary --> H1[\"Heads
P = 0.5\"]:::teal\n S --> T1[\"Tails
P = 0.5\"]:::orange\n\n H1 --> HH[\"HH
P = 0.25\"]:::green\n H1 --> HT[\"HT
P = 0.25\"]:::green\n T1 --> TH[\"TH
P = 0.25\"]:::green\n T1 --> TT[\"TT
P = 0.25\"]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nEach path from root to leaf represents one outcome. The probability of a path is the product of probabilities along its edges. The sum of all leaf probabilities equals 1.\n\n---\n\n## Detailed Explanation\n\n### Expected Value and Linearity of Expectation\n\nThe **expected value** E[X] of a random variable X is the weighted average of its possible values:\n\n**E[X] = sum of (value * probability) for each outcome**\n\nFor a fair die: E[X] = 1*(1/6) + 2*(1/6) + 3*(1/6) + 4*(1/6) + 5*(1/6) + 6*(1/6) = 3.5\n\nThe most powerful property of expected value is **linearity of expectation**:\n\n**E[X + Y] = E[X] + E[Y]**\n\nThis holds even when X and Y are not independent. This property is remarkably useful in algorithm analysis.\n\n**Interview Insight:** Linearity of expectation is the key to analyzing randomized quicksort. Each pair of elements is compared at most once, and the expected number of comparisons across all pairs sums to O(n log n). You do not need the pairs to be independent to add their expectations.\n\n### Reservoir Sampling\n\nReservoir Sampling solves the problem we opened with: selecting k items uniformly at random from a stream of unknown size n, using O(k) memory.\n\n**The Algorithm (for general k):**\n\n1. Fill a reservoir array with the first k items from the stream\n2. For each subsequent item i (where i goes from k+1 to n):\n\n- Generate a random integer j between 1 and i (inclusive)\n- If j is less than or equal to k, replace reservoir[j] with item i\n\n1. After processing the entire stream, the reservoir contains k uniformly random items\n\n**Why does it work?** We need to show that every item ends up in the reservoir with probability k/n.\n\nFor the special case k = 1, the argument is clean. When we see item i, we keep it with probability 1/i. For item i to survive in the reservoir at the end, it must be kept at step i (probability 1/i) and not replaced at steps i+1, i+2, ..., n. The probability of not being replaced at step j is (j-1)/j. So the overall probability is:\n\nP = (1/i) * (i/(i+1)) * ((i+1)/(i+2)) * ... * ((n-1)/n) = 1/n\n\nThe fractions telescope beautifully, leaving exactly 1/n for every item. This is what makes the algorithm correct.\n\n\n```mermaid\nflowchart LR\n A[\"Stream:
item 1, item 2, ..., item n\"]:::primary\n B[\"Reservoir
(size k)\"]:::teal\n C{\"Random j
in [1, i]\"}:::orange\n D[\"j <= k?
Replace reservoir[j]\"]:::green\n E[\"j > k?
Skip item\"]:::red\n\n A --> B\n A --> C\n C --> D\n C --> E\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\n### Fisher-Yates Shuffle\n\nThe Fisher-Yates shuffle (also called the Knuth shuffle) generates a uniformly random permutation of an array in O(n) time and O(1) extra space.\n\n**The Algorithm:**\n\n1. Start from the last element (index n-1)\n2. Pick a random index j between 0 and i (inclusive)\n3. Swap arr[i] with arr[j]\n4. Move to the previous element (i = i-1)\n5. Repeat until i = 0\n\nThe key insight is that at each step, we are selecting which element goes into position i from the remaining unchosen elements (positions 0 through i). After n-1 swaps, every permutation is equally likely.\n\n**Why is this correct?** There are n! possible permutations of n elements. The algorithm makes n choices: the first with n options, the second with n-1 options, and so on. That gives n * (n-1) * ... * 1 = n! possible execution paths, each equally likely. Since each path produces a distinct permutation, every permutation has probability 1/n!.\n\n\n```mermaid\nflowchart TD\n A[\"Array: [A, B, C, D]\"]:::primary\n B[\"i=3: pick j in [0,3]
swap arr[3] with arr[j]\"]:::teal\n C[\"i=2: pick j in [0,2]
swap arr[2] with arr[j]\"]:::orange\n D[\"i=1: pick j in [0,1]
swap arr[1] with arr[j]\"]:::green\n E[\"Shuffled array\"]:::red\n\n A --> B --> C --> D --> E\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\n**Interview Insight:** A common follow-up question is \"what happens if you pick j from 0 to n-1 at every step instead of 0 to i?\" This produces a biased shuffle. For n=3, there are 3^3 = 27 execution paths but only 3! = 6 permutations, and 27 is not divisible by 6. Some permutations will appear more often than others.\n\n---\n\n## Example Walkthrough\n\n### Reservoir Sampling (k=1, stream of 5 elements)\n\nLet us trace through Reservoir Sampling with k=1 on the stream [A, B, C, D, E].\n\n\n```shell\nStep 1: See item A\n Reservoir = [A] (fill first k=1 items)\n\nStep 2: See item B (i=2)\n Random j in [1, 2]\n Suppose j = 1 (probability 1/2): Replace reservoir[0] with B\n Reservoir = [B]\n\nStep 3: See item C (i=3)\n Random j in [1, 3]\n Suppose j = 3 (probability 2/3 that j > 1): Keep B\n Reservoir = [B]\n\nStep 4: See item D (i=4)\n Random j in [1, 4]\n Suppose j = 1 (probability 1/4): Replace reservoir[0] with D\n Reservoir = [D]\n\nStep 5: See item E (i=5)\n Random j in [1, 5]\n Suppose j = 3 (probability 4/5 that j > 1): Keep D\n Reservoir = [D]\n\nFinal result: D\n```\n\n\nLet us verify the probability that each item is selected equals 1/5:\n\n\n| Item | P(selected at its step) | P(survives all later steps) | P(in final reservoir) |\n|------|------------------------|----------------------------|----------------------|\n| A | 1 (first item) | 1/2 * 2/3 * 3/4 * 4/5 | **1/5** |\n| B | 1/2 | 2/3 * 3/4 * 4/5 | **1/5** |\n| C | 1/3 | 3/4 * 4/5 | **1/5** |\n| D | 1/4 | 4/5 | **1/5** |\n| E | 1/5 | 1 (last item) | **1/5** |\n\n\nEvery item has exactly a 1/5 chance. The telescoping product is what makes this work.\n\n### Fisher-Yates Shuffle on [1, 2, 3, 4]\n\n\n```shell\nInitial array: [1, 2, 3, 4]\n\nStep 1: i = 3, pick random j in [0, 3]\n Suppose j = 1\n Swap arr[3] and arr[1]: [1, 4, 3, 2]\n\nStep 2: i = 2, pick random j in [0, 2]\n Suppose j = 0\n Swap arr[2] and arr[0]: [3, 4, 1, 2]\n\nStep 3: i = 1, pick random j in [0, 1]\n Suppose j = 1\n Swap arr[1] and arr[1]: [3, 4, 1, 2] (no change)\n\nFinal shuffled array: [3, 4, 1, 2]\n```\n\n\nNotice that at each step, the range of j shrinks by one. Position i is \"locked in\" after step i, meaning only positions 0 through i-1 are still candidates for future swaps. This is what guarantees a uniform distribution.\n\n---\n\n## Implementation\n\n### Reservoir Sampling (k=1)\n\n**Java**\n\n\n```java\nimport java.util.Random;\n\npublic class ReservoirSamplingOne {\n public static int sample(int[] stream) {\n Random rand = new Random();\n int result = stream[0];\n for (int i = 1; i < stream.length; i++) {\n int j = rand.nextInt(i + 1); // random int in [0, i]\n if (j == 0) {\n result = stream[i];\n }\n }\n return result;\n }\n}\n```\n\n\n**Python**\n\n\n```python\nimport random\n\ndef reservoir_sample_one(stream):\n result = None\n for i, item in enumerate(stream):\n if i == 0:\n result = item\n else:\n j = random.randint(0, i)\n if j == 0:\n result = item\n return result\n```\n\n\n**C++**\n\n\n```cpp\n#include \n#include \n#include \n\nint reservoirSampleOne(const std::vector& stream) {\n std::mt19937 rng(std::random_device{}());\n int result = stream[0];\n for (int i = 1; i < (int)stream.size(); i++) {\n std::uniform_int_distribution dist(0, i);\n if (dist(rng) == 0) {\n result = stream[i];\n }\n }\n return result;\n}\n```\n\n\n**C#**\n\n\n```csharp\nusing System;\n\npublic class ReservoirSampling {\n public static int SampleOne(int[] stream) {\n Random rand = new Random();\n int result = stream[0];\n for (int i = 1; i < stream.Length; i++) {\n int j = rand.Next(0, i + 1); // [0, i] inclusive\n if (j == 0) {\n result = stream[i];\n }\n }\n return result;\n }\n}\n```\n\n\n**JavaScript**\n\n\n```javascript\nfunction reservoirSampleOne(stream) {\n let result = stream[0];\n for (let i = 1; i < stream.length; i++) {\n const j = Math.floor(Math.random() * (i + 1));\n if (j === 0) {\n result = stream[i];\n }\n }\n return result;\n}\n```\n\n\n**TypeScript**\n\n\n```typescript\nfunction reservoirSampleOne(stream: number[]): number {\n let result: number = stream[0];\n for (let i = 1; i < stream.length; i++) {\n const j: number = Math.floor(Math.random() * (i + 1));\n if (j === 0) {\n result = stream[i];\n }\n }\n return result;\n}\n```\n\n\n### Reservoir Sampling (General k)\n\n**Java**\n\n\n```java\nimport java.util.Random;\n\npublic class ReservoirSamplingK {\n public static int[] sample(int[] stream, int k) {\n Random rand = new Random();\n int[] reservoir = new int[k];\n for (int i = 0; i < k; i++) {\n reservoir[i] = stream[i];\n }\n for (int i = k; i < stream.length; i++) {\n int j = rand.nextInt(i + 1); // random int in [0, i]\n if (j < k) {\n reservoir[j] = stream[i];\n }\n }\n return reservoir;\n }\n}\n```\n\n\n**Python**\n\n\n```python\nimport random\n\ndef reservoir_sample_k(stream, k):\n reservoir = []\n for i, item in enumerate(stream):\n if i < k:\n reservoir.append(item)\n else:\n j = random.randint(0, i)\n if j < k:\n reservoir[j] = item\n return reservoir\n```\n\n\n**C++**\n\n\n```cpp\n#include \n#include \n\nstd::vector reservoirSampleK(const std::vector& stream, int k) {\n std::mt19937 rng(std::random_device{}());\n std::vector reservoir(stream.begin(), stream.begin() + k);\n for (int i = k; i < (int)stream.size(); i++) {\n std::uniform_int_distribution dist(0, i);\n int j = dist(rng);\n if (j < k) {\n reservoir[j] = stream[i];\n }\n }\n return reservoir;\n}\n```\n\n\n**C#**\n\n\n```csharp\nusing System;\n\npublic class ReservoirSamplingK {\n public static int[] Sample(int[] stream, int k) {\n Random rand = new Random();\n int[] reservoir = new int[k];\n Array.Copy(stream, reservoir, k);\n for (int i = k; i < stream.Length; i++) {\n int j = rand.Next(0, i + 1);\n if (j < k) {\n reservoir[j] = stream[i];\n }\n }\n return reservoir;\n }\n}\n```\n\n\n**JavaScript**\n\n\n```javascript\nfunction reservoirSampleK(stream, k) {\n const reservoir = stream.slice(0, k);\n for (let i = k; i < stream.length; i++) {\n const j = Math.floor(Math.random() * (i + 1));\n if (j < k) {\n reservoir[j] = stream[i];\n }\n }\n return reservoir;\n}\n```\n\n\n**TypeScript**\n\n\n```typescript\nfunction reservoirSampleK(stream: number[], k: number): number[] {\n const reservoir: number[] = stream.slice(0, k);\n for (let i = k; i < stream.length; i++) {\n const j: number = Math.floor(Math.random() * (i + 1));\n if (j < k) {\n reservoir[j] = stream[i];\n }\n }\n return reservoir;\n}\n```\n\n\n### Fisher-Yates Shuffle\n\n**Java**\n\n\n```java\nimport java.util.Random;\n\npublic class FisherYatesShuffle {\n public static void shuffle(int[] arr) {\n Random rand = new Random();\n for (int i = arr.length - 1; i > 0; i--) {\n int j = rand.nextInt(i + 1); // random int in [0, i]\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n }\n }\n}\n```\n\n\n**Python**\n\n\n```python\nimport random\n\ndef fisher_yates_shuffle(arr):\n for i in range(len(arr) - 1, 0, -1):\n j = random.randint(0, i)\n arr[i], arr[j] = arr[j], arr[i]\n```\n\n\n**C++**\n\n\n```cpp\n#include \n#include \n\nvoid fisherYatesShuffle(std::vector& arr) {\n std::mt19937 rng(std::random_device{}());\n for (int i = (int)arr.size() - 1; i > 0; i--) {\n std::uniform_int_distribution dist(0, i);\n std::swap(arr[i], arr[dist(rng)]);\n }\n}\n```\n\n\n**C#**\n\n\n```csharp\nusing System;\n\npublic class FisherYatesShuffle {\n public static void Shuffle(int[] arr) {\n Random rand = new Random();\n for (int i = arr.Length - 1; i > 0; i--) {\n int j = rand.Next(0, i + 1);\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n }\n }\n}\n```\n\n\n**JavaScript**\n\n\n```javascript\nfunction fisherYatesShuffle(arr) {\n for (let i = arr.length - 1; i > 0; i--) {\n const j = Math.floor(Math.random() * (i + 1));\n [arr[i], arr[j]] = [arr[j], arr[i]];\n }\n}\n```\n\n\n**TypeScript**\n\n\n```typescript\nfunction fisherYatesShuffle(arr: number[]): void {\n for (let i = arr.length - 1; i > 0; i--) {\n const j: number = Math.floor(Math.random() * (i + 1));\n [arr[i], arr[j]] = [arr[j], arr[i]];\n }\n}\n```\n\n\n---\n\n## Complexity Analysis\n\n### Reservoir Sampling\n\n\n| Metric | Complexity | Explanation |\n|--------|-----------|-------------|\n| **Time** | O(n) | Single pass through the stream of n elements |\n| **Space** | O(k) | Only the reservoir of size k is stored |\n\n\nThis is optimal. You must read every element at least once (you cannot skip elements in a stream and still guarantee uniformity), so O(n) time is a lower bound. And you need O(k) space to hold the result.\n\n### Fisher-Yates Shuffle\n\n\n| Metric | Complexity | Explanation |\n|--------|-----------|-------------|\n| **Time** | O(n) | One swap per element |\n| **Space** | O(1) | In-place, no extra memory beyond a few variables |\n\n\nFisher-Yates is also optimal. Generating a random permutation requires touching each element at least once, so O(n) is a lower bound for time.\n\n### Why Randomization Helps\n\nRandomized algorithms trade determinism for performance guarantees that hold \"in expectation\" or \"with high probability.\"\n\nThe classic example is **randomized quicksort**. Deterministic quicksort with a fixed pivot strategy (like always choosing the first element) degrades to O(n^2) on sorted input. Randomized quicksort picks a random pivot, making O(n^2) behavior astronomically unlikely regardless of input. The expected time is O(n log n) for any input.\n\n\n```mermaid\nflowchart LR\n A[\"Input Array\"]:::primary\n B{\"Pick random
pivot\"}:::orange\n C[\"Partition around
pivot\"]:::teal\n D[\"Recurse on
left half\"]:::green\n E[\"Recurse on
right half\"]:::green\n F[\"Sorted Array\"]:::primary\n\n A --> B --> C\n C --> D\n C --> E\n D --> F\n E --> F\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe randomness makes the algorithm robust against adversarial inputs. No matter what data you feed it, the expected performance is O(n log n). This is a fundamentally different guarantee than \"O(n log n) on average-case random input.\"\n\n---\n\n## Common Mistakes\n\n### 1. Biased Shuffle from Wrong Random Range\n\nThe most common mistake in implementing Fisher-Yates is picking j from the full range [0, n-1] at every step instead of [0, i].\n\n\n```java\n// WRONG: biased shuffle\nfor (int i = arr.length - 1; i > 0; i--) {\n int j = rand.nextInt(arr.length); // Bug: should be rand.nextInt(i + 1)\n swap(arr, i, j);\n}\n```\n\n\nThis produces n^n possible execution paths instead of n!, and since n^n is not divisible by n! for n >= 3, some permutations will be more likely than others. For a 3-element array, this bias is measurable: some permutations appear roughly 33% more often than they should.\n\n### 2. Off-by-One in Reservoir Sampling\n\nA subtle error is using the wrong range for the random index. If you generate j in [0, i-1] instead of [0, i], or use [1, i] instead of [1, i] inclusive, the probabilities no longer telescope correctly.\n\n\n```java\n// WRONG: off-by-one\nfor (int i = k; i < stream.length; i++) {\n int j = rand.nextInt(i); // Bug: should be rand.nextInt(i + 1)\n if (j < k) {\n reservoir[j] = stream[i];\n }\n}\n```\n\n\nWith `rand.nextInt(i)` the range is [0, i-1], giving each new item a slightly higher chance of entering the reservoir than it should have. The final distribution will not be uniform.\n\n### 3. Using rand() % n for \"Uniform\" Random Numbers\n\nIn C and C++, the expression `rand() % n` is not truly uniform when RAND_MAX + 1 is not divisible by n. For example, if RAND_MAX is 32767 and n is 3, there are 32768 possible values. Since 32768 = 10922 * 3 + 2, the values 0 and 1 are each slightly more likely (10923/32768) than value 2 (10922/32768).\n\nUse `std::uniform_int_distribution` in C++ or the language-appropriate uniform random facility. In Java, `Random.nextInt(bound)` handles this correctly. In Python, `random.randint(a, b)` is uniform.\n\n### 4. Forgetting That Reservoir Must Be Filled First\n\nWhen implementing general-k Reservoir Sampling, you must fill the reservoir with the first k items before starting the replacement logic. A common bug is starting the replacement loop at index 0 instead of index k, which corrupts the initial reservoir state.\n\n---\n\n## Interview Questions\n\n**Q1: How would you select a random node from a linked list in one pass, without knowing the length?**\n\nThis is Reservoir Sampling with k=1. Walk through the list, keeping a counter i starting at 1. For each node, generate a random number in [1, i]. If it equals 1, replace the current selection with this node. After reaching the end, the selected node is uniformly random.\n\nThe proof is the same telescoping argument. Node i is selected at step i with probability 1/i, and survives all subsequent steps with probability i/(i+1) * (i+1)/(i+2) * ... * (n-1)/n. The product telescopes to 1/n.\n\n**Q2: Why does Fisher-Yates produce a uniform shuffle, but picking a random index from [0, n-1] at every step does not?**\n\nFisher-Yates makes choices that shrink by one each step: n choices, then n-1, then n-2, and so on. This produces n! equally likely execution paths, one for each permutation. The naive approach with a fixed range [0, n-1] produces n^(n-1) execution paths. Since n^(n-1) is generally not divisible by n!, multiple paths map to the same permutation unevenly, creating bias.\n\nFor n=3: Fisher-Yates has 3 * 2 * 1 = 6 paths for 6 permutations. The naive approach has 3^2 = 9 paths for 6 permutations. 9 is not divisible by 6, so at least one permutation must appear more often.\n\n**Q3: Can you modify Reservoir Sampling to give weighted sampling, where item i has weight w_i?**\n\nYes. Instead of replacing the reservoir element with probability 1/i, use weighted replacement. One approach: for each item, generate a random key = rand()^(1/w_i) and keep the k items with the largest keys. This is the algorithm by Efraimidis and Spirakis (2006). The key insight is that raising a uniform random number to the power 1/w gives heavier items larger keys on average, so they are more likely to remain in the reservoir.\n\n**Q4: What is the expected number of comparisons in randomized quicksort, and how do you derive it using linearity of expectation?**\n\nThe expected number of comparisons is 2n * ln(n), which is O(n log n). The derivation uses linearity of expectation. For each pair of elements (i, j) in the sorted order, define an indicator variable X_ij that is 1 if i and j are ever compared. Two elements are compared only if one of them is chosen as a pivot before any element between them. The probability of this is 2/(j - i + 1). The expected total comparisons is the sum of 2/(j - i + 1) over all pairs, which evaluates to 2n * H_n (where H_n is the n-th harmonic number), approximately 2n * ln(n).\n\n---\n\n## Summary\n\n- **P(A)** = favorable outcomes / total outcomes when outcomes are equally likely. The addition rule handles \"or\" events, the multiplication rule handles \"and\" events.\n- **Expected value** is the weighted average of outcomes. Linearity of expectation (E[X+Y] = E[X] + E[Y]) holds even for dependent variables, making it the go-to tool for analyzing randomized algorithms.\n- **Reservoir Sampling** selects k items uniformly at random from a stream of unknown size in O(n) time and O(k) space. The correctness proof relies on a telescoping product of probabilities.\n- **Fisher-Yates Shuffle** generates a uniformly random permutation in O(n) time and O(1) extra space. The critical detail is that the random range must shrink at each step (pick j in [0, i], not [0, n-1]).\n- **Randomization helps** by making algorithms robust against adversarial inputs. Randomized quicksort achieves O(n log n) expected time regardless of input order.\n- **Common pitfalls** include biased shuffles from a fixed random range, off-by-one errors in reservoir indices, and using non-uniform random number generators like `rand() % n`.\n\n---\n\n## References\n\n- Knuth, D. E. *The Art of Computer Programming, Volume 2: Seminumerical Algorithms* (Section 3.4.2, Algorithm P). Addison-Wesley.\n- Vitter, J. S. \"Random Sampling with a Reservoir.\" *ACM Transactions on Mathematical Software*, 1985. https://doi.org/10.1145/3147.3165\n- Fisher, R. A. and Yates, F. *Statistical Tables for Biological, Agricultural and Medical Research*. Oliver and Boyd, 1938.\n- Efraimidis, P. and Spirakis, P. \"Weighted Random Sampling with a Reservoir.\" *Information Processing Letters*, 2006. https://doi.org/10.1016/j.ipl.2005.11.003\n- Wikipedia: Fisher-Yates Shuffle. https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle\n- Mitzenmacher, M. and Upfal, E. *Probability and Computing: Randomized Algorithms and Probabilistic Analysis*. Cambridge University Press.","pageType":"dsa"}

Chapter 7: Probability

Ashish Pratap Singh

Get Premium