11. Randomized and Probabilistic Algorithms

Introduction and Context

Classical algorithm analysis often assumes that the input is fixed and that the algorithm follows a completely determined sequence of operations. In many important computing problems, however, a deterministic strategy is either inefficient, vulnerable to adversarial inputs, or difficult to design. Randomization provides an alternative: an algorithm may make deliberate random choices so that its performance is excellent on average, even when the input is unfavorable.

Randomized algorithms are especially important in artificial intelligence and machine learning, where data are large, high-dimensional, noisy, and frequently sampled. Randomization supports approximate computation, scalable data processing, randomized optimization, hashing, distributed coordination, privacy-preserving mechanisms, and probabilistic data structures. The central analytical challenge is to reason about an algorithm whose execution is not completely predictable. This requires probability, expectation, indicator variables, tail bounds, and an explicit distinction between different meanings of correctness.

A randomized algorithm does not necessarily produce an uncertain or unreliable answer. Its random choices may be used only to determine the path by which it reaches a guaranteed answer. Alternatively, the algorithm may always run within a prescribed time but occasionally return an incorrect answer. These two cases lead to the fundamental categories of Las Vegas and Monte Carlo algorithms.

Learning Objectives

After completing this chapter, the learner should be able to:

1. Explain the role of randomness in algorithm design and analysis.

2. Distinguish Las Vegas and Monte Carlo algorithms using correctness and running-time guarantees.

3. Apply indicator random variables and linearity of expectation to algorithm analysis.

4. Use concentration ideas, including Markov, Chebyshev, and Chernoff bounds, to reason about deviations from expected behavior.

5. Analyze randomized quicksort, randomized selection, hashing, sampling, and probabilistic data structures.

6. Identify the effects of adversarial inputs, weak random-number generation, and poor parameter choices.

7. Select appropriate randomized techniques for practical AI, ML, and large-scale computing applications.

8. Evaluate the ethical, security, and reproducibility implications of randomized computation.

1. Randomness as an Algorithmic Resource

A randomized algorithm has access to a source of random bits and uses those bits during execution. For a fixed input, different random outcomes may lead to different execution paths, running times, or outputs. Algorithm analysis therefore considers a probability distribution over executions.

If an algorithm A receives input x and uses a random seed R, its behavior can be written as A(x, R). The input may be fixed while R varies, or both the input and the random choices may be modeled probabilistically. This distinction matters. An analysis over random choices is an average over the algorithm's internal behavior, whereas an analysis over a distribution of inputs is an average over possible data. The two should not be confused.

Randomization is useful for several reasons. It can prevent a deterministic algorithm from consistently encountering its worst case; simplify the design of algorithms that otherwise require complicated deterministic rules; provide efficient approximate answers; and distribute work or select representative samples. Randomization can also improve robustness against an adversary who does not know the future random choices.

Randomness does not automatically improve an algorithm. A randomized method must be analyzed in terms of correctness, expected or high-probability running time, variance, implementation cost, and the quality of its random source. In security-sensitive applications, unpredictability is a stronger requirement than merely appearing statistically random.

2. Las Vegas and Monte Carlo Methods

The distinction between Las Vegas and Monte Carlo algorithms is based on what is guaranteed and what is allowed to vary.

A Las Vegas algorithm always returns a correct answer, but its running time is random. A randomized quicksort implementation is a standard example: regardless of the pivots selected, it sorts correctly; random choices influence the running time. A randomized search procedure may similarly repeat trials until a certificate of correctness is obtained.

A Monte Carlo algorithm has a bounded or controlled running time, but it may return an incorrect answer with a limited probability. For example, a randomized primality test may declare a composite number probably prime after a fixed number of rounds. The probability of error can generally be reduced by independent repetition.

The error probability of a Monte Carlo algorithm is often called its failure probability. If one independent run has error probability p, and the algorithm is repeated k times with a suitable rule for combining results, the failure probability may decrease exponentially. For instance, if every run must fail for the combined result to be wrong, the probability is p^k. This improvement assumes independence or an adequately controlled dependence structure.

A useful comparison is:

| Property | Las Vegas | Monte Carlo |

|---|---|---|

| Answer correctness | Always correct | Correct with high probability or bounded error |

| Running time | Random | Usually bounded or predictable |

| Main analytical quantity | Expected running time | Error probability and running time |

| Typical use | Randomized sorting, exact search | Testing, approximation, simulation |

