CLRS -随机搜索-如何计算预期的拾取数量？

Question

这是CLRS问题。这个问题来自第三版的CLRS书籍: 5-2-b。

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

Answer 1

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

这个随机变量有一个众所周知的分布。它是给定成功概率参数p的geometric distribution。几何分布的期望值为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 to n的Pr{k失败}的和。因此，E(X)=n(n+1)/2(n-1)。