Random number generation: A combinatorial approach (Q2266344)

Given a sample with replacement from a finite set M, we show simply how to generate a maximal sequence of functions of the sample, all uniform on M, such that these functions are pairwise independent. We also consider the problem of generating a sequence of k-wise independent functions of the sample. To this end we set up a geometrical framework in which this problem is intimately related to that of finding, in a projective geometry of dimension r, a set of points such that no one subset with k points belongs to a hyperplane of dimension k-1.