Thurston, Selberg, and Random Polynomials, Part II.

What is the probability that the largest root of a polynomial is real?

Naturally enough, this depends on how one models a random polynomial. If we take polynomials of degree N which are constrained to have all of their roots to be of absolute value at most one (with respect to the normalized Lebesgue measure on \mathbf{R}^N), then, as mentioned last time, the probability that the largest root is real is either 1/N in odd degree N and 1/(N-1) in even degree. A priori, this seems surprisingly small. However, the roots of such polynomials are accumulating on the unit circle, and it’s easier for complex roots to be near the unit circle than real roots. So let’s instead consider the Kac model of polynomials f(x), where the coefficients are chosen to be independent normals with mean zero. If you ask for the probability that the root whose absolute value is closest to one is real, then I suspect that the answer will be approximately 1/N. However, what about the largest root? The first observation is that the expected number of real roots is 2/\pi \log N, so a the most naïve guess is that the probability that the largest root is real is approximately (2/\pi N) \log N. If you like, you can pause here and guess whether you think this is too high, too low, or about right.

A useful observation is that, instead of considering the largest root, we can consider the smallest root. This is because the map a_k \rightarrow a_{N-k} is measure preserving and inverts the roots. On the other hand, the behavior of random Kac polynomials in large degree inside the unit circle starts to approximate the behavior of random power series

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

where the a_i are all normally distributed with mean zero and standard deviation one. It’s easy to see that f(x) will have radius of convergence 1 with probability one. So we might instead consider what the probability is that the smallest root of a random power series is real. However, in this case, it is quite elementary to see that this probability P_{\infty} is strictly between zero and one. Quite explicitly, consider the subspace of power series such that the following inequality holds:

\displaystyle{|a_0| + \frac{1}{2} |a_1 - 2| + \frac{1}{2^2} |a_2| + \frac{1}{2^3} |a_3| + \ldots < 1}.

This region has positive measure (easy exercise). On the other hand, for all such power series, one can apply Rouché's theorem for the contour |2x| = 1 to see that f(x) and 2x have the same number of zeroes inside this disc, and hence f(x) has exactly one root of absolute value less than 1/2. By the reflection principle, this root is real. It follows that the probability that the smallest root of f(x) is real is positive. Equally, one can consider the region:

\displaystyle{|a_0 - 1| + \frac{1}{2} |a_1| + \frac{1}{2^2} |a_2 - 8| + \frac{1}{2^3} |a_3| + \ldots < 1},

and by applying Rouché along |2x| = 1 and comparing with 1 + 8 x^2, the corresponding f(x) will have exactly two roots inside this ball, and from the inequalities above it follows that neither of them will be real, and hence P_{\infty} < 1.

The same argument shows that if P_N is the probability that the smallest (or largest) root of a Kac polynomial is real, then there are uniform (independent of N) estimates 0 < a < P_N < b < 1 for all N. Naturally enough, one should expect that P_N converges to P_{\infty}. This is true, and the rough idea is to show that, with probability approaching one (as N \rightarrow \infty), one can apply Rouché’s theorem to deduce that the smallest root of f(x) is real if and only if the smallest roots of its truncation f_N(x) is real. The key idea here is that, for the truncation f_N(x), most of the roots of f_N(x) will be uniformly distributed along the unit circle, and so the contribution of the relevant factor \prod |x - \alpha| to f_N(x) will not be too small. Hence one can usually apply Rouché along the contour |x| = \beta as long as there are no roots of f_N(x) of absolute value too close to \beta.

The computations above also allow one to give effective gaps between P_{\infty} and either zero or one (by estimating the measure of the corresponding regions as translates of |a_i| \le 1/2^{i+1}), although these estimates are not so sharp. Namely, the probability that the smallest root of a random power series is real is at least 0.256% and at most 99.999999999999917%. Some numerical data suggests, however, that the probability that the largest root of a random Kac polynomial (of large degree) will be real is approximately 52%. I have some undergraduates working with me this summer, and one of their projects will be to see if they can prove that the probability is really strictly larger than 50%, or at least to find a good an estimate as they can.

