6 ms·

Two questions that immediately jump at me are: 1. What is random? They seem to have run numerical experiments, which suggests they used (something equivalent t

by ptero 2y ago

Two questions that immediately jump at me are: 1. What is random? They seem to have run numerical experiments, which suggests they used (something equivalent to) uniform integer coefficients from a bounded set. And that could affect findings a lot! 2. Did they look at odd degrees (which always guarantees a real root), even or both? Not trying to knock this fun post.

lupire 2y ago
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. But the important part of the question can be asked for any possible distribution over the reals.
- 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.
ykonstant 2y ago
As stated in the definition, the distribution is that of independent uniform coefficients in (-1,1).
- thaumasiotes 2y ago
  True, but they give a justification for that distribution, and the justification is incorrect. > The number of real roots of a random polynomial with real coefficients is much smaller than the number of complex roots. Assume that the coefficients are independently and uniformly random in (−1,1) for if not then we can divide each coefficient by the coefficient with the largest absolute[] value to scale each coefficient to (−1,1). It's true that, if you have a known polynomial, you can normalize the coefficients in this way... assuming that (-1, 1) is a typo for [-1, 1]. But it's definitely not true that you can produce a random polynomial as the input to this idea. That can't be done. The concept of "a random polynomial with real coefficients" is known not to exist; you would have to specify some kind of nonuniform distribution over the reals for the coefficients to be drawn from. Once you have done this, the distribution of coefficients in the normalized equivalents that have coefficients in [-1, 1] will not be uniform. In other words, the question says "assume that the coefficients [of a random polynomial] are independently and uniformly random in (-1, 1), for if not, we can exhibit equivalent polynomials whose coefficients are dependently and nonuniformly random in [-1, 1]". But this observation makes no sense.
  - ykonstant 2y ago
    >The concept of "a random polynomial with real coefficients" is known not to exist; The concept of "a random polynomial with real coefficients" means what we want it to mean in each particular context; mathematicians don't care too much about semantics, but interesting questions. And this is a very interesting question.
    - eternauta3k 2y ago
      He's right that this question isn't fundamentally about the space of polynomials but rather about this particular arbitrary-looking distribution. But yeah, the question is interesting nonetheless.

by ptero 2y ago

lupire 2y ago

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. But the important part of the question can be asked for any possible distribution over the reals.

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.

ykonstant 2y ago

As stated in the definition, the distribution is that of independent uniform coefficients in (-1,1).

thaumasiotes 2y ago
True, but they give a justification for that distribution, and the justification is incorrect. > The number of real roots of a random polynomial with real coefficients is much smaller than the number of complex roots. Assume that the coefficients are independently and uniformly random in (−1,1) for if not then we can divide each coefficient by the coefficient with the largest absolute[] value to scale each coefficient to (−1,1). It's true that, if you have a known polynomial, you can normalize the coefficients in this way... assuming that (-1, 1) is a typo for [-1, 1]. But it's definitely not true that you can produce a random polynomial as the input to this idea. That can't be done. The concept of "a random polynomial with real coefficients" is known not to exist; you would have to specify some kind of nonuniform distribution over the reals for the coefficients to be drawn from. Once you have done this, the distribution of coefficients in the normalized equivalents that have coefficients in [-1, 1] will not be uniform. In other words, the question says "assume that the coefficients [of a random polynomial] are independently and uniformly random in (-1, 1), for if not, we can exhibit equivalent polynomials whose coefficients are dependently and nonuniformly random in [-1, 1]". But this observation makes no sense.
- ykonstant 2y ago
  >The concept of "a random polynomial with real coefficients" is known not to exist; The concept of "a random polynomial with real coefficients" means what we want it to mean in each particular context; mathematicians don't care too much about semantics, but interesting questions. And this is a very interesting question.
  - eternauta3k 2y ago
    He's right that this question isn't fundamentally about the space of polynomials but rather about this particular arbitrary-looking distribution. But yeah, the question is interesting nonetheless.