Some algorithms can be transformed between these categories. A Monte Carlo method may be converted into a Las Vegas method if an efficient verification procedure exists: the algorithm repeatedly generates a candidate and verifies it, returning only a verified answer. Conversely, a Las Vegas algorithm can sometimes be truncated to obtain a Monte Carlo method, accepting a small probability of failure when the time limit is reached.

3. The Probabilistic Toolkit for Algorithm Analysis

3.1 Sample spaces and random variables

The sample space is the set of all possible outcomes of the random choices. A random variable assigns a numerical value to each outcome. In algorithm analysis, a random variable may represent the running time, number of comparisons, number of collisions, memory consumption, or approximation error.

The expected value of a discrete random variable X is

E[X] = Σx x Pr[X = x].

Expectation is an average over repeated executions under the stated probability model. It does not imply that a particular execution will take exactly E[X] time. An algorithm can have a small expected running time while occasionally taking much longer.

3.2 Indicator random variables

An indicator variable is defined by

I(E) = 1 if event E occurs, and 0 otherwise.

Its expectation is simply Pr[E]. If X counts the number of events E1, E2, ..., En, then

X = I(E1) + I(E2) + ... + I(En),

and therefore

E[X] = Σ Pr[Ei].

This result, known as the linearity of expectation, holds even when the events are dependent. That feature makes indicator variables particularly powerful. Analysts can count complex events without calculating the full joint probability distribution.

For example, suppose n items are assigned independently and uniformly to n positions. Let Ii indicate that item i occupies its original position. The number of fixed points is X = ΣIi. Since Pr[Ii = 1] = 1/n, E[X] = n(1/n) = 1. The expected number of fixed points is one, although the events are not necessarily independent under some assignment models.

3.3 Conditional expectation and the probabilistic method

The law of total expectation states that E[X] = E[E[X | Y]]. This is useful when an algorithm proceeds in stages or when conditioning on an initial random choice simplifies the analysis.

The probabilistic method proves the existence of an object with a desired property by showing that a randomly constructed object has positive probability of possessing that property. If a random construction has expected cost at most c, then at least one outcome has cost at most c. The method may establish existence without providing an efficient construction, although in algorithm design it often suggests a randomized procedure.

3.4 Concentration and tail bounds

An expectation alone is incomplete. A system with expected load 100 may usually have load close to 100, or it may have load 0 most of the time and an extremely large load occasionally. Concentration bounds quantify the probability that a random variable deviates from its expectation.

Markov's inequality applies to a nonnegative random variable X:

Pr[X ≥ a] ≤ E[X]/a, for a > 0.

It requires few assumptions but may be loose. Chebyshev's inequality uses variance:

Pr[|X − E[X]| ≥ t] ≤ Var(X)/t².

Chernoff bounds are often much stronger for sums of independent Bernoulli variables. If X is the sum of independent indicators with mean μ, then, informally, the probability that X differs from μ by a fixed fraction decreases exponentially in μ. One common upper-tail form is

Pr[X ≥ (1 + δ)μ] ≤ [e^δ/(1 + δ)^(1 + δ)]^μ, for δ > 0.

The exact form is less important than the principle: independent random choices often produce sharply concentrated outcomes. This is why randomized hashing, sampling, and load balancing can provide reliable performance at scale.

4. Randomized Quicksort and Randomized Selection

4.1 Randomized quicksort

Quicksort selects a pivot, partitions the array into elements smaller and larger than the pivot, and recursively sorts the two parts. Its worst-case running time is Θ(n²) when the pivot repeatedly produces highly unbalanced partitions. If the pivot is selected uniformly at random from the current subarray, the expected running time is Θ(n log n), regardless of the order of the input.

A useful analysis focuses on comparisons. Consider two elements in the sorted order, zi and zj, with i < j. They are compared only if one of them is selected as the first pivot from the set of elements zi, zi+1, ..., zj. Every element in this set is equally likely to be selected first, so the probability of comparison is 2/(j − i + 1). Summing this probability over all pairs gives an expected number of comparisons of O(n log n).

The algorithm remains vulnerable if the random generator is predictable, biased, or repeatedly initialized with the same seed. In adversarial environments, pivot selection should be independent of information available to the attacker, or a deterministic worst-case linear-time selection method should be considered.

4.2 Randomized selection

The selection problem asks for the kth smallest element. Randomized quickselect chooses a random pivot and recursively continues only in the partition containing the kth element. Unlike quicksort, it does not process both sides.

