(Answer)
–
– Probability that a bit in the array is not set to 1 by total km hashing:
lim (1 + 1)𝑛 = 𝑒 𝑛→∞ 𝑛
– Probability that a bit in the array is set to 1 by at least one hashing: 1 − 𝑒−𝑘𝑚/𝑛
(Answer)
Why (1pt):
The average of 2R (estimated count) is infinite as R grows.
Probability of hash value for some element having at least r trailing 0’s:
−𝑚 𝑚
P=1−𝑒 2𝑟 ≈2𝑟 𝑖𝑓2𝑟 ≫𝑚
(m: the number of distinct elements)
Increasing R by 1, P haves, but 2R doubles, so very large 2R is possible. Approach (1pt):
– Partition hash functions into small groups
– Take average for each group
– Take the median of the averages
Probability that a bit in the array is not set to 1 by a hashing: 1 − 1 𝑛
−𝑛×𝑘𝑚
(1−1)𝑘𝑚 =(1+ 1 ) −𝑛 ≈𝑒−𝑘𝑚/𝑛, 𝑛 −𝑛
1
(Answer)
abcbdacdabdcaab
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 At position 3: X1.element = c, X1.value = 1
At position 7: X1.value = 2
At position 8: X2.element = d, X2.value = 1
At position 11: X2.value = 2
At position 12: X1.value = 3
At position 13: X3.element = a, X3.value = 1 At position 14: X3.value = 2
X1.value = 3, X2.value = 2, X3.value = 2 Estimate of 2nd moment = n(2*X.value -1) Estimate using X1 = 15(2*3 -1) = 75 Estimate using X2 = 15(2*2 -1) = 45 Estimate using X3 = 15(2*2 -1) = 45 Average = (75+45+45)/3 = 55
2
(Answer)
– How many times have X been sold in the last k sales with 0/1 stream of whether that X was sold in the n-th transaction? (k ≤ N)
– How many 1’s in the last k bits? (k ≤ N)
– The sum of the last k integers of an integer stream for any k ≤ N?
– average speed/temperature in the last k time units within the window
3