随机性, 概率和算法

一个问题

考虑一个问题: 洗一副牌: 然后按顺序依次查看它们. 在期望意义下, 两张连续的牌有相同花色的次数是多少? 用Python可以写为:

import numpy as np
import random
import pdb
deck = 13 * ['S', 'H', 'D', 'C']
consecutives = []
for _ in range(50000):
    shuffled_deck = random.sample(deck, len(deck))
    consecutives += [np.sum([shuffled_deck[i] == shuffled_deck[i+1] for i in range(len(deck) - 1)])]
print("Empirical mean: %f" % np.mean(consecutives))

运行完之后可以发现, 得到的值趋近于12. 这是为什么呢? 下面是证明过程.

有定理\(\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]\)(Linear of Expectations). 该定理除了需要\(X\)和\(Y\)满足存在期望意外不需要任何假设. 定义\(X_i\)为1, 如果第\(i\)张卡和第\(i+1\)张卡有相同的花色, 否则为0. \(X\)就是一个indicator random variables. 所以有\(X=\sum_{i=1}^{51}X_i\), 故有\(\mathbb{E}[X]=\mathbb{E}[\sum_{i=1}^{51}X_i]=\sum_{i=1}^{51}\mathbb{E}[X_i]=\sum_{i=1}^{51} \Pr[\text{i, i+1 have same suit}]\), 由于抽样是有放回的抽样, 所以这个概率很容易计算, 假设第\(i\)张牌拿到的是S花色, 那么相当于这个花色的牌少了一张, 还剩12张, 总牌数也少了1张, 所以下一张抽到S花色的概率是\(\frac{12}{51}\), 所以, \(\mathbb{E}[X]=51\times \frac{12}{51}=12\).

随机算法和标准算法的区别

与确定性算法在相同输入下总能产生相同结果不同, 随机算法由于引入了随机因素, 即使相同输入也可能产生不同输出. 随机算法不仅依赖输入本身, 还会在算法内部引入随机选择(或随机比特)来影响运行过程. 它并不意味着输入是随机的, 也不意味着我们需要在多次调用算法的平均情况下分析时间复杂度. 正确的理解是: 即使输入是最坏情况, 算法依然会通过自身的随机选择来影响最终结果和性能.

可以把算法A想象成同时接收输入x和一串来自\(\{0,1\}^*\)的随机位R. 由于A是随机的, 这可能意味着以下情况之一或其组合: * 算法在输入x上的运行时间τ_A(x; R)是随机的, 并取决于随机位R * 算法对输入x的输出A(x; R)是随机的, 可能因R不同而产生不同结果 * 其他方面(例如算法的内存使用量)也可能取决于R * 或上述所有情况的任意组合.

通常,我们会在最坏情况输入x和均匀随机的R下分析随机算法A.需要关注的两个关键问题是:(1)A的输出是否总是正确?或者,在随机位R的不同选择下,A是否能以高概率给出正确结果?(2)A的运行时间是否始终有界?或者,在随机位R的不同选择下,A的运行时间是否能以高概率或在期望意义上保持有界? 如下面的两个随机算法的侧重点就不同.

两个随机算法

这里先介绍两个随机算法, Las Vegas算法:算法的输出总是正确,但其运行时间仅在期望意义上有界. Monte-Carlo算法:算法的输出只能以高概率正确,但其运行时间通常有一个明确的上界.

为什么要随机化

1.避免病态的极端情况: 随机化可以帮助算法在面对某些特定输入时减少最坏情况出现的概率; 2.更快地获得近似结果: 通过随机化, 我们常常能在较短地时间内得到可以接受地解; 3.提供可预测的期望行为: 虽然时随机, 但是从统计或者概率角度可以分析其行为, 从而在大概率上预测结果; 4.实现更快, 更简单的算法: 随机化能够在某些问题上降低算法复杂度, 并简化实现; 5.绕过不可能性结果或者打破平局: 在一些确定性条件下无法完成的任务, 借助随机化可以获得概率上的可行解; 6.密码学与隐私保护: 高质量的随机数时安全加密和隐私保护的核心.

另一个问题

给定一个n位整数,判断它是否是素数. 有一种名为AKS的算法能够解决这个问题. 自2002年起, 该算法以多项式时间(~O(n^12))运行, 后续改进为~O(n^6). 它是首个无需依赖数学猜想(如广义黎曼猜想)就能在多项式时间内判断给定整数是素数还是合数的算法. 但是, 这个算法又复杂又慢, 实际上, 可以使用随机算法来解决这个问题, 自从1980年, Miller-Rabin等人就提出了一种随机算法, 时间复杂度为\(O(n^2)\).

快排

给定一个包含n个不同数字的数组A, 排序A. 已经存在一些deterministic的排序算法, 时间复杂度为\(O(n\log n)\). 并且, 每一个(comparison-based)排序算法一定有一个最差的时间复杂度\(\Omega(n\log n)\).

快排(Quick Sort)时一种deterministic的排序算法, 时间复杂度为\(O(n^2)\). 其伪代码可以表示为:

Require: Input array A of size n
1: if n <= 1 then return A
2: Select an index 1 <= i <= n, and let p <- A[i] be the pivot
3: Partition A into 3 subarrays: A1 (elements smaller than p), A2 (equal to p), and A3 (greater than p) -> O(n) time
4: Recursively call QuickSort on A1 and A3 to sort them
5: Merge the (sorted) A1, A2, A3 into A -> O(n) time
6: return A

这个算法非常的简洁, 并且在实际中表现较好, 但是它的时间复杂度和\(O(n\log n)\)相比比较高, 所以, 有一个它的随机算法衍生版, 叫做随机快排, 可以把时间复杂度缩短到\(O(n\log n)\).

快排一个关键的问题就是如何选取pivot, 并且事实上, 整个算法的时间复杂度都依赖于如何选择pivot. naive的选择方式是选择\(i=\lceil n/2\rceil\), 这会导致时间复杂度为\(O(n^2)\). 一个更加好的方法是使用一个线性复杂度的算法选择中位数作为pivot, 这会使得时间复杂度缩短为\(O(n\log n)\), 但是, 这会导致算法过于复杂并且在实际情况下并没有想象中的那么快.

但是我们发现选取pivot其实可以用一种随机的策略, 例如, 均匀选取pivot, 在上面的第2步, 从\(\{1, 2, ..., n\}\)中随机选取\(i\), 这就是随机快排. 下面, 来证明它的时间复杂度是\(O(n\log n)\).

它的时间复杂度满足\(T(n)=\mathbb{E}[T(|A_1|)]+\mathbb{E}[T(|A_2|)]+O(n)\). 我们假设选择的是第\(k\)个元素, 选中那个元素的概率为\(\frac{1}{n}\), 所以上面的复杂度可以写为\( T(n) = c n + \frac{1}{n} \sum_{k=1}^n \Bigl(T(k-1) + T(n-k)\Bigr) = c n + \frac{1}{n} \sum_{k=0}^{n-1} T(k) + \frac{1}{n} \sum_{\ell=0}^{n-1} T(\ell) =c n + \frac{2}{n} \sum_{k=0}^{n-1} T(k)\), 那么, 怎么才能解出\(T(n)=c n + \frac{2}{n} \sum_{k=0}^{n-1} T(k)\)呢?