随机算法中的循环不变式

排序算法中的循环不变式中总结了循环不变式在排序算法中的运用,循环不变式还可以用于随机算法,本文总结循环不变式在随机算法中的运用。

随机算法

随机算法的数学基础是概率论,如果我们能够证明某个算法服从特定的概率公式,那么我们可以认为此算法具备均匀随机分布的特征。

问题:如何产生随机数

给定一个有序的输入,如A[1…n],如何通过一个算法,输入有序的A,返回一个A的集合Ua,Ua中的所有子序列是均匀随机分布的。

思路

我们确定序列A[1…n]是排列P(n,n)序列集合中的某一个子序列,而排列P(n,n)的所有子序列是符合随机均匀分布的。假设特定的子序列[a1,a2,…an]被包含在P(n,n)集合中的事件为E(x),那么E(x)发生的概率为:

\frac{1}{n!}

因此将A[1…n]转变随机均匀分布的方法是求得A[1…n]的所有子序列,然后随机取一个。

解法1

伪代码

def premute_sorting(A):
	n = len(A)

	# 从P(n,n)中随机选择一个子序列
	P[n] <- 0
	for i = 0 to n:
		P[i] = random(1, n**3)  

	# 以P[1...n]为key,将A[1...n]排序
	# 使用选择排序法
	for i = 1 to n:
		for j = i to n:
			# 从j到n序列中找到一个最小值所在位置k
		# 交换P[i]与P[k]的值
		# 交换A[i]与A[k]的值

循环不变式

算法本身就是一个选择排序算法,但是我们这里需要证明的是通过排循一个随机的无序序列P[1…n]过程中产生的数组下标序列Index[1…k]是随机均匀分布的,因此循环不变式为:在i=1 to n的循环中,序列Index[1…k]为P(n,k)排列序列集合中的一个子序列的概率:

\frac{(n-k)!}{n!}

证明

初始i=1

当i=1时,此时Index[1]的值为随机序列P(n,1)中的一个值,Index[1]的值为[1,n]的某个值的概率为:

\frac{(n-1)!}{n!}=\frac{1}{n}

不变式成立。

保持

假设当i=m时,序列Index[1…m]为P(n,m)排列序列集合中的一个子序列的概率**:

\frac{(n-m)!}{n!}

当i=m+1时,序列Index[1…m,m+1]是P(n,m+1)排列序列集合中的一个子序列的概率是多少? 我们设定序列Index[1…m]为P(n,m)的一个子序列的事件为E1,概率为P(E1)。此时事件E1已经发生,再假定在E1已经发生了的前提下,Index序列中下一个值Index[m+1]发生的事件为E2,概率为P(E2),那么序列Index[1…m,m+1]是P(n,m+1)排列序列集合中的一个子序列的概率是:

P({E1}\cap{E2})

根据概率公式,上述等式等价于:

P({E1}\cap{E2})=P(E1)P(E2|E1)

P(E1)的值为:

\frac{(n-m)!}{n!}

P(E2|E1)的值为:

\frac{1}{(n-m)}

(从剩余的n-m个元素中随机挑选一个) 那么:

P({E1}\cap{E2})=P(E1)P(E2|E1)=\frac{(n-m)!}{n!}\frac{1}{(n-m)}=\frac{(n-(m+1))!}{n!}

因此,序列Index[1…m,m+1]是P(n,m+1)排列序列集合中的一个子序列的概率是:

\frac{(n-(m+1))!}{n!}

结束

当i=n,序列Index[1…n]是P(n,n)排列序列集合中的一个子序列的概率为:

\frac{(n-n)!}{n!}=\frac{1}{n!}

证明完毕。

解法2

求序列A[1…n]的随机排列的另外一个方法,逻辑相对简单。

伪代码

def premute_inplace(A):
	for i = 1 to n:
		swap(A[i], A[random(i,n)])

循环不变式

这个算法中的不变式:子序列A[1…i]为序列A的排列A(n,i)集合中的某个子序列的概率为:

\frac{(n-i)!}{n!}

证明方法与解法1类似。

代码参考

algorithm

关注公众号获得更多云最佳实践