Количество ожидаемых итераций цикла при поиске в массиве по случайному индексу
Вопрос
Допустим, у нас есть массив 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, как описано выше.
Решение
Позволь $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]$.