A couple of friends and I were talking about the best way to attempt to shuffle a infinite list, given finite memory. We immediately concluded that you could not do so, at least not in the same sense that you could shuffle a finite list. But we devised an approximation.
Initialize: Draw from the infinite list $L$, a array of items $W$ which we will call the window, of size $w$ items ($w\in\mathbb{Z}$)
Output To output an element from our shuffled list:
- $i\leftarrow rand(0:w)$ -- Generate a random integer $i$, with $0\le i < w$
- $r\leftarrow W[i]$ -- select the item to return
- $W[i]\leftarrow head(L)$ -- replace it with the first item in the infinite list
- $L\leftarrow tail(L)$ -- remove that item that we took
- Output $r$
So the basic idea is that we give a random item from a finite window, which we take with replacement from the infinite list.
Now I am sure this is not a new idea. So I am looking for a name for it, so I can look into it and read up on its properties. Eg it is clear that by increasing $w$ increases the "entropy" in some sense. But I am not sure if for a fixed $w$ if over time it converges to a steady state for the expected positional distance between adjacent output items.
Also so that if I end up implementing and using it in my current work, I can cite the right paper.
