algorithm - CLRS - 随机搜索 - 如何计算预期的选择数量？

Question

这是 CLRS 问题。问题来自第三版 CLRS 书：5-2-b。

随机搜索是一种算法，您必须随机选择一个元素并将其与搜索的元素进行比较。如果相等，我们需要停止。现在，假设您恰好有一个索引为 i 的元素，使得 A[i]=x（x 是数组中的搜索元素）。在找到 x 之前，我们必须选择 A 的预期索引数是多少？此外，当我们有超过 1 个等于 x 的索引值时，我们如何找到预期的索引数量？

Answer 1

我们可以定义一个随机变量 X = 在选择目标元素之前的迭代次数。如果您将术语概括为“迭代”被称为“试验”而“选择目标元素”被称为“成功”，那么您有 X = 成功前的试验次数。

这个随机变量有一个众所周知的分布。它是给定成功概率参数 p的几何分布。几何分布的期望值为 E(X) = 1/p。

要将几何分布应用于问题，必须确定成功概率 p。对于只有一个索引包含目标值的情况，p = 1/n 其中 n 是搜索到的集合的大小。所以在这种情况下，E(X) = n。

对于任意数量的索引映射到目标值的一般情况，p = m / n 其中 m 是映射到目标值的索引的数量。所以在这种情况下，E(X) = n / m。

Answer 2

假设在我们找到元素 x 之前有 k 次失败。所以 Pr{k 失败}=k/(n-1)。现在 E(X)=对于 k=1 到 n 的 Pr{k 失败} 的总和。因此，E(X)=n(n+1)/2(n-1)。