51、随机采样与图模型算法解析

随机采样与图模型算法解析

1. 随机采样方法

随机采样在很多领域都有重要应用，这里介绍两种常见的随机采样方法：排他采样和基于拒绝的采样。

1.1 排他采样（Exclusive Sampling）

排他采样用于从长度为 $M$ 的给定序列 $x[]$ 中随机且无放回地提取 $m$ 个数字。其实现思路简单，每次从剩余的 $K$ 个元素中均匀随机采样一个元素，将其与序列 $x[]$ 的最后一个元素交换，然后将序列 $x[]$ 的有效大小减 1。以下是具体的算法实现：

Algorithm 25 exclusive_sampling() Input: x, m Output: v 1: K ← M 2: for all i in 0 to m - 1 do 3: ξ ← RAND(0, 1) 4: j ← ⌊Kξ⌋ 5: v[i] ← x[j] 6: tmp ← x[j] 7: x[j] ← x[K] 8: x[K] ← tmp 9: K ← K − 1 10: end for

该算法的时间复杂度为 $O(m)$，但缺点是会修改输入序列 $x[]$ 的顺序。若 $m$ 远小于 $M$，复制 $x[]$ 到临时向量的方法效率不高。

1.2 基于拒绝的排他采样（Exclusive Sampling with Rejection）

为避免修改输入序列，可采用基于拒绝的采样算法。该算法通过不断随机采样，若采样的数字已存在则拒绝并重新采样，直到得到 $m$ 个不同的数字。