认为指标随机变量 X k和值T(max(k - 1, n - k))是独立的。
答案是
当我们知道 k-1 和 nk 的最大值时,X_k 等于 1 的概率不变。换句话说,Pr{X_k =a| max(k-1, nk)=m} = Pr{X_k=a} for a=0,1 and m=k-1, nk 所以 X_k 和 max(k-1, nk) 是独立的。
现在,根据我的理解,k-1 是子数组的下侧,其中数组 < k 的每个元素和 nk 是数组的上侧,其中数组的每个元素 > k。所以我们可以将 k 视为支点。X_k 是指示随机变量,当子数组 A[p..q] 恰好有 k 个元素时,X_k = 1。[参考 Cormen 的算法介绍第 9 章。第 9.2 节:预期线性时间的选择]。
现在,当我们知道 k-1 和 nk 的最大值时,答案是 X_k=1。我相信 k-1 的最大值将是数组的第 k-1 个元素,而 nk 的最大值是数组的第 n 个元素。最大元素与指标随机变量 1 的关系是什么?
Pr{X_k=a} 给定 max(k-1, nk)
max(k-1, nk) 表示最大元素应该在第 n 个位置。
另外,我不清楚a和m的定义。
我在 CLRS 解决方案链接问题 9.2-2 的答案中找到了这个问题。
虽然答案是在链接中定义的,但我相信对这个答案的更多解释会更有帮助。