Начнем с простого вопроса: если вы трижды подбросили честную монету, какова вероятность того, что вы получите три решки подряд? Это будет 1/8, так как вероятность выпадения решки у каждой монеты составляет 50/50.
Теперь мы можем спросить - если бы вам пришлось несколько раз подбрасывать монету три раза, примерно сколько групп из трех подбрасываний Вам нужно, чтобы один из них получил три решки подряд? Что ж, поскольку вероятность получить три решки составляет 1/8, можно ожидать, что вам придется повторить это восемь раз. Фактически, это как раз ожидаемое количество раз, которое вам нужно будет сделать это.
В более общем плане, сколько раз вам нужно будет подбросить серию из k монет, прежде чем вы ожидаете увидеть k последовательных хвостов ? Вероятно, это примерно 2 k раз, так как есть 1/2 k шанс получить k последовательных хвостов.
Теперь предположим, что кто-то подходит к вам и говорит: «Эй ! Я подбросил монетку десять раз подряд и получил десять решек подряд ». Вы были бы немного подозрительны к этому утверждению, если бы подумали, что человек только что однажды попытался подбросить десять монет, поскольку с одной попытки у вас есть примерно 1/1000 шанс получить десять последовательных решек. Но если вы представите, что этот человек пытался подбросить десять монет подряд над и над и над снова, теперь это будет немного более правдоподобно. Вы могли бы сказать в ответ что-то вроде «Вау! Тебе, наверное, приходилось подбрасывать эти монеты, что, 2 10 раз?» И хотя вы можете быть далеко - может быть, им просто действительно повезло - у вас все еще, вероятно, есть довольно хорошая оценка того, сколько попыток подбрасывания монеты им пришлось сделать.
Спасибо за то, что потворствовали этому маленькому уходу. Вернемся к Флажолет-Мартен. : -)
Оценщик Flajolet-Martin работает путем хеширования элементов и отслеживания количества нулевых битов, которые появляются в конце каждого из хешей. Думайте о хэшах не как о числах, а как о последовательностях нулей и единиц, которые кодируют серию подбрасываний монеты. Например, ha sh 0110 будет интерпретироваться как «решка, решка, решка, решка».
В этой модели идея «посчитать, сколько нулей в конце» оказывается по существу эквивалентной чтобы «подсчитать, сколько решек подряд было перевернуто». И, используя рассуждения выше, очень маловероятно, что вы увидите большое количество хвостов, поэтому, если вы делаете видите много хвостов подряд, это, вероятно, означает, что вы видели много предметов.
Конечно, как вы отметили, это не идеально, и вам может не повезти, имея код ha sh с огромной серией последовательных нулей сзади, даже если вы я видел только небольшое количество предметов. Вот что произошло в вашем примере выше. Чтобы противодействовать этому, вы можете запустить несколько копий Flajolet-Martin параллельно и объединить результаты вместе, чтобы одна неверная оценка не испортила общий результат. (Это, плюс еще немного, дает вам знаменитую оценку HyperLogLog!)
Надеюсь, это поможет!