One may ask what happens for other ensembles of polynomials. One natural class to consider is the so-called binomial polynomials, where the a_i are now normal with mean zero and variance \displaystyle{\binom{n}{i}}. Here the previous argument doesn't (a priori) work. On the other hand, as Boris Hanin (a Steve Zelditch student from Northwestern who is leaving for a postdoc at MIT next year) pointed out to me, it actually does: to fix it, one should scale all the roots of the relevant polynomials by \sqrt{N}, and then there really is a limit distribution as N \rightarrow \infty, given by power series

f(x) = \displaystyle{\frac{a_0}{0!} + \frac{a_1 x}{\sqrt{1!}} + \frac{a_2 x^2}{\sqrt{2!}} + \ldots}

where the normalized a_i are normals with standard deviation one. Note that these power series have an infinite radius of convergence with probability one. The probability that the smallest root is real will once again be strictly between 0 and 1. In order to prove convergence of P_N (by applying Rouché’s theorem), one needs to know that the relevant 2-point correlation functions behave reasonably enough; I’m hoping to get Boris to work out and write down the details here. Numerically, the limit probability in this case is somewhere around 62%.

Gap Probabilities:

I speculated last time on some conjectural relationship between the space of real monic polynomials \Omega_N all of whose roots are at most one, and the space of random Kac polynomials of degree N as N goes to infinity. But now I wanted to point out a more direct an elementary relationship between ensembles of random real polynomials and our space \Omega_N. A gap probability is the probability that the eigenvalues/roots of some ensemble avoid some region of the corresponding parameter space. Let’s compute this for a very large gap. That is, let’s compute the probability that a random polynomial has all of its roots less than T as T \rightarrow 0.

Let's consider the Kac model of random polynomials

f(x) = a_0 x^N + a_1 x^{N-1} + \ldots +  a_N

where the a_i are chosen independently from a normal distribution with mean zero and standard deviation one. Hence we are asking: what is the probability that all the roots of f(x) have absolute value at most T? This is simply the integral

\displaystyle{\left(\frac{1}{\sqrt{2 \pi}}\right)^{N+1} \int_{P \Omega_N(T)} e^{-|x|^2/2} dx}

where P \Omega_N(T) is the space of polynomials (not necessarily monic) all of whose roots are at most T. There is a map

\Omega_N(T) \times [-\infty,\infty] \rightarrow P \Omega_N

given by (\lambda,P) \mapsto \lambda P with Jacobian |\lambda|^{N+1}. Hence we can write our quantity as an integral over \Omega_N(T), which turns out to be

\displaystyle{\left(\frac{1}{\sqrt{2 \pi}}\right)^{N+1} \int^{\infty}_{-\infty} \int_{ \Omega_N(T)} |\lambda|^{N+1} e^{-(\lambda^2 - a^2_1 \lambda^2 - \ldots - a^2_N \lambda^2)/2}  dx}.

We can now compute the integral over \lambda directly, and then scaling \Omega_N(T) to \Omega_N in the usual way, we find that the probability that all the roots have absolute value T is

\displaystyle{ T^{N(N+1)/2} \left(\frac{2}{\pi}\right)^{(N+1)/2} \Gamma(N/2+1) \int_{\Omega_N} \frac{dV}{(1 + T^2 a^2_1 + T^4 a^2_2 + \ldots + T^{2N} a^2_{N})^{N/2+1}}}

Now suppose that T \rightarrow 0. Then the integral over \Omega_N converges to the volume of \Omega_N, and we obtain an exact asymptotic that all the roots are (highly) concentrated at zero. In fact, one can do this computation with any probability measure \mu which decays sufficiently at infinity.

Curiously enough, we can also ask (in the setting of random polynomials subject to some reasonable measure \mu for each i) what the probability is that a random polynomial has R real roots contingent on all the roots of that polynomial being less than T. It turns out that, as T \rightarrow 0, the answer in this case is simply the ratio of the volume of \Omega_{R,S} to \Omega_N (with R+2S=N). This answer does not depend at all on \mu. The explanation for this is that, having subjected the polynomials to the constraint that all the roots have absolute value at most T for small T, one is restricting to some tiny region where the measure is constant, and so it is converging to a scaled version of Lebesgue measure.

Advertisements
This entry was posted in Mathematics and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s