1 Probability and Computing

1.15 Pairwise Independence and Universal Hash Function

1.15.1 Pairwise Independence

1.15.2 Chebyshev’s Inequality for Pairwise Independent Random Variables

1.15.3 Universal Families of Hash Functions

1.15.4 Application in Finding Heavy Hitters in Data Streams

TODO: after balls and bins, Poisson, and maybe Probabilistic methods.