Let $p_1(x)$ and $p_2(x)$ be cubic polynomials with
random coefficients in $[-1,1]$.
I wanted to compute the probability that $p_1$ and $p_2$
share at least one point within
the square $[-1,1]^2$.
Of course this is the same as the probability that
$p_1(x)=p_2(x)$ for $x \in [-1,1]$ and $p_1(x) \in [-1,1]$.
I am not seeing this as a straightforward computation
based on known root distribution results for random polynomials,
but I admit to ignorance in this area.
Crude experimentation suggests the probability might not be
far from $\frac{1}{2}$.
Below, $5$ out of $9$ instances meet within the $[-1,1]^2$ square.
My interest derives from graphics and cubic splines.
I wanted to understand how likely it would be that the
(relatively expensive) root computation would be necessary
to compute certain graphic representations, e.g., visibility
from above.
1 Answer
If $p_i(x)=a_ix^3+b_{i,2}x^2 + b_{i,1}x + b_{i,2}$ for $i\in\{1,2\}$ then a sufficient condition for $\exists (x,y)\in [-1,1]^2$ with $y=p_1(x)=p_2(x)$ is that (writing $a=a_1-a_2$, $b_j=b_{1,j}-b_{2,j}$) \begin{eqnarray} \tag{1}\sum_{j=0}^2 |b_{j}|\le |a|\quad\text{and}\\ \tag{2}|a_i| + \sum_{j=0}^2 |b_{i,j}| \le 1\quad\exists i\in\{1,2\} \end{eqnarray} and this gives a nonzero lower bound of approximately $0.02$ on the probability (an 8-fold multiple integral which it is tricky to get Mathematica to do).
Indeed, it is easy to see that with probability 1 there exist $(x,y)\in\mathbb R^2$ with $y=p_1(x)=p_2(x)$; consider one such pair. If $|x|\ge 1$ then we have by (1) $$ |ax|\le |b_2| + \frac{|b_1|}{|x|} + \frac{|b_2|}{|x|^2} \le \sum_j |b_j|\le |a| $$ so $|x|\le 1$ after all. To ensure $|y|\le 1$ we use (2).
-
$\begingroup$ You can ask WolframAlpha to evaluate the probability of (2), via NIntegrate[ Boole[a + Abs[b] + Abs[c] + Abs[d] < 1], {a, -1, 1}, {b, -1, 1}, {c, -1, 1}, {d, -1, 1}]/16. This gives 0.27, so your lower bound is between 0 and 0.27^2 = 0.073. I similarly asked Mathematica to evaluate the 8-fold integral for (1) and (2), and it complained about slow convergence, saying: "NIntegrate obtained 0.02 and 0.04 for the integral and error estimates". $\endgroup$– user44143Commented Feb 25, 2014 at 8:39
-
$\begingroup$ I also got about 0.02 using Mathematica, so I incorporated that into the answer. $\endgroup$ Commented Feb 25, 2014 at 23:21
Probability[ And @@ (-1 <= # <= 1 & /@ {x, a x + b} /. Solve[a x + b == c x + d, x] // First), {a, b, c, d} \[Distributed] UniformDistribution[{{-1, 1}, {-1, 1}, {-1, 1}, {-1, 1}}]]
gives the exact result $47/96\approx0.48958...$. $\endgroup$