Supplementary

The way we define the window sizes is equivalent to placing each element independently intoarandom bucket,andlettingni bethenumber ofelements inbucketi. Hence thedistribution of window sizes is correct. Conditioned on the window sizes, the assignment of elements into windows is determined by a random permutation; any partition is equally likely. Therefore the distribution of elements into windows is equivalent to placing each each element into a random windowindependently. ForeachHi 1-compatible partition P with P(e) = j0, we begin by showing that we can create anotherHi 1-compatible partition P by setting P(e) = j and all other values of P equal toP.