📚 Investigation 1 - A Computer-Based Random Sampler | 探究1 - 计算机随机采样器
Random sampling is a fundamental technique in computer science, used in simulations, statistical analysis, Monte Carlo methods, gaming, cryptography, and randomised algorithms. This investigation explores how computers generate randomness, the algorithms behind random sampling, and how we can build a reliable random sampler programmatically. We will examine pseudorandom number generators, methods for sampling with and without replacement, weighted sampling, and the practical implementation of a random sampler using Python, a language commonly adopted in the IB Computer Science curriculum.
随机采样是计算机科学中的一项基本技术，广泛应用于模拟、统计分析、蒙特卡洛方法、游戏、密码学和随机化算法中。本调查探讨计算机如何生成随机性、随机采样背后的算法以及如何以编程方式构建可靠的随机采样器。我们将研究伪随机数生成器、有放回和无放回的采样方法、加权采样，以及使用IB计算机科学课程中常用的Python语言实现随机采样器的实践。
1. The Need for Randomness in Computing | 计算中对随机性的需求
Many computational problems rely on randomness. For instance, randomised quicksort uses random pivot selection to achieve expected O(n log n) performance. Simulations of physical systems, like Brownian motion, require random sampling from probability distributions. In cryptography, the security of keys depends on truly unpredictable random numbers. Game development uses randomness to create non-deterministic behaviours, and statistical sampling is used to estimate population parameters without processing the entire dataset.
许多计算问题依赖于随机性。例如，随机化快速排序使用随机枢轴选择来达到期望的 O(n log n) 时间复杂度。物理系统的模拟，如布朗运动，需要从概率分布中随机采样。在密码学中，密钥的安全性取决于真正不可预测的随机数。游戏开发利用随机性来创建非确定性行为，统计抽样则用于在不处理整个数据集的情况下估计总体参数。
In the context of the IB Computer Science course, understanding random sampling allows students to appreciate how programs can model uncertainty and make decisions based on probability. It also introduces the concept of deterministic vs. non-deterministic systems, which is central to algorithm analysis.
在IB计算机科学课程的背景下，理解随机采样能让学生体会程序如何对不确定性进行建模以及基于概率做出决策。它也引入了确定性系统与非确定性系统的概念，这是算法分析的核心。
2. Pseudorandom Number Generators (PRNGs) | 伪随机数生成器
Computers are deterministic machines; generating true randomness is challenging. Instead, they use algorithms called pseudorandom number generators (PRNGs) to produce sequences of numbers that appear random. The most common PRNG is the linear congruential generator (LCG), which generates the next number Xₙ₊₁ from the previous Xₙ using the recurrence:
计算机是确定性机器；生成真正的随机性具有挑战性。取而代之的是，它们使用称为伪随机数生成器（PRNG）的算法来生成看起来随机的数字序列。最常见的PRNG是线性同余生成器（LCG），它通过递推公式从前一个数 Xₙ 生成下一个数 Xₙ₊₁：
Xₙ₊₁ = (a × Xₙ + c) mod m
where a is the multiplier, c the increment, and m the modulus. All parameters are positive integers. The initial value X₀ is called the seed. By choosing appropriate constants, the LCG can produce a long period before repeating. However, the sequence is entirely determined by the seed, which makes it predictable if the seed is known.
其中 a 是乘数，c 是增量，m 是模数，所有参数均为正整数。初始值 X₀ 称为种子。通过选择合适的常数，LCG 可以在重复之前产生很长的周期。然而，序列完全由种子决定，因此如果种子已知，序列就是可预测的。
In Python, the random module uses the Mersenne Twister algorithm, a more sophisticated PRNG with an extremely long period (2¹⁹⁹³⁷−1) and good statistical properties. The seed can be set manually via random.seed() or automatically from the system time.
在Python中，random 模块使用梅森旋转算法，这是一种更复杂的PRNG，具有极长的周期（2¹⁹⁹³⁷−1）和良好的统计特性。可以通过 random.seed() 手动设置种子，或从系统时间自动获取。
3. True Random Number Generation (TRNG) | 真随机数生成
While PRNGs are sufficient for most applications, cryptographic systems require non-deterministic random numbers. True random number generators (TRNGs) harvest entropy from physical phenomena, such as thermal noise, radioactive decay, or mouse movements. Operating systems often collect environmental noise to provide a source of randomness, accessible via /dev/random on Unix-like systems or CryptGenRandom on Windows.
尽管PRNG对于大多数应用已经足够，但密码系统需要非确定性的随机数。真随机数生成器（TRNG）从物理现象中收集熵，例如热噪声、放射性衰变或鼠标移动。操作系统通常收集环境噪声以提供随机源，在类Unix系统上可通过 /dev/random 访问，在Windows上通过 CryptGenRandom 访问。
In Python, the secrets module was introduced for generating cryptographically secure random numbers suitable for managing secrets such as passwords, tokens, and account authentication. It uses the best available entropy source provided by the operating system, ensuring unpredictability.
在Python中，secrets 模块被引入用于生成加密安全的随机数，适用于管理密码、令牌和账户认证等密钥。它使用操作系统提供的最佳熵源，确保了不可预测性。
4. Sampling from a Uniform Distribution | 从均匀分布采样
. A PRNG typically produces a floating-point number in [0.0, 1.0) by dividing Xₙ by m. Scaling and shifting can then map it to any desired interval.
最简单的随机采样形式是从连续区间 [a, b] 或一组离散整数中均匀抽取一个数。对于均匀连续分布，概率密度函数为 f(x) = 1/(b−a)。PRNG通常通过将 Xₙ 除以 m 来生成一个在 [0.0, 1.0) 范围内的浮点数。然后通过缩放和平移可以将其映射到任意所需区间。
ng how these functions use the underlying PRNG helps in building reliable random samplers.
对于在闭区间 [low, high] 内均匀采样整数，Python 提供了 random.randint(low, high)。对于实数，random.uniform(a, b) 返回一个浮点数 N，满足 a ≤ N ≤ b。理解这些函数如何使用底层的PRNG，有助于构建可靠的随机采样器。
5. Sampling without Replacement: Fisher-Yates Shuffle | 无放回采样：Fisher-Yates洗牌
to randomly select k distinct items from a population of size n (k ≤ n). This is sampling
Published by TutorHao | IB Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图