The expected running time is Θ(n). If a pivot divides the input reasonably often, the problem shrinks rapidly. Even though an occasional poor pivot is possible, the expected total work remains linear. However, the worst-case time is Θ(n²). A Las Vegas version still returns the exact kth element; the randomness affects only its running time.

Randomized selection is useful in robust statistics, quantile computation, feature engineering, approximate query processing, and data summarization. For very large data sets, exact selection may be combined with sampling or distributed partitioning.

5. Hashing and Randomized Dictionaries

Hashing maps keys to positions in a table. If h is a hash function and the table has m slots, a collision occurs when distinct keys receive the same slot. A randomized hash family provides a distribution over hash functions rather than relying on one fixed function.

A family H is universal if, for any distinct keys x and y, the probability over a randomly chosen h from H that h(x) = h(y) is at most 1/m. Universal hashing limits the expected number of collisions even when keys are selected adversarially, provided the hash function is chosen secretly or independently of the adversary's choices.

With separate chaining, the expected lookup cost is related to the load factor α = n/m, where n is the number of stored keys. Under suitable hashing assumptions, expected chain length is O(1 + α). Keeping α bounded supports expected constant-time dictionary operations.

Hashing is used in symbol tables, caches, database joins, duplicate detection, compiler implementations, distributed storage, and machine-learning feature maps. In ML, the hashing trick maps high-dimensional categorical features into a fixed-dimensional vector. It saves memory but introduces collisions, which can create interference between features. Increasing the dimension reduces collision probability but increases computational and memory cost.

Security-sensitive hash tables require additional care. An attacker who can force many collisions can cause denial-of-service behavior. Randomized hash seeds, strong hash functions, bounded input processing, and monitoring of collision patterns are practical defenses.

6. Random Sampling and Approximate Computation

Sampling replaces an expensive computation over all data with a computation over a carefully selected subset. The value of a sample depends on its selection mechanism. Uniform sampling is appropriate for estimating a population mean when every record should have equal probability of selection. Stratified or importance sampling is preferable when rare but important groups must be represented.

6.1 Estimating a mean

Suppose X1, ..., Xs are independent observations sampled from a population with mean μ. The estimator

μ̂ = (1/s)ΣXi

is unbiased when the observations are sampled appropriately, meaning E[μ̂] = μ. Its variance decreases as the sample size grows. Concentration bounds can then provide a sample size sufficient to achieve a desired error tolerance and confidence level.

An unbiased estimator is not automatically useful. It may have high variance, and a biased estimator may have lower total error in some applications. Analysts should consider bias, variance, confidence intervals, distribution shift, and the cost of obtaining additional samples.

6.2 Reservoir sampling

Reservoir sampling selects a uniform sample of fixed size k from a stream whose length is unknown. The first k items fill the reservoir. When the ith item arrives, it is selected with probability k/i; if selected, it replaces a uniformly chosen reservoir item. At the end, every item in the stream has probability k/n of appearing in the reservoir.

This method is valuable in streaming analytics, telemetry, online learning, and monitoring systems. It uses O(k) memory and processes each item in constant expected time. If records have unequal importance, weighted reservoir sampling or another sampling design is required.

6.3 Monte Carlo estimation

Monte Carlo methods estimate a quantity by repeated random trials. If Y is a random variable whose expectation equals the target quantity θ, the sample average of independent trials estimates θ. Increasing the number of trials generally reduces standard error at a rate proportional to 1/√s. This convergence can be slow, which motivates variance-reduction methods such as control variates, antithetic sampling, importance sampling, and stratification.

In AI and ML, Monte Carlo estimation appears in policy evaluation, Bayesian inference, uncertainty quantification, reinforcement learning, randomized numerical linear algebra, and simulation-based optimization.

7. Probabilistic Data Structures

Probabilistic data structures trade exactness for compact memory and fast operations. Their errors should be characterized explicitly rather than described vaguely as “approximately correct.”

A Bloom filter represents a set using a bit array and several hash functions. To insert an item, the corresponding bit positions are set to one. To query membership, all corresponding bits are checked. A false positive is possible: the structure may report that an absent item is present. A false negative is not possible under ordinary insertion-only operation. The false-positive rate depends on the number of bits, number of hash functions, and number of inserted elements.

