Given the article's windup, I'd be a bit skeptical of the naive solution - at input n, with probability 1/n replace the current choice.
Once you've reached input number 10^8 or whatever, you've got all sorts of chances to have arithmetic overflow and/or the weirdness of that many pseudo-random operations screw you.
I'd rather keep a list of x's; let x1 be randomly chosen from the last 10, x2 randomly chosen from the last 100, x3 random chosen from the last 1000, etc and when termination time come do a little fixup. That'd take O(log(n)) memory instead of O(1) but if this matters, shouldn't you want some sample of what's happening?