
424 Large Scale and Big Data
The count of 1s can remain the same when the ith element e
i
in the stream is not
inserted. Further, if the element is inserted, the count of 1s can still remain the same
if a 0 bit is selected to be set to 1 and a 1 bit is reset to 0 during deletion. Also, if the
bit to be set to 1 is already set and that to be reset is already 0, the count of 1s remain
constant. Hence,
Pr() ()
()
λ
λλ
=− +
−+
+
−
1
1
pp
s
s
s
s
ii
(13.13)
Similarly, the count increases by one if a 0 bit is set to 1 and during deletion a 0
bit is selected.
Pr()λ
λ
+=
−
1
2
p
s
s
i
(13.14)
Substituting Equations 13.12, 13.13, and 13.14 in Equation 13.11,