29
$\begingroup$

I randomly had a thought about what proportion of quadratics don't have real $x$-intercepts. Initially I thought 33%, because 0,1,2 intercepts, then I thought that the proportion of 1 intercepts is infinitesimal. So I then thought 50%, as graphically half the quadratics would be above the $x$-axis, the other half below.

If you put it into a list of (max,min) and (above,below): Minimum + Above = no $x$-intercepts

Minimum + Below = 2 $x$-intercepts

Maximum + Above = 2 $x$-intercepts

Maximum + Below = no $x$-intercepts.

Hence 50% right?

Well I simulated it using code. I randomised a, b and c, and output the discriminant. If it is less than 0, add 1 to a variable. Do this about 100000 times. Now divide the variable by 100000. I get numbers like $(37.5\pm0.2)$%.

I hypothesise that it averages $3/8$.

Why?

There may be a fallacy to my approach of finding the 'proportion'. Fundamentally, it is the probability of getting a quadratic with no $x$-intercepts. However, I am not sure.

EDIT: The range was from $(-n,n)$, where $n$ was 100000, or even higher.

$\endgroup$
  • 5
    $\begingroup$ For the case $a, b, c \in (0, 1)$, see this question. $\endgroup$ – Luca Bressan Jul 29 at 7:39
  • 1
    $\begingroup$ I should have mentioned, the range was from (-n,n), and I kept increasing n, no change in the output. $\endgroup$ – Simplex1 Jul 29 at 7:48
  • 6
    $\begingroup$ @Simplex1 since $a,b,c$ gives the same number of intercepts as $ka, kb, kc$ for any $k$, the results of your experiment should be independent of the range. $\endgroup$ – alephzero Jul 29 at 15:56
  • 13
    $\begingroup$ As an example of how there's not a natural probability distribution over quadratics - in my mind, it's equally or perhaps more natural to specify a quadratic in "completed square" form as: $A(x-B)^2 + C$. In this case, B marks the axis of reflection, C the y-coordinate of the extremal point. If we take $(A, B, C)$ uniformly distributed in $[-n, n]^3$ then it's clear we have probability $1/2$ of an intercept because we have an intercept exactly when A and C are of opposite sign (ignoring the case of A or C being 0 which has probability density 0). $\endgroup$ – David E Jul 29 at 16:21
  • 2
    $\begingroup$ This was a great question, regardless of how it turns out. $\endgroup$ – The Count Jul 30 at 1:59
48
$\begingroup$

The problem isn't that there's no way to choose a random quadratic. The problem is that there's many ways, and there's no obvious reason to think of any of them as "the" way to pick one.

For starters, even picking a "random number" is something you can do in many ways:

  • uniformly from some interval, say $(-1,1)$, or $(0, 1)$, or $(2,17)$,
  • from a normal distribution with any mean or variance,
  • from an exponential distribution with any mean,
  • from a Cauchy distribution,
  • from some weird arbitrary distribution you make up yourself

(Note that "a number uniformly randomly chosen from all real numbers" is not possible, simply because the integral of the density function over all real numbers (i.e. the total probability) must be $1$, and no constant function does that.)

Now, with that in mind, here are some ways you could pick a random quadratic:

  • choosing each of $a$, $b$ and $c$ randomly by any of the above methods (or some combination of them) and constructing $ax^2 + bx + c$,
  • choosing $(a, b)$ as the stationary point and a scaling factor $c$ (again, by any / several of the methods above) and writing $c(x - a)^2 + b$,
  • choosing $f(0)$, $f(1)$, $f(2)$ randomly and using the unique quadratic that goes through all three (of course, you could replace $0$, $1$, $2$ with any other three real numbers),
  • choosing $f(0)$, $f'(0)$, and $f''(0)$ randomly, and picking the quadratic that has those values (which is admittedly very similar to the first method, but not quite),
  • ... I could go on.

All of these are plausible interpretations of "a random quadratic", depending on where the randomness is coming from. They will all (in general) produce different answers to questions like these.