A Count-Min Sketch estimates frequencies in a stream. It uses several arrays and hash functions; an update increments one counter in each row, and a query takes the minimum of the corresponding counters. With nonnegative updates, the estimate does not underestimate the true frequency, but it may overestimate because of collisions.

A HyperLogLog-type structure estimates the number of distinct elements using a small amount of memory. It is useful when exact distinct counting would require storing all identifiers. These structures are common in databases, network monitoring, search systems, and large-scale analytics.

Probabilistic structures are appropriate when a small, quantifiable error is preferable to excessive memory or latency. They are inappropriate when a false positive or frequency overestimate can trigger severe legal, safety, or financial consequences without a verification step.

8. A Framework for Designing and Evaluating Randomized Algorithms

A disciplined design process contains several decisions.

First, identify the source of difficulty: adversarial ordering, large input size, expensive exact computation, uncertain data, or distributed coordination. Second, specify what is random: pivot choices, hash functions, sample selection, initialization, or exploration actions. Third, define the guarantee precisely. Is correctness absolute? Is the time expected, high probability, or worst case? What is the permitted error probability?

Fourth, derive the relevant random variables and use indicators, conditioning, or recurrence relations to analyze them. Fifth, examine concentration rather than expectation alone. Sixth, determine how random choices will be generated, stored, seeded, and tested. Finally, validate the implementation through repeated experiments, independent seeds, adversarial tests, and statistical diagnostics.

A high-probability guarantee typically means that an undesirable event occurs with probability at most δ, where δ is explicitly stated. It does not mean that failure is impossible. In production, the choice of δ should reflect the number of executions, the cost of failure, and whether failures can accumulate over time.

9. Applied Case Study: Randomized Feature Processing in a Streaming Fraud System

Background

Consider an illustrative financial-technology system that receives millions of transaction events per hour. Each event contains categorical attributes such as merchant, device type, geographic region, and account context. The system must detect repeated entities, estimate feature frequencies, and reject clearly invalid records before sending selected features to a more expensive ML model.

Situation and Problem

An exact set of all previously seen identifiers would require substantial memory. Exact frequency tables would also grow continuously. Furthermore, an attacker might deliberately submit specially chosen identifiers to exploit predictable hash behavior and overload a service.

Analysis

The system needs several different guarantees. Membership screening should be fast and memory efficient, but a false positive should only cause an additional verification lookup rather than an automatic rejection. Frequency estimates may tolerate small overestimates. The hash function must not be predictable by an external user.

Approach and Strategy

The system uses a Bloom filter for an initial membership test, followed by an exact database lookup for any positive result. A Count-Min Sketch estimates the frequency of selected features and triggers deeper analysis when a feature appears unusually often. Hash functions are selected from a keyed or randomized family, and the seed is rotated under controlled operational procedures. A reservoir sample is maintained for human investigation and model-drift analysis.

The design documents the bit-array size, number of hash functions, expected insertion volume, target false-positive rate, sketch dimensions, and sampling policy. Periodic exact audits estimate whether observed collision behavior remains consistent with the assumptions.

Outcome

The architecture reduces memory and average lookup cost while preserving exact decisions at the final verification stage. The probabilistic structures serve as filters and estimators rather than authoritative sources of truth. Randomized hashing also makes it harder for an external party to manufacture systematic collisions.

Learning Points

The case illustrates that different probabilistic tools solve different problems. It also demonstrates the importance of separating approximate screening from legally or operationally consequential decisions. A probability guarantee is meaningful only when its assumptions, parameters, and failure-handling procedures are explicit.

10. Limitations, Risks, and Common Mistakes

A frequent mistake is to confuse expected performance with a guarantee for every execution. Randomized quicksort has expected O(n log n) time, but a particular run can be quadratic. Another mistake is to use independence assumptions that do not hold. Hash collisions, samples, and distributed events may be correlated.

Poor random-number generators can introduce bias, repeated patterns, or predictability. A fixed seed is useful for debugging and reproducibility, but it should not be used as the only seed in a security-sensitive deployment. Repeating a randomized algorithm does not always reduce error if the repetitions share the same flawed randomness or data bias.

Sampling can amplify dataset bias. A uniformly sampled dataset may underrepresent rare populations, while a convenient sample may exclude them entirely. In probabilistic data structures, parameter choices determine error rates; memory savings obtained by ignoring these parameters can produce unacceptable false positives or distorted estimates.

