Random selection of a fixed number of distinct items from an unknown-length sequence is one of the intriguing challenges in computer science. This task becomes particularly interesting because it needs to be completed in a single iteration. This article explains this process in detail, providing both technical explanations and practical examples for clarity.

Problem Overview

Given a sequence of unknown length, the objective is to select N distinct items randomly with uniform probabilities. The challenge lies in the unknown length, which means one cannot make multiple passes through the data, nor can one store more than N items at any point due to memory constraints.

Reservoir Sampling Algorithm

Reservoir Sampling is an efficient algorithm that helps achieve the task in one pass. The most common version is the Reservoir Sampling with size N. Here’s how it works:

Steps for Reservoir Sampling

1. Initialization:
   Create an array R of size N, which will be the reservoir to store the selected items. Initialize it with the first N items from the sequence.
2. Sampling:
   For each subsequent item in the sequence (i.e., from the N+1-th item onwards):
   • Generate a random index j such that 0 ≤ j ≤ current_index.
   • If j is less than N, replace the j-th item in the reservoir with the current item from the sequence.

Technical Explanation

The logic behind step 2 is based on the probability guarantee that each item from the sequence has an equal chance to be included. For instance, the N+1-th item has an N/(N+1) probability of not being included in the reservoir, allowing the initially chosen items to be retained randomly. In general, the probability ensures uniform sampling across the entire sequence, no matter its length.

Practical Example

Assume you need to select 3 items from the following sequence: [10, 20, 30, 40, 50, 60, 70, 80]. Following reservoir sampling:

1. Initialize the reservoir with the first 3 items: [10, 20, 30].
2. For item 40 at index 3, generate j such that 0 ≤ j ≤ 3. If j = 2, replace item at index 2 in the reservoir: [10, 20, 40].
3. Continue this process for items at subsequent indices.
4. The resulting reservoir (3 items) is your uniformly random sample.

Key Points of Reservoir Sampling

Additional Considerations

Real-world Applications

• Data Stream Processing: Ideal for operations like sampling network packets or transactions in financial systems where data hits continuously.
• Online Algorithms: Suitable for scenarios where data is uncertain, such as web analytics, where pages or clicks arrive randomly.

Limitations

• Reservoir Sampling assumes a fixed N which might not adapt to dynamics where N could change based on rules or conditions.
• Its randomness solely relies on the quality of the pseudo-random number generator, affecting the uniformity of the selection.

Conclusion

Reservoir Sampling provides an effective and efficient means for selecting random samples from a data stream of unknown size. Its capability to perform with minimal storage and a single-pass requirement makes it suitable for vast applications, especially in environments constrained by memory or processing speed. By understanding its mechanism, users can harness its power for various real-world scenarios.