(And note that for the same reasons as before, you can't have any way of picking random quadratics that is "translation-invariant" in the sense that $f(x)$ and $f(x - a)$ are equally likely, or $f(x)$ and $f(x) + b$ are equally likely.)

Now you could ask for your particular way of choosing a random quadratic, why the probability of having no x-intercepts is what you found it out to be. I think another of this question's answers points you in the right direction for that.

$\endgroup$
  • 15
    $\begingroup$ @YungGun it sounds like you want the coefficients a, b, c, and c to be sampled uniformly from the real numbers. But this is impossible because there is no uniform distribution over the real numbers. The integral of a constant function on the reals is either zero or infinite, never 1. $\endgroup$ – Thom Smith Jul 29 at 17:58
  • 12
    $\begingroup$ It converges to zero everywhere? I'm not sure what you're getting at. $\endgroup$ – Thom Smith Jul 29 at 19:11
  • 1
    $\begingroup$ @Joshua: A constant function is just f(x)=c. You're overthinking this. $\endgroup$ – MSalters Jul 30 at 8:27
  • 2
    $\begingroup$ Yes but then it's identically the constant function $f(x)=0$. $\endgroup$ – Jam Jul 30 at 14:02
  • 2
    $\begingroup$ @Falco: If you take the positive integers in the order $2,4,1,6,8,3,10,12,5,14,16,7,\dots$, then $\frac{1}{3}$ of them are odd. But nobody would consider the positive integers in this order unless they were deliberately trying to construct a counterexample to something. On the other hand, if you asked 10 different mathematicians "what is the most natural way to construct a random quadratic", the procedures you'd get would probably lead to at least four different answers to this problem. $\endgroup$ – Micah Jul 31 at 17:08
45
$\begingroup$

It's helpful to think of each quadratic polynomial as corresponding to a point in "coefficient space", an abstract 3D space whose coordinates are $(a,b,c)$. The question "What fraction of quadratic polynomials have no $x$-intercept?" can then be rephrased as "What fraction of coefficient space lies in the region $b^2 < 4 a c$?"

The problem is, of course, that this "coefficient space" has an infinite volume: $a$, $b$, or $c$ can be arbitrarily large. What's more, the region of coefficient space corresponding to polynomials without intercepts is also infinitely large: for any polynomial without an $x$-intercept, you can multiply it by any real number and get another polynomial without an $x$-intercept. And if mathematics has taught us anything, it's that if we try to divide ∞ by ∞ we cannot expect a meaningful result.

You can, however, place bounds on the values of $a$, $b$, and $c$, so that these volumes of "coefficient space" are finite. In your code, you picked the quantities $(a, b, c)$ with uniform probability from the range $(-10^5, 10^5)$. This corresponds to the region of coefficient space below:

enter image description here

Mathematica (which I used to make this plot), tells me that the fraction of this cube that is filled is $$ \frac{31 - 6 \ln 2}{72} = 0.3727932905... \neq \frac{3}{8}. $$ So the ratio you found "experimentally" is not actually equal to 3/8, but it's pretty close.

On the other hand, you could have also decided to pick all your coefficients such that $a^2 + b^2 + c^2 < (10^5)^2$. This would correspond to allowing $a$, $b$, and $c$ to lie in some spherical region of "coefficient space". Spheres are nice, right? Everybody likes spheres.

enter image description here

The fraction of this region out of the allowed spherical volume in coefficient space is (again, relying on Mathematica) is only about 0.3514..., noticeably less than 3/8. The region of coefficients you allow, and how you parametrize them, turns out to make a difference in what your final answer is (which is what some of the other answers are trying to point out.)

$\endgroup$
  • $\begingroup$ Is the fraction dependent on the size of the structure? $\endgroup$ – M.Herzkamp Jul 30 at 9:09
  • 2
    $\begingroup$ @M.Herzkamp: No, so long as you scale the volume uniformly in all directions. This is because of the scaling properties I mentioned: when $a x^2 + b x + c$ has no intercept, so does $k ax ^2 + kb x + kc$ for any value of $k$. $\endgroup$ – Michael Seifert Jul 30 at 11:55
  • 1
    $\begingroup$ Does the sequence converge as the radius of the coeffecient space increases toward infinity? $\endgroup$ – Paul Belanger Jul 31 at 12:54
27
$\begingroup$

There are infinitely many quadratics, so the number you get in the end is completely up to how "sample" from the set of all possible curves. For example, if you sample $a\in[1,2]$, and $c\in[-2, -1]$, then all the curves will have a real intercept. On the other hand, if $a,c\in [1,2]$ and $b\in[-1,1]$, then none of the curves will have a real intercept.

Edit:

Now that you said that $a,b,c$ are all uniformly distributed on $[-n, n]$, your problem translates to this:

  • Each selection of $(a,b,c)$ is one point in the cube $C=(-n, n)\times(-n, n)\times(-n,n)$.
  • Each selection is equally likely.
  • Therefore, you are really asking about the volume of the set $\{(a,b,c)\in\mathbb C| b^2-4ac \geq 0\}$. Once you get that volume, the ration of that volume to the volume of $C$ is what you need.
$\endgroup$
  • 13
    $\begingroup$ @Simplex1 No I would suggest that there is no way to "just randomize". You have to specify the range and distribution, but once you do that, it is perfectly meaningful to randomize. But you won't get an answer of "x% of all quadratics have a real intercept". You will get an answer of "If a random quadratic is picked in such and such way, then the probability of it having a real intercept is x%". $\endgroup$ – 5xum Jul 29 at 7:53
  • 8
    $\begingroup$ What does "properly depicts a random set of coefficients" mean? I'm not trying to f*** with you here. I honestly don't know what you mean by that. That is, I know vaguely what you mean, but mathematics doesn't deal with vague meanings, we can only answer a question if we know exactly what it means. $\endgroup$ – 5xum Jul 29 at 8:00
  • 6
    $\begingroup$ @Simplex1 I'm really not trying to be annoying, but what you wrote is not mathematically meaningful. "No bias towards the values of the coefficients" is meaningless. $\endgroup$ – 5xum Jul 29 at 8:12
  • 6
    $\begingroup$ @Simplex1 Unoformly over what? $\endgroup$ – 5xum Jul 29 at 8:15
  • 5
    $\begingroup$ @YungGun What "some" finite range? $\endgroup$ – 5xum Jul 29 at 18:32
16
$\begingroup$

Assume $a$,$b$,$c$ are independent and uniform in $(-n,n)$. Denote the probability that the quadratic has no $x$-intercept by $p = P[b^2 < 4ac]$. Since $b^2 < 4ac$ can only be true when $ac > 0$, which happens in $4$ of the $8$ possible sign assignments on $a,b,c$, and otherwise the condition is symmetric with respect to signs, we have \begin{align} p &= \frac{1}{2} P[b^2 < 4ac \mid a,b,c > 0] \\ &= \frac{1}{2} P[(b/n)^2 < 4(a/n)(c/n) \mid a,b,c > 0] \\ &= \frac{1}{2} P[y^2 < 4xz] \end{align} where $x,y,z$ are independent and uniform in $(0,1)$. In particular, $p$ does not depend on $n$. The last probability is given by the integral $$ \int_0^1 \int_0^1 \int_0^{\min\{2\sqrt{xz},1\}} 1 \; dy \; dz \; dx = \frac{31}{36} - \frac{\ln 2}{6} \approx 0.745587 $$ (Wolfram Alpha). Hence $$ p = \frac{31}{72} - \frac{\ln 2}{12} \approx 0.372793, $$ very close to the conjectured $0.375$.

$\endgroup$
8
$\begingroup$

While other answers have pointed out the problem of defining a random quadratic, I will argue that there are, indeed, rather interesting measures on the quadratics.

Let $ax^2+bx+c=0$ be the equation of a parabola. Il we multiply all the coefficients by some constant, we get e.g.

$$10ax^2+10bx+10c=0,$$

which is another equation of the same curve. Hence, instead of taking for $(a,b,c)$ general real numbers, we can normalize, for instance by adding the constraint $a^2+b^2+c^2 = 1$. Then $(a,b,c)$ lie on a sphere, on which there is a natural probability measure: the uniform measure. The simplest way to simulate this setting is to take for $a$, $b$ and $c$ three independent standard Gaussians; then $(a,b,c)/ \|a^2+b^2+c^2\|$ is uniform on the unit sphere.

Note that (as per Leftaroundabout's comment) this is just one possible normalization, and thus one possible measure on quadratics, called Kac's random polynomial. There are other reasonable measures. However, this one in particular gives rise to some interesting and not too difficult pieces of mathematics.

Anyway, whichever normalization you choose, this highlights a feature of this problem which is not very visible in Michael Seifert's answer: the quadratics having no $x$-intercept are exactly those whose coefficients satisfy $b^2-4ac<0$, which is, in parameter space, the equation of a filled cone (try to plot it on Mathematica and to move the object around). The point of view above interprets "the proportion of quadrics having no $x$-intercept" as "the proportion of directions in parameter space corresponding to quadrics having no $x$-intercept", or equivalently "the proportion of quadratics with $a^2+b^2+c^2 \leq 1$ having no $x$-intercept".

Under this setting, and if I'm not mistaken, a quick computation gives me that the probability of having no $x$-intersect is:

$$1-\frac{1}{2\pi}\int_{\mathbb{R}} \frac{\sqrt{t^4+4t^2+1}}{t^4+t^2+1} \ dt \simeq 0,351.$$

Reference : How many zeroes of a random polynomial are real?, A. Edelman and E. Kostlan, Bulletin of the AMS, Vol. 32, n.1, January 1995. Available on arXiv: https://arxiv.org/pdf/math/9501224.pdf

The formula above is due to Kac (1943). I will let somebody else try to find a closed form, as there are poeple here much better than me at identifying and computing integrals.

$\endgroup$
  • 3
    $\begingroup$ This is an interesting way to look at it, but I disagree that this should be considered a “natural measure” on the space of quadratics. The sphere you're using is the Stiefel-1 manifold of the vector space of quadratics here, so far so good. But that vector space is per se not a Euclidean space; the Stiefel manifold is still defined but it is not a unit sphere. By using the monomial-expansion coefficients, you're picking an ultimately arbitrary scalar product which then gives rise to a measure on the Stiefel manifold as well. $\endgroup$ – leftaroundabout Jul 30 at 13:46
  • $\begingroup$ @leftroundabout: good catch, and you are completely right. I've modified my answer to highlight this kind of choices (turning things a bit differently -- the Euclidean structure is still there, but then there is an arbitrary choice of embedding of the sphere into the Euclidean space). $\endgroup$ – D. Thomine Jul 30 at 20:16
  • $\begingroup$ This is $1/(2 \pi)$ times the solid angle of an oblique circular cone with base radius $2$, height $1$ and the distance between the center of the base and the foot of the altitude equal to $\sqrt 3$. There is a known formula for the solid angle, which gives $$1 - \frac \alpha {2 \pi} K(1 - \alpha^4) - \frac {\alpha^5} {2 \pi} \Pi(1 - \alpha^8, 1 - \alpha^4)$$ in terms of $K(m)$ and $\Pi(n, m)$, where $\alpha = \sqrt {2 - \sqrt 3 \hspace {1px}}$. $\endgroup$ – Maxim Jul 31 at 19:09
5
$\begingroup$

Since you used a computer, $a, b, c$ must have been in a restricted range. Try altering that range and see how it affects your answer. Even if you have a super computer with an enormous but still finite range of numbers, it will still tell you nothing about the case for all numbers.

Even a dream computer without limits would have a problem as you cannot pick evenly from an infinite set.

Consider a simpler problem: what proportion of positive integers have a digit $9$ in them? The super naive answer is $10\%$ but even going as far as $100$ gives the larger answer $19\%$. Now go to $1000$, $10000$, etc and you will find that the answer continues to grow. It is easy enough to prove that it grows without limit and approaches $100\%$. So, in a sense, $100\%$ of positive integers have a digit $9$.

$\endgroup$
  • 1
    $\begingroup$ Lets say he tests all numbers from (-100, 100), then (-1000, 1000), then (-10000, 10000), until he reaches 500 zeros. If all of those give you the same answer, then isn't it very highly likely you will get that answer no matter what numbers you choose? We can't know for sure if the answer is right, but we can know to a very high degree of probability can't we? Also, saying that the limit approaches 100% for the infinite series of numbers is not the same as saying the chance is 100% at any point, which is what you're saying when you say 100% of integers have a 9. It's untrue mathematically $\endgroup$ – YungGun Jul 29 at 16:29
  • 1
    $\begingroup$ No, whatever your finite limit is, however huge, it is still an insignificant fraction of all numbers. For example, before Wiles' proof of Fermat's theorem, it was known that any exception would be very large. However, this was not considered a proof. Another thing to note is that if there are infinitely many possibilities then $100\%$ is not the same as certain. $\endgroup$ – badjohn Jul 29 at 19:29
  • 2
    $\begingroup$ @YungGun see also math.stackexchange.com/questions/514/…. $\endgroup$ – Thom Smith Jul 29 at 20:17
  • 1
    $\begingroup$ The answer by nomadictype proves that the range does not influence the result. I don't see how your answer adds value. $\endgroup$ – Vincent Jul 31 at 2:55
  • 1
    $\begingroup$ nomadictype's samples are all cubes. D. Thomine uses another attractive approach and gets a different answer. That's the point. You cannot sample the whole infinite space uniformly. Different restrictions or distributions may give different results. $\endgroup$ – badjohn Jul 31 at 8:19
4
$\begingroup$

Other answers have done a good job at showing this mathematically, but I feel that a bit of visual explanation would help to solidify exactly why there is a difference in these two answers of $1/2$ and ~$3/8$.

Below, I have made a graph of all quadratic equations of the form $a(x-b)^2 +c$, for every combination of $a$, $b$ and $c$ in the closed interval $[-4,4]$, with a step size of $0.5$. The exact numbers are not relevant to this answer (though it is relevant to say that the x-scale and y-scale are equal, and both are linear).

For each parabola, I've only plotted a small section near the vertex. The line of each is colored according to how many x-intercepts it has: 0 is red, 1 is grey, and 2 is blue.

graph of the search space for a(x-b)^2 +c

A visual inspection reveals that there is roughly an equal number of red and blue parabolas, and both vastly outnumber the grey ones. The exact counts in this graph are:

$$ \begin{matrix} \color{blue}{\text{Two}} & 2448 & 0.4982699 \\ \color{gray}{\text{One}} & 289 & 0.05882353 \\ \color{red}{\text{Zero}} & 2176 & 0.4429066 \\ \end{matrix} $$

Now, let's look at the same search space, but using the form $ax^2 +bx+c$. The graph looks quite different:

graph of the search space for ax^2 +bx+c

Again the grey are outnumbered, but we see vastly more blue than red. The exact numbers here are:

$$ \begin{matrix} \color{blue}{\text{Two}} & 3104 & 0.6317932 \\ \color{gray}{\text{One}} & 65 & 0.0132302055 \\ \color{red}{\text{Zero}} & 1744 & 0.3549766 \\ \end{matrix} $$

As we can see, the 'wings' of this graph are exclusively blue, meaning that all such parabolas have two intercepts. This is what skews the result away from $1/2$.


For those interested, the language I used to generate these images was Processing, and the code may be found here: https://pastebin.com/geLya3jQ. (Why? Mostly because I don't have much experience with Mathematica, etc.)

$\endgroup$
0
$\begingroup$

We need the probability that $b^2 < 4ac$. When $a$ and $c$ have opposite signs this condition is never satified; this occurs in 4 of the 8 octants of the problem domain. So we need only look at the other 4 octants. These are all related by symmetry, so we can choose one representative. Here we'll choose the octant $a \in [0,n], b \in [0,n], c \in [0,n]$. The relevant volume of the domain is given by

$$V = \int_{a=0}^n \int_{c=0}^n \int_{b=0}^{2\sqrt{ac}} \,{db} \,{dc} \,{da} $$

Carrying out the integration

$$V = \int_{a=0}^n \int_{c=0}^n {2\sqrt{ac}} \,{dc} \,{da} $$

$$V = \int_{a=0}^n \frac{4}{3} \sqrt{a} n^{3/2} \,{da} $$

$$V = \frac{8}{9} n^{3/2} n^{3/2} $$

This is the volume of one octant; the volume for the 4 octants is then

$$V = \frac{32}{9} n^{3} $$

The volume of the entire domain is $(2n)^3 = 8n^3$

Then the probability of having no x-intercept is

$$p=\frac{\frac{32}{9} n^{3}}{8n^3} = \frac{4}{9} $$

Note that the probability is independent of $n$.

$\endgroup$
  • 4
    $\begingroup$ Note that we could have $2\sqrt{ac}>n$ even if $a \le n$ and $c \le n$. So your integral isn't computing the volume of the correct region, but of something bigger. Perhaps this is why you've come up with a larger fraction than the OP... $\endgroup$ – Micah Jul 29 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.