Randomized algorithms can also be difficult to debug because failures may not be reproducible. Systems should record seeds or experiment identifiers when appropriate, while ensuring that secrets are not exposed. Reproducibility must be balanced against confidentiality and unpredictability.

11. Ethical, Governance, and Professional Considerations

Randomization does not remove responsibility for outcomes. If a randomized sampling procedure excludes a protected group, the resulting model or decision system may be unfair even when the sampling code is statistically valid under a narrow objective. Data collection, sampling weights, missingness, and error rates should be audited across relevant populations.

For high-impact applications, designers should document the algorithm's guarantee, random source, error probabilities, fallback mechanisms, and monitoring plan. Approximate data structures should not silently determine eligibility, credit, employment, healthcare access, or legal status without an exact review path when required.

Security applications require cryptographically secure randomness where unpredictability matters. Ordinary pseudorandom generators may be sufficient for simulation but inadequate for keys, salts, tokens, or adversarially exposed hash seeds. Professional practice therefore distinguishes statistical randomness, computational unpredictability, and reproducibility.

12. Current Developments and Best Practices

Modern AI systems increasingly use randomized optimization, stochastic gradient methods, dropout, randomized sketches, approximate nearest-neighbor search, and sampling-based inference. Large language model training and distributed ML pipelines depend on careful control of random seeds, worker-level randomness, data shuffling, and nondeterministic hardware operations.

Best practice includes:

• State whether guarantees concern correctness, running time, approximation error, or all three.
• Use independent or appropriately controlled random streams for repeated trials.
• Analyze both expectation and tail behavior.
• Select parameters from a documented error and resource budget.
• Test against adversarial, skewed, and distribution-shifted data.
• Preserve reproducibility for research while protecting secrets in production.
• Add exact verification when a probabilistic filter can create costly errors.
• Monitor empirical collision rates, failure rates, and subgroup performance.
• Use cryptographically secure randomness for security-sensitive choices.

Chapter Summary

Randomized algorithms use random choices to simplify design, avoid adversarial behavior, scale computation, or obtain approximate answers. Las Vegas algorithms always produce correct answers but have random running times; Monte Carlo algorithms control time but permit a bounded probability of error. Their analysis relies on sample spaces, random variables, indicator variables, linearity of expectation, conditional expectation, variance, and concentration inequalities.

Randomized quicksort and quickselect illustrate how random pivots produce strong expected performance. Universal hashing controls expected collisions, while random sampling and reservoir sampling support large-scale estimation and streaming. Bloom filters, Count-Min Sketches, and cardinality estimators demonstrate how probabilistic data structures trade exactness for memory and speed. Effective use requires explicit guarantees, sound random sources, parameter selection, adversarial testing, and ethical oversight.

Key Terms

Randomized algorithm: An algorithm whose execution depends on internally generated random choices.

Las Vegas algorithm: A randomized algorithm that always returns a correct answer, with random running time.

Monte Carlo algorithm: A randomized algorithm with controlled running time that may produce an incorrect answer with bounded probability.

Failure probability: The probability that a randomized algorithm violates its correctness or accuracy requirement.

Random variable: A function assigning a numerical value to each outcome in a probability space.

Expectation: The probability-weighted average value of a random variable.

Indicator variable: A binary random variable representing whether an event occurs.

Linearity of expectation: The rule that the expectation of a sum equals the sum of expectations, even without independence.

Variance: A measure of the spread of a random variable around its expected value.

Concentration bound: An inequality that limits the probability of large deviation from an expected value.

Universal hashing: Hashing in which distinct keys collide with low probability over a randomly selected hash function.

Load factor: The ratio of stored keys to available hash-table slots.

Reservoir sampling: A streaming method for maintaining a uniform fixed-size sample from an unknown-length stream.

Bloom filter: A compact membership structure permitting false positives but, under standard use, not false negatives.

Count-Min Sketch: A compact frequency estimator that may overestimate counts because of hash collisions.

Monte Carlo estimation: Approximation of a quantity through repeated random sampling.

High-probability bound: A guarantee that an event holds except with a stated small probability.

Random seed: An initial value used to generate a reproducible pseudorandom sequence.

Probabilistic method: A technique proving existence by showing that a randomly constructed object has positive probability of satisfying a property.

Review Questions

Short Answer Questions

1. What is the essential difference between a Las Vegas and a Monte Carlo algorithm?

2. Why are indicator variables useful in expected-time analysis?

3. State the main idea of universal hashing.

