59
$\begingroup$

Problem

The premise is almost the same as in this question. I'll restate for convenience.

Let $A$, $B$, $C$ be independent random variables uniformly distributed between $(-1,+1)$. What is the probability that the polynomial $Ax^2+Bx+C$ has real roots?

Note: The distribution is now $-1$ to $+1$ instead of $0$ to $1$.

My Attempt

Preparation

When the coefficients are sampled from $\mathcal{U}(0,1)$, the probability for the discriminant to be non-negative that is, $P(B^2-4AC\geq0) \approx 25.4\% $. This value can be obtained theoretically as well as experimentally. The link I shared above to the older question has several good answers discussing both approaches.

Changing the sampling interval to $(-1, +1)$ makes things a bit difficult from the theoretical perspective. Experimentally, it is rather simple. This is the code I wrote to simulate the experiment for $\mathcal{U}(0,1)$. Changing it from (0, theta) to (-1, +1) gives me an average probability of $62.7\%$ with a standard deviation of $0.3\%$

I plotted the simulated PDF and CDF. In that order, they are:

PDFCDF

So I'm aiming to find a CDF that looks like the second image.

Theoretical Approach

The approach that I find easy to understand is outlined in this answer. Proceeding in a similar manner, we have

$$ f_A(a) = \begin{cases} \frac{1}{2}, &-1\leq a\leq+1\\ 0, &\text{ otherwise} \end{cases} $$

The PDFs are similar for $B$ and $C$.

The CDF for $A$ is

$$ F_A(a) = \begin{cases} \frac{a + 1}{2}, &-1\leq a\geq +1\\ 0,&a<-1\\ 1,&a>+1 \end{cases} $$

Let us assume $X=AC$. I proceed to calculate the CDF for $X$ (for $x>0$) as:

$$ \begin{align} F_X(x) &= P(X\leq x)\\ &= P(AC\leq x)\\ &= \int_{c=-1}^{+1}P(Ac\leq x)f_C(c)dc\\ &= \frac{1}{2}\left(\int_{c=-1}^{+1}P(Ac\leq x)dc\right)\\ &= \frac{1}{2}\left(\int_{c=-1}^{+1}P\left(A\leq \frac{x}{c}\right)dc\right)\\ \end{align} $$

We take a quick detour to make some observations. First, when $0<c<x$, we have $\frac{x}{c}>1$. Similarly, $-x<c<0$ implies $\frac{x}{c}<-1$. Also, $A$ is constrained to the interval $[-1, +1]$. Also, we're only interested when $x\geq 0$ because $B^2\geq 0$.

Continuing, the calculation

