通过随机索引搜索数组时的预期循环迭代量

Question

让我们说我们有一个大小的数组。它有1个作为其第一个索引和n作为其最后一个索引。它包含一个值x，其中x在a中发生k次，其中1 <= k <= n

如果我们有一个搜索算法如此：

while true:
  i := random(1, n)
  if A[i] == x
    break

.

随机（a，b）从a均匀地从a均匀地拾取一个数字

从此我们知道找到x和终止程序的机会是每次迭代的k / n。然而，我想知道的是迭代次数的预期值或更具体地说，在这个程序中访问了阵列的次数给出了如上所述的数组a。

Answer 1

让 $ n $ 是几何r.v.返回返回数组被访问的次数以搜索元素， $ a [x] $ ，直到我们成功找到它。我们想知道 $ \ mathbb {e} [n] $ 。

我们可以将循环的迭代视为一个IID伯努利试验的序列，每个试验概率 $ p $ 成功， $ q= 1 - P $ 失败。鉴于这个问题，我们想知道需要多少试验来获得“成功”，该试验将找到元素 $ a [x] $ 因此，while循环终止。

由于 $ \ pr \ {n= k \}= q ^ {k-1} p $ ，我们有那个 $ \ mathbb {e} [n]=sum \ limits_ {k= 1} ^ \ idty k \：q ^ {k-1} p $ 。

因此， $ \ mathbb {e} [n]=dfrac 1p $ 其中 $ p=dfrac kn $ so $ \ mathbb {e} [n]=dfrac nk $ 。

如此，它需要 $ \ dfrac nk $ 访问，然后在找到元素之前， $ a [x] $ 。