4. What type of error can an ordinary Bloom filter produce?

5. Why is expectation alone insufficient to describe algorithm performance?

Long Answer Questions

1. Explain randomized quicksort and derive the intuition behind its expected O(n log n) comparison count.

2. Discuss Markov, Chebyshev, and Chernoff bounds and compare the assumptions and strengths of each.

3. Explain reservoir sampling and prove why each stream item has equal probability of appearing in the final reservoir.

4. Compare Bloom filters, Count-Min Sketches, and exact dictionaries in terms of memory, accuracy, and applications.

5. Develop a framework for selecting and validating a randomized algorithm for a production AI system.

Analytical / Application Questions

1. A system repeats an independent Monte Carlo test whose single-run failure probability is 0.1, accepting the result only when all runs agree. Explain how repetition changes the failure probability and identify the assumptions required.

2. A hash table stores n keys in m slots using separate chaining. Analyze how the load factor affects expected lookup cost and explain how randomized hashing helps against adversarial keys.

3. Design a streaming architecture that estimates frequent events, maintains a representative sample, and performs approximate membership checks. Specify the probabilistic structures, their possible errors, and how exact verification would be added.

22. Multiple Choice Questions with Answers

Question 1

Which statement correctly characterizes a Las Vegas algorithm?

A. It always returns a correct answer, but its running time may be random.

B. It always finishes in fixed time, but its answer may be incorrect.

C. It never uses random bits during execution.

D. It guarantees both fixed running time and zero error.

Correct Answer: A. It always returns a correct answer, but its running time may be random.

Question 2

Why can linearity of expectation be used for dependent indicator variables?

A. Dependence always disappears after conditioning.

B. Linearity of expectation does not require independence.

C. Indicator variables are independent by definition.

D. The variance of the sum is always zero.

Correct Answer: B. Linearity of expectation does not require independence.

Question 3

A Bloom filter used in its ordinary insertion-only form can produce which error?

A. False negatives only

B. Both false negatives and false positives necessarily

C. False positives but not false negatives

D. Neither false positives nor false negatives

Correct Answer: C. False positives but not false negatives

Question 4

What is the principal reason randomized quicksort has expected O(n log n) running time?

A. Every pivot gives two equal-sized subarrays.

B. The expected total number of element comparisons is O(n log n).

C. Its worst-case partition is always linear in recursion depth.

D. Randomness eliminates all recursive calls.

Correct Answer: B. The expected total number of element comparisons is O(n log n).

Question 5

If X is a nonnegative random variable, which inequality gives a general upper bound on Pr[X ≥ a] using only E[X]?

A. Markov's inequality

B. Chernoff's inequality only

C. The central limit theorem

D. The union bound only

Correct Answer: A. Markov's inequality

Question 6

In reservoir sampling with a reservoir of size k, when the ith stream item arrives for i > k, what is its selection probability?

A. 1/i

B. k/i

C. k/n, where n is known in advance

D. 1/k

Correct Answer: B. k/i

Question 7

A Count-Min Sketch with nonnegative updates generally has which frequency-estimation property?

A. It always underestimates the true frequency.

B. It is exact regardless of collisions.

C. It does not underestimate, but may overestimate because of collisions.

D. It returns only binary membership information.

Correct Answer: C. It does not underestimate, but may overestimate because of collisions.

Question 8

Which condition is most important when using repeated Monte Carlo trials to reduce failure probability?

A. All trials must use the same random seed.

B. The trials should be independent or have appropriately controlled dependence.

C. The input must be sorted before every trial.

D. The algorithm must be Las Vegas.

Correct Answer: B. The trials should be independent or have appropriately controlled dependence.

Question 9

Why can randomized hashing improve resistance to adversarial hash-table inputs?

A. It ensures that collisions are mathematically impossible.

B. It hides the selected hash behavior and limits expected collisions under suitable assumptions.

C. It removes the need for table resizing.

D. It makes every lookup worst-case constant time.

Correct Answer: B. It hides the selected hash behavior and limits expected collisions under suitable assumptions.

Question 10

A production system uses a probabilistic membership filter for financial eligibility decisions. What is the safest design?

A. Treat every positive filter result as final.

B. Ignore the filter's false-positive rate.

C. Use the filter for screening and perform exact verification before the final decision.

D. Replace the filter with a fixed seed to guarantee reproducibility.

Correct Answer: C. Use the filter for screening and perform exact verification before the final decision.