$$ \begin{align} F_X(x) &= \frac{1}{2}\left(\int_{c=-1}^{+1}P\left(A\leq \frac{x}{c}\right)dc\right)\\ &= \frac{1}{2}\left(\int_{c=-1}^{-x}P\left(A\leq \frac{x}{c}\right)dc + \int_{c=-x}^{0}P\left(A\leq \frac{x}{c}\right)dc + \int_{c=0}^{x}P\left(A\leq \frac{x}{c}\right)dc + \int_{c=x}^{+1}P\left(A\leq \frac{x}{c}\right)dc\right)\\ &= \frac{1}{2}\left(\int_{c=-1}^{-x}P\left(A\leq \frac{x}{c}\right)dc + 0 + 1 + \int_{c=x}^{+1}P\left(A\leq \frac{x}{c}\right)dc\right)\\ &= \frac{1}{2}\left(\int_{c=-1}^{-x}\frac{x+c}{2c}dc + 0 + 1 + \int_{c=x}^{+1}\frac{x+c}{2c}dc\right)\\ &= \frac{1}{2}\left(\frac{1}{2}(-x+x(\log(-x)-\log(-1)+1) + 0 + 1 + \frac{1}{2}(-x+x(-\log(x)-\log(1)+1)\right)\\ &= \frac{1}{2}\left(2 + \frac{1}{2}(-x+x(\log(x)) -x + x(-\log(x))\right)\\ &= 1 - x \end{align} $$

I don't think this is correct.

My Specific Questions

  1. What mistake am I making? Can I even obtain the CDF through integration?
  2. Is there an easier way? I used this approach because I was able to understand it well. There are shorter approaches possible (as is evident with the $\mathcal{U}(0,1)$ case) but perhaps I need to read more before I can comprehend them. Any pointers in the right direction would be helpful.
$\endgroup$
9
  • 3
    $\begingroup$ When you divide the variable $c$ from both sides of inequality, the inequality sign will flip when $c < 0$. So this is one of the possible error. $\endgroup$
    – BGM
    Sep 8, 2020 at 17:24
  • 3
    $\begingroup$ $(41 + \log(64))/72 \approx 0.627207$. $\endgroup$ Sep 8, 2020 at 18:01
  • 25
    $\begingroup$ Super cool question. $\endgroup$
    – K.defaoite
    Sep 8, 2020 at 21:53
  • 3
    $\begingroup$ A small point of style: When you write “Let us assume $X = AC$…”, it would be more usual to write “Let us take $X = AC$…”, or “set”, “define”, “write”. It’s generally good to distinguish assumptions about terms/variables that are already under consideration from introducing a new term and defining it in terms of the things you had before. Some people also notate the difference by e.g. “Let us take $X := AC$…” $\endgroup$ Sep 9, 2020 at 9:53
  • 1
    $\begingroup$ $p_{[0,1]}=\frac16 \log_e(2) +\frac5{36} \approx 0.254$ so $p_{[-1,1]}=\frac12 p_{[0,1]} +\frac12 = \frac1{12} \log_e(2) +\frac{41}{72} \approx 0.627$ $\endgroup$
    – Henry
    Sep 9, 2020 at 12:05

3 Answers 3

51
$\begingroup$

I would probably start by breaking into cases based on $A$ and $C$.

Conditioned on $A$ and $C$ having different signs, there are always real roots (because $4AC\leq 0$, so that $B^2-4AC\geq0$). The probability that $A$ and $C$ have different signs is $\frac{1}{2}$.

Conditioned on $A\geq0$ and $C\geq 0$, you return to the problem solved in the link above. Why? Because $B^2$ has the same distribution whether you have $B$ uniformly distributed on $(0,1)$ or on $(-1,1)$. At the link, they computed this probability as $\frac{5+3\log4}{36}\approx0.2544134$. The conditioning event here has probability $\frac{1}{4}$.

Finally, if we condition on $A<0$ and $C<0$, we actually end up with the same probability, as $4AC$ has the same distribution in this case as in the case where $A\geq0$ and $C\geq 0$. So, this is an additional $\frac{5+3\log 4}{36}\approx0.2544134$ conditional probability, and the conditioning event has probability $\frac{1}{4}$.

So, all told, the probability should be $$ \begin{align*} P(B^2-4AC\geq0)&=1\cdot\frac{1}{2}+\frac{1}{4}\cdot\frac{5+3\log4}{36}+\frac{1}{4}\cdot\frac{5+3\log 4}{36}\\ &=\frac{1}{2}+\frac{5+3\log4}{72}\\ &\approx0.6272... \end{align*} $$

$\endgroup$
3
  • $\begingroup$ I found this approach the easiest to understand. And indeed, I should have tried to reduce the problem to the known case. Thank you! Also, I suppose we can prove that the distribution of $B^2$ is indeed the same in both $\mathcal{U}(0, 1)$ and $\mathcal{U}(-1, +1)$ using the same CDF approach, right? $\endgroup$ Sep 9, 2020 at 4:25
  • 1
    $\begingroup$ @HungryBlueDev Exactly right, yes. :-) $\endgroup$ Sep 9, 2020 at 12:05
  • 4
    $\begingroup$ A core idea in analysis, and frankly all of mathematics, "can I reduce this to a problem I can already solve?" $\endgroup$
    – John
    Sep 9, 2020 at 21:34
41
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ Hereafter, $\ds{\bracks{P}}$ is an Iverson Bracket. Namely, $\ds{\bracks{P} = \color{red}{1}}$ whenever $\ds{P}$ is $\ds{\tt true}$ and $\ds{\color{red}{0}}$ $\ds{\tt otherwise}$. They are very convenient whenever we have to manipulate constraints.


\begin{align} &\bbox[5px,#ffd]{\int_{-1}^{1}{1 \over 2}\int_{-1}^{1} {1 \over 2}\int_{-1}^{1}{1 \over 2}\bracks{b^{2} - 4ac > 0} \dd c\,\dd a\,\dd b} \\[5mm] = &\ {1 \over 4}\int_{0}^{1}\int_{-1}^{1} \int_{-1}^{1}\bracks{b^{2} - 4ac > 0} \dd c\,\dd a\,\dd b \\[5mm] = &\ {1 \over 4}\int_{0}^{1}\int_{-1}^{1} \int_{0}^{1}\braces{\bracks{b^{2} - 4ac > 0} + \bracks{b^{2} + 4ac > 0}} \dd c\,\dd a\,\dd b \\[5mm] = &\ {1 \over 4}\int_{0}^{1}\int_{0}^{1} \int_{0}^{1}\left\{\bracks{b^{2} - 4ac > 0} + \bracks{b^{2} + 4ac > 0}\right. \\[2mm] &\ \phantom{{1 \over 4}\int_{0}^{1}\int_{-1}^{1} \int_{0}^{1}} \left. + \bracks{b^{2} + 4ac > 0} + \bracks{b^{2} - 4ac > 0}\right\}\dd c\,\dd a\,\dd b \\[5mm] = &\ {1 \over 2} + {1 \over 2}\int_{0}^{1}\int_{0}^{1}\int_{0}^{1} \bracks{b^{2} - 4ac > 0}\dd c\,\dd a\,\dd b \\[5mm] = &\ {1 \over 2} + {1 \over 2}\int_{0}^{1}\int_{0}^{1}{1 \over a}\int_{0}^{a} \bracks{b^{2} - 4c > 0}\dd c\,\dd a\,\dd b \\[5mm] = &\ {1 \over 2} + {1 \over 2}\int_{0}^{1}\int_{0}^{1}\bracks{b^{2} - 4c > 0} \int_{c}^{1}{1 \over a}\,\dd a\,\dd c\,\dd b \\[5mm] = &\ {1 \over 2} - {1 \over 2}\int_{0}^{1}\int_{0}^{1} \bracks{c < {b^{2} \over 4}}\ln\pars{c}\,\dd c\,\dd b \\[5mm] = &\ {1 \over 2} - {1 \over 2}\int_{0}^{1}\int_{0}^{b^{2}/4} \ln\pars{c}\,\dd c\,\dd b \\[5mm] = &\ {1 \over 2} - {1 \over 2}\int_{0}^{1}\bracks{% -\,{1 + 2\ln\pars{2} \over 4}\,b^{2} + {1 \over 2}\,b^{2}\ln\pars{b}}\,\dd b \\[5mm] = & \bbx{{\ln\pars{2} \over 12} + {41 \over 72}} \approx 0.6272 \\ & \end{align}
$\endgroup$
8
  • 2
    $\begingroup$ @HungryBlueDev We can assume $[b^2 + 4ac > 0] = 1$ since the integrals are from $0$ to $1$. $\endgroup$
    – chi
    Sep 9, 2020 at 7:24
  • 1
    $\begingroup$ @HungryBlueDev Once we switch the integration to $\displaystyle\left(0,1\right)^{3},\ \left[b^{2} + 4ac > 0\right] = \color{red}{1}$ which makes the integration with those terms a trivial one. Hoever, we still have to take care of the other one: $\left[b^{2} + 4ac > 0\right]$. Thanks. $\endgroup$ Sep 9, 2020 at 16:42
  • 1
    $\begingroup$ In the last line of my previous comment, it must be $\left[b^{2} \color{red}{-} 4ac > 0\right]$. Sorry. $\endgroup$ Sep 9, 2020 at 19:15
  • 2
    $\begingroup$ This is my favorite of all the answers, even if I upvoted all of them. I hope more people use Iversonian brackets. $\endgroup$ Sep 11, 2020 at 8:10
  • 1
    $\begingroup$ @HungryBlueDev It's equivalent to $\displaystyle ac = t \implies \mathrm{d}c = \mathrm{d}t/\color{red}{a}$. Later on, we rename $\displaystyle t$ as $\displaystyle c$. That is usually done to be brief. $\endgroup$ Sep 24, 2020 at 15:59
21
$\begingroup$

We know from the quadratic formula that the polynomial $Ax^2 + Bx + C$ has real roots if $B^2 - 4AC \geq 0$. We can think of this problem in terms of volumes. To do so, it's easier if we rename the coefficients as $x \equiv A$, $y \equiv C$, and $z \equiv B$. Hence, in order to have real roots we require that $z^2 \geq 4xy$ for $x,y,z \in (-1,1)$. The probability we are after is the ratio between the volume of the region for which this inequality is true and the volume of the containing cube, which is 8. Begin by observing that if $x$ and $y$ have opposite signs then this inequality is trivially satisfied. The volume of the region for which they have opposite signs 4. Now consider the case where $x$ and $y$ have the same signs. In this case, we want to compute the volume above the surface $z^2 = 4xy$ and below the containing cube. There are four cases to consider:

  1. $-1 < x \leq -\frac{1}{4}$ and $\frac{1}{4x} \leq y \leq 0$.
  2. $-\frac{1}{4} \leq x \leq 0$ and $-1 < y \leq 0$.
  3. $0 \leq x \leq \frac{1}{4}$ and $0 \leq y < 1$.
  4. $\frac{1}{4} \leq x < 1$ and $0 \leq y \leq \frac{1}{4x}$.

By symmetry we can just consider cases 1 and 2 and then multiply that volume by 2. In each case we have to compute the integral: \begin{align*} \int_a^b\int_c^d 2 - 4\sqrt{xy}\,dy\,dx, \end{align*} where the limits of integration are defined above. Evaluating cases 1 and 2 we find that the volume is $5/18 + (1/6)\ln(4)$. Hence, the total volume that satisfies the inequality is \begin{align*} 4 + 2\left(\frac{5}{18} + \frac{1}{6}\ln(4)\right) = \frac{41}{9} + \frac{1}{3}\ln(4) \end{align*} which leads to a probability of \begin{align*} \frac{1}{8}\left(\frac{41}{9} + \frac{1}{3}\ln(4)\right) \approx 0.62721 \end{align*}

$\endgroup$
2
  • $\begingroup$ I find this volume approach to be very intuitive. Thank you! However, integration seems to be a weakness of mine. Can you recommend any books/courses/other resources I can use to improve in this aspect? $\endgroup$ Sep 9, 2020 at 4:01
  • 5
    $\begingroup$ This seems like a fantastic problem to give to a multivaraible calculus class. $\endgroup$ Sep 9, 2020 at 21:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .