# What's the strict definition of random coins in streaming algorithm?

I have a very basic question about random bits in streaming. How could a streaming algorithm use them? Can the algorithm use the same random bit at the start of the execution and look at it again later? Or it serves a random source that once you look at it, you will get a random bit?

Sometimes it makes difference on the space when the algorithm have to store the random bits in memory and look at it later. Or, are they just equivalent?

• You may want to check this thesis, in one of the chapters the author talks about use of the number of times randoms are used (IIRC). – Kaveh Nov 25 '11 at 18:46
• A related question is on how to derandomize streaming algorithms - many of the answers there might be helpful: cstheory.stackexchange.com/questions/589/… – Suresh Venkat Nov 26 '11 at 7:04

From algorithms design perspective, designing and even understanding a streaming algorithm is usually a two-step process. First think of the streaming algorithm as a RAM that can magically reuse random bits, i.e. has access to a random oracle. Actually there are some papers that do propose algorithms in this random oracle model. But usually, the next step is to try to make the algorithm work with hash families with bounded independence rather than a true random oracle. The seed for such families is logarithmic in size, so you can afford to store it. For some fine examples of this, just check out the classical paper of Alon, Matias and Szegedy. Another, heavier hammer to use is Nisan's pseudorandom number generator, which also allows reducing the number of random bits needed to be stored down to polylogarithmic (but larger than you usually get from bounded independence). For an example of using Nisan's generator, look at Indyk's use of the Cauchy distribution to approximate the $\ell_1$-norm of a stream. Both papers are classic and good read.