4 ms·

Right. The problem as originally stated is paradoxical. You can't uniformly sample an unbounded set. I assume OP used a random floating point, which are bounded

• Sesse__ 2y ago
  > You can't uniformly sample an unbounded set. You definitely can, as long as you are accepting the use of limits (and without that, sampling uniform over any subsegment over the reals would also be pretty much impossible). “Sample a uniformly chosen real” just is shorthand for “Sample over a real from [-N, +N], then we are interested in the answer then N goes to infinity”. In this case, then just divide all the coefficients by N, which obviously doesn't affect the answer. So uniformly over [-1,+1] is as good as uniformly over R. This is very common. See e.g. number theory, where you can ask questions like “what is the probability that two randomly chosen natural numbers are coprime”; the set of natural numbers is also unbounded, but it doesn't prevent this question from being well-defined, and the answer is 6/π² (about 0.608).
  • mturmon 2y ago
    This comment opens perhaps a bigger can of worms than intended. The original statement: >> You can't uniformly sample an unbounded set. [of real numbers] is true, provided that by "sample" we mean "sample in a way that obeys Kolmogorov's axioms". (I'm adding the qualifier "of real numbers" to keep this somewhat grounded, so that we don't get distracted with abstract metric spaces, or worse.) In the above comment, by placing a limit on the set ([-N, +N]), you have made the set bounded -- thereby contradicting the premise of the original statement! * Your last paragraph is interesting. Suffice to say, the situation is more complex than your summary would indicate, precisely because of the above issue -- that is, "what does sample mean in this context". It led me to this paper by Lei and Kadane (the latter, the well-known Bayesian theorist) -- https://arxiv.org/pdf/1806.00053 https://arxiv.org/pdf/1806.00053 It is well worth a read, if you're into such things. See especially section 1, and section 7. In essence, the above statement ("You can't sample uniformly") is true, if you interpret "sample" as "following a scheme that obeys Kolmogorov's well-known axioms." However, if you are willing to abandon countable additivity of your measure, and drop down to finitely-additive measures, there are several classes to choose from that support a notion of uniformity. (Again, just thinking about measures on integers, not real numbers. But these are not measures in Kolmogorov's sense.) These measures support a notion of uniformity, but they may not have some properties that you might hope for, such as that the measure of a set A of natural numbers is the same as A + i, where adding "i" shifts the set by "i" units left or right. For some of these measures, the result about co-prime numbers is as you say, and for others, the result is indeterminate. That is, the limit exists, but it can be any number between 0 and $6/\pi/\pi$.
    • selimthegrim 2y ago
      >It led me to this paper by Lei and Kadane (the latter, the well-known Bayesian theorist) Not to be confused with J-P Kahane, who also studied this area (of the posted article) via Fourier series
• ptero 2y ago
  They are also discrete, coming from a finite set. I remember at the undergrad differential equation class the teacher asked for some arbitrary coefficients so we can classify the result. She was very surprised that 3 differential equations she got all turned out to be parabolical, which form a set of probability 0 in the full space. But of course the probabilities for equations with small integer coefficients (which is what people wrote) are totally different.
• owyn 2y ago
  > You can't uniformly sample an unbounded set. I was asked to do this as an interview question at google! It was about log file processing not math (sample an infinite log file), and I thought my answer was ok? But that's why I don't work there so I am really enjoying this whole thread.
  • CamperBob2 2y ago
    What's the correct answer (and what was yours?)
    • seanhunter 2y ago
      The usual trick to sampling one line at random with uniform probability from an arbitrarily large file or stream is worth knowing because people have been asking this as an interview question for >20years at this point[1]. 1. Store the first line with probability p=1 2. When the second line arrives, either keep the first line or with p=.5 drop it and replace it with the second line 3. Continue in this manner with each line. That is to say on the n-th line you either keep the line you have or with p=1/n you drop the line you have and replace the stored line with the new n-th line[2] 4. When you reach the end of the stream or the user quits the program or whatever, return the line you have stored. This will have been selected with uniform probability from the lines you have received. You can sketch the grid for a few lines you can see at every point you have all the lines with uniform probability. It's worth noting that by doing the algorithm in this way you are not in fact ever selecting with uniform probability from an unbounded set so noone is going to revoke your maths license or anything. You are only ever choosing between two things (keep the thing you have or drop it and replace it with a specific new thing). An intuition behind the proof that this does not violate any laws is that in the case of a truly infinite stream this algorithm would never terminate. [1] I know because over 20 years ago I was asked this as an interview question. [2] It's something like this probability. If I was actually answering the question I would work it out properly to be sure.
      • owyn 2y ago
        Yep that was my answer too. I didn't get the job so I'm just guessing but I'm pretty sure that's it.