Is the largest root of a random polynomial more likely to be real than complex?

Question

This question might be hard because it got $35$ upvotes in MSE and also had a $200$ points bounty by Jyrki Lahtonen but it was unanswered. So I am posting it in MO.

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)$. The number of real roots of a polynomial of degree $n$ is asymptotic to $\displaystyle \frac{2\log n}{\pi} + o(1)$. This means that the number of complex roots is approximately $\displaystyle n - \frac{2\log n}{\pi}$. Similar asymptotics hold for other distribution of the coefficients.

Definition: The largest (or smallest) root of a polynomial is the root with the largest (or smallest) modulus.

The above graph shows the roots of one such polynomial with degree $101$. The largest root is in the top right corner in green.

We can ask if the largest (or the smallest) root is more likely to be real or complex? Since there are exponentially more complex roots than real roots as seen from the above asymptotic, my naive guess was that the largest (or the smallest) root is more likely to be complex. However experimental data proved to be quite counterintuitive.

The data show that

1. Probability that the largest (or smallest) root is real is greater than the probability that it is complex.
2. And this probability decreases to some value near $1/2$ as $n \to \infty$ as shown in the above graph (created using a Monte Carlo simulation with $10^5$ trials for each value of $n$).
3. Note: Instead of uniform distribution, if we assume that the coefficients are normally distributed with mean $0$ and standard deviation $1$ and scaled to $(-1,1)$, the above observation and limiting probabilities hold.

It is counterintuitive that, despite being much (exponentially) fewer in number, real roots are more likely to contain both the largest and the smallest roots of a random polynomial. In this sense, the largest and the smallest roots are both biased towards reals.

Question 1: What is the reason for this bias?

Question 2: Does the probability that the largest (or the smallest) root of a polynomial of degree $n$ is real converge (to some value near $\frac{1}{2}$ as $n \to \infty$)?

Note: We can quantify the observed bias as follows. Let $P(L\mid R)$ be the probability that a root is the largest given that it is real and let $P(L\mid C)$ be the probability that a root is the largest given that it is complex. Similarly, let $P(S\mid R)$ be the probability that a root is the smallest given that it is real and let $P(S\mid C)$ be the probability that a root is the smallest given that it is complex. Then the experimental data say that

$$ P(L\mid R) = P(S\mid R) \approx \frac{\pi}{4\log n}, $$

$$ P(L\mid C) = P(S\mid C) \approx \frac{\pi}{2n\pi - 4\log n}. $$

Update 1: In the linked MSE post, it has now been proved that the probability that the largest root is real is at least

$$ \frac{23-16\sqrt{2}}{6} \approx 6.2 \% $$

Update 2, 11-May-24: (I am shocked to see that this post has reached $17,000$ views in just one single day !!!) A simulation with nearly $60,000$ trials for a polynomial of degree $n = 1000$ is shown below. The observation is consistent with those for $n \le 125$ shown above in the previous graph. These data also show that the probability that the largest root is real has a decreasing trend as the number to trials increases; it probably converges to $\frac{1}{2}$.

Related: What is the probability that the absolute value of the roots of a polynomial of degree $n$ is greater than $x$?

Answer 1

As mentioned in MathStackExhange, it's already explained on this blog post: https://www.galoisrepresentations.com/2014/05/24/thurston-selberg-and-random-polynomials-part-ii/

(and also mentioned in the comments) that the limit (for a reasonable distribution of the $a_i$) will be the probablity that the smallest root of a random power series

$$P(x) = a_0 + a_1 x + a_2 x^2 + \ldots $$

is real. It's also explained how using Rouché's theorem it's easy to prove that this probability is bigger than $0$ and less than $1$ and that the answer will depend on what distribution you take for the $a_i$. If you take $a_i$ to have the uniform distribution on $[-1,1]$ then the answer appears to be around 51% as you computed. If you take $a_i$ to be Gaussian with mean zero and variance one, the probability appears to be around 52% as mentioned on the blog. If you take the $a_i$ to be Gaussian but with variance $1/k!$ then this goes up to 62%. If you take $a_i$ to be the discrete measure on $1$ and $-1$ then the probability seems more like something in the low 40s in percentage instead.

In summary, there doesn't seem to be any mystery that in any reasonable case there is a limit and that depending on the model it may be bigger or less than 50%. It also doesn't seem at all surprising that even though $P(x)$ of degree $n$ has only a logarithmically small number of real roots the smallest root might still be real. In many of these models you also know that the roots converge around the unit disc with uniform angular measure, and that there is a certain repulsions between the roots on a very local scale. But while the complex roots can spread out around the unit disc the repulsion between the real roots means they are "forced" to become smaller or larger. From that perspective having kogarithmically many roots seems like lots of real roots.

