<p>If you want something more formal, you can think of a streaming algorithm as a Turing machine with read-once random bits tape and working tapes whose total size is polylogarithmically bounded. So, you can store and reuse random bits, as long as you don't exceed your polylog memory bound.</p>

<p>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.</p>

<p>Refs:
AMS: <a href="http://www.tau.ac.il/~nogaa/PDFS/amsz4.pdf">www.tau.ac.il/~nogaa/PDFS/amsz4.pdf</a></p>

<p>Indyk: <a href="http://people.csail.mit.edu/indyk/stream.ps">people.csail.mit.edu/indyk/stream.ps</a></p>

CC BY-SA 3.0
2011-11-26T07:03:34.347Z
In fact, using Nisan's PRG is the only correct way to generically use randomness in streaming that I'm aware of (I'm excluding special cases like the Indyk example).
Suresh Venkat
CC BY-SA 3.0
2011-11-25T22:07:32.000Z
2011-11-25T22:07:32.000Z
Sasho Nikolov
<p>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?</p>

<p>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?</p>

CC BY-SA 3.0
2011-11-25T18:46:11.543Z
You may want to check [this thesis](http://www.itcs.tsinghua.edu.cn/~papakons/pdfs/phd_thesis.pdf), in one of the chapters the author talks about use of the number of times randoms are used (IIRC).
Kaveh
CC BY-SA 3.0
2011-11-26T07:04:47.670Z
A related question is on how to derandomize streaming algorithms - many of the answers there might be helpful: http://cstheory.stackexchange.com/questions/589/streaming-derandomization
Suresh Venkat
<ds.algorithms><derandomization><randomized-algorithms><streaming>
What's the strict definition of random coins in streaming algorithm?
Wei Yu
# What's the strict definition of random coins in streaming algorithm?

(Asked by: username_0 on 2011-11-25)

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?

**Tags:** ds.algorithms, derandomization, randomized-algorithms, streaming

> **Comments:**
> **username_1**: You may want to check [this thesis](http://www.itcs.tsinghua.edu.cn/~papakons/pdfs/phd_thesis.pdf), in one of the chapters the author talks about use of the number of times randoms are used (IIRC).  
> **username_2**: A related question is on how to derandomize streaming algorithms - many of the answers there might be helpful: http://cstheory.stackexchange.com/questions/589/streaming-derandomization  

---

## 1 answers

### Answer by username_3 on 2011-11-25. Score: 6

If you want something more formal, you can think of a streaming algorithm as a Turing machine with read-once random bits tape and working tapes whose total size is polylogarithmically bounded. So, you can store and reuse random bits, as long as you don't exceed your polylog memory bound.

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.

Refs:
AMS: [www.tau.ac.il/~nogaa/PDFS/amsz4.pdf](http://www.tau.ac.il/~nogaa/PDFS/amsz4.pdf)

Indyk: [people.csail.mit.edu/indyk/stream.ps](http://people.csail.mit.edu/indyk/stream.ps)

> **Comments:**
> **username_2**: In fact, using Nisan's PRG is the only correct way to generically use randomness in streaming that I'm aware of (I'm excluding special cases like the Indyk example).  

---

