Hacker News Reader

Comment by ykonstant | Hacker News Reader

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

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.

>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.

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.

I don't get your objection. (-1,1) uniform distribution is equivalent to uniform distribution over (-inf, +inf) when it comes to roots. Because you can map one to one between those intervals without affecting roots.

There is no such thing as a uniform distribution over (-inf, +inf) for the simple reason that the Lebesgue measure of (-inf, +inf) is +inf and you can’t make the integral of the whole set be equal to 1. For it to be a valid probabilistic distribution, the integral of 1 over the whole space relative to the distribution should be 1. But it won’t be. In U(a,b) a and b need to be bounded, so that you can divide the Lebesgue measure by (b - a).

You can't do it directly, that's what the scaling is for. Another trick would be to answer the question for (a,b) and then see what the answer is when b-a -> inf.

For some questions neither of those tricks will work. For this question scaling trick seems to work perfectly.

It's impossible to have a uniform distribution over (-inf, +inf). Since the distribution is uniform, each digit has an equal chance of being zero through nine, but that's true of all digits or else it's no longer uniform. At that point 100% of the values drawn in any sampling of the distribution are infinite.

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!)

Typically you would do a uniform (-x, x) and then take the limit.

This isn’t necessarily the same as the (-1, 1) version though

Its the same because the uniform distribution over (-x,x) can be obtained by taking a random variable uniformly distributed over (-1,1) and multiplying it by x.

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.

> Typically you would do a uniform (-x, x) and then take the limit.

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.

You're using a shorthand that captures an important point but does not quite dispose of the objection. Let R(X) be an indicator function that's 1 when largest root is real and 0 otherwise; then we want E[R(X)]. I think your point is that E[R(aX)]=E[R(X)], so the choice of Uniform(-1,1) rather than Uniform(-LargeNumber, LargeNumber) is a 'without loss of generality' simplification. Likewise we could take any scale mixture E[R(AX)] for A real, almost surely nonzero, and independent of X. That's a broad class of distributions, but it doesn't cover every 'natural' way of generating coefficient vectors; for example, you could sample X from a hypersphere instead of a hypercube.

> but it doesn't cover every 'natural' way of generating coefficient vectors;

But it covers one of the 'natural' ways. It seems like reasonable question to ponder.

Oh yeah, definitely reasonable. I'm a statistician by trade, so if I see R^n, I want to put a multivariate normal measure on it, which means hyperspheres. Hypercubes are cool too. Just as long as we don't treat the limit from growing the hypercube to cover R^n as being equivalent to a uniform measure on R^n. Unlike, say, in probabilistic number theory, where they shamelessly get away with defining the equivalent of a uniform probability measure on infinitely many integers, much to the consternation of every other kind of mathematician.

There are ways to 'approximate' a uniform distribution by just choosing greater and greater ranges and then normalising the result.

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

Reply on news.ycombinator.com