So the only reasonable remaining question is how to rigorously give estimates for these quantities that can numerically be computed easily using Monte-Carlo.

There's no "theoretical" obstruction for giving a rigorous estimate. Suppose that $a_i \in [-1,1]$ is unform. Take polynomials of degree $< 100$. Divide them up into small boxes where the $a_i$ are in $1000$ intervals of the same length. Then you end up with $100^{1000}$ polynomials. From a Monte-Carlo simulation, one expects that a vast majority of these polynomials can be separated into two sets, one whose smallest root is real and less than $9/10$, and another whose smallest pair of roots are complex and less than $9/10$, and such that in both cases there additionally is a disc containing exactly these roots for which on the boundary disc $|P| > (9/10)^{100}$. Then Rouche's theorem will give a very good rigorous estimate of the probability that the smallest root of $P(x)$ is real. Now $100^{1000}$ is quite a large number and this is probably too large to do this in practice. Maybe even working in degree $< 10$ and looking at $10^{10}$ polynomials might give a reasonable estimate as well. But there might be some hope for a more efficient division of these polynomials to speed this up. Or there might be other approaches for studying the exact distribution of the smallest root by some other means.

Added: Your data is not at all convincing so the statement "it probably converges to $1/2$" seems a little like wishful thinking. The fact that other natural and symmetric models do not converge to this value really suggests otherwise. It would be really nice if it was true of course but I don't yet see any evidence for it.

I just generated $1000$ random polynomials of degree $500$ and looked at the absolute value of the smallest root. In every case, this root had absolute value strictly less than $0.91$. That means when one extends this to a random power series the function changes in the disc $|z| < 0.91$ by something of order $10^{-20}$ and often considerably less. For Rouché's theorem not to apply, the smallest root (or pair of complex conjutate roots) would have to have to be of absolute value extremely close to the "next" root.

I propose doing the following calculation if possible. My guess is that the answer for degree $500$ would both be extremely close to the answer for degree $1000$ and degree $\infty$, because I expect that for almost all polynomials one can apply Rouché's theorem. But this is testible using Monte-Carlo methods. The idea is not to test in degree $500$ and $1000$ independently, but to do the following:

1. Compute $50000$ (or some number) random polynomials of degree $500$,
2. Compute $50000$ random polynomials of degree $1000$ which extend the original degree $500$ polynomials to degree $1000$ (so they have the same initial terms).

Now you can compute not only how many times (in case 1 or 2) the smallest root is real, but also compute how often this changes as one goes from degree $500$ to degree $1000$. My (possibly faulty) intuition says that the probability of applying Rouché to show the nature of the smallest root doesn't change is very high. If that is true, any "swapping" behavior between degree $500$ and $1000$ will happens very rarely, but at least computing this should allow a better estimate of the rate of convergence.

For example, if the answers to both 1 and 2 are close to 51% but the number of times the answer changes is far less than 1% then this suggests the limit is strictly larger than 50%.

=========

My computational skills are modest, but here is a small report on trying to do the suggested computation:

Computing in huge degrees was taking too long, so I compared degree $200$ and degree $300$ polynomials. From a run of $40000$ polynomials, I found:

1. $20287$ of the degree $200$ polynomials had smallest root real.
2. In every case, the extension to degree $300$ had the same property.

Point 2 in particular suggests that the expectation in degree $200$ or $300$ and certainly degree $1000$ is most likely extremely close to the expectation in degree $\infty$. In particular, the computation here (which gives just over 50.7%) and your own computation (also 50.7% or so) strongly suggest the limit is strictly bigger than $1/2$).

So I'm quite confident the limit is bigger than 50%. I'll offer 100\$ to anyone who proves me wrong.

Even more evidence: Taking a random power series $P(x) = \sum_{i=0}^{\infty} a_i x^i$, consider for which $k$ the truncated polynomials $P_k(x) = \sum_{i=0}^{k} a_i x^i$ for $k = 1,2,\ldots,1000$ stabilize to having the smallest root real or complex. For $200$ random polynomials, the point where stability began was as follows (ordered):

$$1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, \ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, \ 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, \ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, \ 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, \ 8, 9, 9, 9, 9, 9, 10, 10, 11, 12, 12, 12, 12, 13, 18, 22.$$