Gray Area -- good question, thanks for bring my attention to reservoir sampling. I found a compact description of it in Devroye's "Non-Uniform ..." and for sampling just 1 integer x it looks as follows

1. At step 1, let x=1 2. At step k, let x=k with probability 1/k

sum_i 1/i diverges, this means x will never stop growing

pdf23ds -- I think you can use reservoir sampling for sampling from infinite streams, an interesting question is when it works. For instance, consider an infinite stream of IID bits, 1-element reservoir sampling converges after 1 step. An interesting question is when exactly it works -- my intuition is that it works whenever the stream has finite entropy, and a stationary Markov property