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.
> 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.
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.
For some questions neither of those tricks will work. For this question scaling trick seems to work perfectly.
If scaling the coefficients down to [-1, +1] gives a uniform distribution, then the original distribution must have been uniform in [-x, +x] where x is the largest coefficient in the original polynomial. That, too, is a contradiction! It means that either -x or +x are guaranteed to be one of the random coefficients, which is very much not a uniform distribution.
(That said, I think the (-1, +1) version of the problem still has interest!)
This isn’t necessarily the same as the (-1, 1) version though
This doesn't change anything for the question about roots because the roots of a polynomial don't change when you multiply it by x.
But this is completely uninformative for the interval (-inf, +inf). Taking limits is a tool you can use, and it works well when the infinite behavior matches the limit of the finite behavior. The opposite is the case here and the infinite behavior is radically unlike the finite behavior. You might as well try to determine the value of an impulse function at zero by seeing what the limit is as you approach zero.
But it covers one of the 'natural' ways. It seems like reasonable question to ponder.
One problem with this is that there's no one way to do it. You could argue equally well that the result should be a uniformly random point on the S100 sphere.
What it definitely cannot be is a random point on the [-1,1]^100 cube because if you divide by the greatest absolute value then one of the coefficients will be -1 or 1
But the important part of the question can be asked for any possible distribution over the reals.
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).
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
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$.
Not to be confused with J-P Kahane, who also studied this area (of the posted article) via Fourier series
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.
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.
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.
But if you're going to play Google's game, this what you're going to get apparently. So what was your answer? One guesses that they weren't so much interested in a correct answer (since it's a bullshit question anyway) but that you were willing to give it a college try (and reference some concepts about limits, and perhaps the geometric layout of this "file system" in the Doctor Who universe they were apparently hoping to roll out this system in, the speed of light, etc).
In order to, you know, pass their dipshit filter.
As if this what they do all day: ask each other fundamentally useless questions with no meaningful answer (that anyone would actually care about), and which you aren't expected to provide an actual working answer to, anyway. But which have a cute partial (shibboleth) answer embedded in them. Which if you manage to come up with (under interview time constraints and pressure) -- and most importantly: if you ignore the request to actually solve the problem as stated -- will tell the person asking "how you think".