Количество ожидаемых итераций цикла при поиске в массиве по случайному индексу

Question

Допустим, у нас есть массив A размера n.Он имеет 1 в качестве первого индекса и n в качестве последнего индекса.Он содержит значение x, причем x встречается k раз в A, где 1<=k<=n

Если у нас есть алгоритм поиска, подобный следующему:

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

случайный (a, b) выбирает число равномерно от a до b

Из этого мы знаем, что шансы найти x и завершить программу равны k/n с каждой итерацией.Однако то, что я хотел бы знать, - это каково было бы ожидаемое значение для количества итераций или, более конкретно, количества обращений к массиву в этой программе, учитывая массив A, как описано выше.

Answer 1

Позволь $N$ быть геометрическим R.V.который возвращает количество обращений к массиву для поиска элемента, $A[x]$ пока мы успешно не найдем его.Мы хотим знать $\mathbb{E}[N]$.

Мы можем рассматривать итерации цикла while как последовательность IID-испытаний Бернулли, каждое из которых имеет определенную вероятность $p$ о преуспевании, и $q = 1 - p$ о неудаче.Учитывая этот вопрос, мы хотим знать, сколько испытаний необходимо для достижения "успеха", который заключался бы в нахождении элемента $A[x]$ таким образом, while цикл завершается.

С тех пор, как $\Pr\{N = k\} = q^{k-1}p$, у нас есть это $\mathbb{E}[N] = \sum\limits_{k = 1}^\infty k \:q^{k-1}p$.

Таким образом, $\mathbb{E}[N] = \dfrac 1p$ где $p = \dfrac кн$ так $\mathbb{E}[N] = \dfrac nk$.

Таким образом, в среднем это занимает $\dfrac nk$ обращается до того, как мы найдем элемент, $A[x]$.