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
At step 1, let x=1
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
Interesting post, thanks for the Jaynes link. Related book which is a great read is Szekely’s Paradoxes in Probability Theory and Statistics
I think the most intriguing paradoxes are the ones that experts can not agree how to resolve. For instance, take the two envelope paradox: you are presented with two envelopes, one has twice as much money as the other. You are told that first envelope contains x dollars, which envelope should you choose? From expected value calculations, the other envelope has $1.25x which is larger regardless of x. Turns out that the paradoxical “always pick the other one” solution comes out even if we introduce a proper prior on the amounts in envelopes