Я изучаю алгоритм потоковой передачи для Count Sketch.
Мой профессор вводит 3 алгоритма,
один это
<Generate r in >
Update(i, c)
s = s + ri c
Estimate(i)
return ri s
второй это
Initialization
<Generate r in {-1, 1}^n>
Update(i, c)
t = h(i)
s(t) = s(t) + ri c
Estimate(i)
t = h(i)
return ri s(t)
И третье - это вычисление n одного и того же алгоритма и получение среднего значения.
Я понимаю, что сначала просто обновите счетчик, во-вторых, можно обновить значение с помощью хэш-функции.
Но представьте концепцию дисперсии и ожидания. Может быть, для показа, что оценка верна?
Профессор предлагает этот ресурс, но мне нелегко
https://www.cs.rutgers.edu/~farach/pubs/FrequentStream.pdf
Я слежу за этим
https://courses.cs.washington.edu/courses/cse522/14sp/lectures/lect05.pdf
где на странице 4 объясняется дисперсия моего второго алгоритма.
Кто-нибудь может прояснить мне связь между дисперсией и этим агорифмом?