Computer scientists devise randomized algorithms when they cannot find good deterministic ones. Then they try to decrease the randomness used and still try to prove that the algorithm answers correctly with high probability. They even hope to decrease the randomness used to a small amount that they can finally convert the randomized algorithm to a deterministic one. A critical tool for doing this is to generate a long string from a distribution close to uniform, using only a small random string. We will see how to do this using Epsilon Biased Probability Spaces and also construct more general objects called strings that are almost k-wise independent.
