Ytukyg

I have problem understanding how the math works in the hyperloglog algorithm. More specifically, I have trouble seeing how the author get formula 5 from formula 4, in the HyperLogLog paper, page 132.

The formula 4 says

$mathbb{E}_n(Z) = sum_{k_1,...,k_mgeq 1}frac{1}{sum_{j=1}^m2^{-k_j}}sum_{n_1+...+n_m=n}begin{pmatrix}n\n_1,...,n_mend{pmatrix}frac{1}{m^n}prod_{j=1}^mgamma_{n_j,k_j}$, where $gamma_{n_j,k_j} = (1-frac{1}{2^{k_j}})^{n_j}-(1-frac{1}{2^{k_j-1}})^{n_j}$

Then the paper assumes $n$ satisfies Poisson distribution of rate $lambda$, $mathbb{P}(N=n) = e^{-lambda}frac{lambda^n}{n!}$, and get formula 5

$mathbb{E}_{P(lambda)}(Z) = sum_{ngeq 0}mathbb{E}_n(Z)e^{-lambda}frac{lambda^n}{n!}=sum_{k_1,...,k_mgeq 1}frac{1}{sum_{j=1}^m2^{-k_j}}prod_{j=1}^mg(frac{lambda}{m2^{k_j}})$, where $g(x) = e^{-x}-e^{-2x}$.

The paper says it is obtained by simple series rearrangements. However I fail to understand how this is done. Any help is greatly appreciated!

Here is the derivation which uses the identity $e^x = sum_{ngeq 0} frac{x^n}{n!}$:

begin{aligned}
mathbb{E}_{P(lambda)}(Z) &= sum_{ngeq 0}e^{-lambda}frac{lambda^n}{n!}mathbb{E}_n(Z)
\
&=
sum_{ngeq 0}e^{-lambda}frac{lambda^n}{n!}sum_{k_1,...,k_mgeq 1}frac{1}{sum_{j=1}^m2^{-k_j}}sum_{n_1+...+n_m=n}begin{pmatrix}n\n_1,...,n_mend{pmatrix}frac{1}{m^n}prod_{j=1}^mgamma_{n_j,k_j}
\
&=
e^{-lambda}sum_{ngeq 0}sum_{k_1,...,k_mgeq 1}frac{1}{sum_{j=1}^m2^{-k_j}}sum_{n_1+...+n_m=n}frac{lambda^{n_1+n_2+cdots n_m}}{n_1!n_2!cdots n_m!}frac{1}{m^n}prod_{j=1}^mgamma_{n_j,k_j}
\
&=
e^{-lambda}sum_{k_1,...,k_mgeq 1}frac{1}{sum_{j=1}^m2^{-k_j}}sum_{ngeq 0}sum_{n_1+...+n_m=n}frac{left(frac{lambda}{m}right)^{n_1+n_2+cdots n_m}}{n_1!n_2!cdots n_m!}prod_{j=1}^mgamma_{n_j,k_j}
\
&=
e^{-lambda}sum_{k_1,...,k_mgeq 1}frac{1}{sum_{j=1}^m2^{-k_j}}sum_{n_1geq 0}sum_{n_2geq 0}cdotssum_{n_mgeq 0}frac{left(frac{lambda}{m}right)^{n_1+n_2+cdots n_m}}{n_1!n_2!cdots n_m!}prod_{j=1}^mgamma_{n_j,k_j}
\
&=
e^{-lambda}sum_{k_1,...,k_mgeq 1}frac{1}{sum_{j=1}^m2^{-k_j}}prod_{j=1}^msum_{n_jgeq 0}frac{left(frac{lambda}{m}right)^{n_j}}{n_j!}gamma_{n_j,k_j}
\
&=
e^{-lambda}sum_{k_1,...,k_mgeq 1}frac{1}{sum_{j=1}^m2^{-k_j}}prod_{j=1}^msum_{n_jgeq 0}frac{left(frac{lambda}{m}right)^{n_j}}{n_j!}left((1-frac{1}{2^{k_j}})^{n_j}-(1-frac{1}{2^{k_j-1}})^{n_j}right)
\
&=
e^{-lambda}sum_{k_1,...,k_mgeq 1}frac{1}{sum_{j=1}^m2^{-k_j}}prod_{j=1}^m
left(
left(
sum_{n_jgeq 0}frac{left(frac{lambda}{m}(1-frac{1}{2^{k_j}})right)^{n_j}}{n_j!}right)
-
left(
sum_{n_jgeq 0}frac{left(frac{lambda}{m}(1-frac{1}{2^{k_j-1}})right)^{n_j}}{n_j!}right)
right)
\
&=
e^{-lambda}sum_{k_1,...,k_mgeq 1}frac{1}{sum_{j=1}^m2^{-k_j}}prod_{j=1}^m
left(
e^{frac{lambda}{m}left(1-frac{1}{2^{k_j}}right)}
-
e^{frac{lambda}{m}left(1-frac{1}{2^{k_j-1}}right)}
right)
\
&=
e^{-lambda}sum_{k_1,...,k_mgeq 1}frac{1}{sum_{j=1}^m2^{-k_j}}prod_{j=1}^m
e^frac{lambda}{m}left(
e^{-frac{lambda}{m 2^{k_j}}}
-
e^{-frac{lambda}{m 2^{k_j-1}}}
right)
\
&=
sum_{k_1,...,k_mgeq 1}frac{1}{sum_{j=1}^m2^{-k_j}}prod_{j=1}^m
left(
e^{-frac{lambda}{m 2^{k_j}}}
-
e^{-frac{lambda}{m 2^{k_j-1}}}
right)
\
&=
sum_{k_1,...,k_mgeq 1}frac{1}{sum_{j=1}^m2^{-k_j}}prod_{j=1}^mg(frac{lambda}{m2^{k_j}})
end{aligned}

By the way, a simpler derivation of the HyperLogLog algorithm that does not involve complex analysis can be found in my paper https://arxiv.org/pdf/1702.01284.pdf.