Warum wird 1 zur führenden Nullzählung im Hyperloglog-Algorithmus hinzugefügt

Question

Wenn es im Bitmuster von Hash eine Anzahl führender Nullen gibt, warum wird die geschätzte Größe als 2 ^{k + 1} betrachtet? sollte es nicht sein 2 ^k? die Wahrscheinlichkeit k von Null aufweist führenden sollte 1/(2 ^k) sein und daher sollte die Größe 2 ^k

ich immer korrekte Schätzung der Größe bekommen In meinem Code sein, wenn ich k + 1 anstelle von k verwenden . Aber ich verstehe die Logik dahinter nicht.

Answer 1

Die Intuition, nach der Sie suchen, ist, dass der Algorithmus auf der Wahrscheinlichkeit beruht, das gesamte Bitmuster am Anfang des Hashs (k Nullen, gefolgt von einer 1) zu sehen, nicht nur die Nullen.

Der schwierigere Teil ist von dort bis zur Schätzung der Kardinalität bei 2 ^{k + 1}. Leider ist der formale Beweis dafür nicht einfach. Tatsächlich ist der größte Teil der ursprünglichen Originalarbeit, die die Methode eingeführt hat (Flajolet und Martin, Probabilistische Zählalgorithmen für Datenbankanwendungen, http://algo.inria.fr/flajolet/Publications/FlMa85.pdf), dem Nachweis gewidmet, dass die damit berechnete Schätzung gut ist. Nachfolgende Arbeiten (die Protokolle LogLog und HyperLogLog) haben ähnliche Beweise für ihre verbesserten Schätzungen.

Hoffe, dass hilft!

Answer 2

Nach Wahrscheinlichkeitstheorie sind Sie richtig! Sie würden erwarten, 2 ^k Beobachtungen (im Durchschnitt) gemacht zu haben, bevor Sie einen Wert mit k führenden Nullen beobachtet haben.

Der Grund, warum Ihre Schätzung das Doppelte ist, könnte sein, dass Ihre Zufallsfunktion (oder Hash-Funktion) einen vorzeichenbehafteten int liefert, der immer positiv ist und eine führende Null immer vorhanden ist. Dies sollte Ihre Chancen, einen Wert mit k führenden Nullen zu sehen, ungefähr verdoppeln. Deshalb erhalten Sie die richtige Antwort, wenn Sie 2 ^{k + 1} anstelle von 2 ^k verwenden.

Answer 3

k führende Nullen bedeuten, dass die ersten k Bits Nullen sind, denen ein Ein-Bit folgt. (Andernfalls hätten wir mehr als k führende Null-Bits.) Daher sind k führende Nullen tatsächlich durch eine Bitsequenz der Länge (k + 1) gekennzeichnet, für die die Wahrscheinlichkeit 1/2^(k + 1) ist.