12
$\begingroup$

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.
      PolyInt3x3
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.

$\endgroup$
9
  • 3
    $\begingroup$ I simulated 100,000 cases, and the result in the form of {# of zeros, frequency (%)} is as follows: {{0, 39.179}, {1, 48.567}, {2, 10.847}, {3, 1.407}} That is, about 40% of total cases had no zero. $\endgroup$ Feb 22, 2014 at 5:26
  • 2
    $\begingroup$ For what it's worth, this is exactly a question about the number of roots in [-1,1] of a random cubic with coefficients taken from a "witch's hat" distribution on [-2,2]. $\endgroup$ Feb 22, 2014 at 6:49
  • 4
    $\begingroup$ @Anthony Quas: That ignores the restriction on the $y$-coordinate. The graphs of $(x^3+3x)/3$ and $(3x^2+1)/3$ meet at $(1,4/3)$ which is outside $[-1,1]^2$. $\endgroup$ Feb 22, 2014 at 9:21
  • 2
    $\begingroup$ Indeed, the Mathematica command 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$
    – Eckhard
    Feb 22, 2014 at 19:21
  • 2
    $\begingroup$ If you don't restrict the $y$-coordinate of the intersection then the probability for two lines is exactly $1/2$ by the involution swapping the linear and constant coefficients. The x-coordinate of the point of intersection of $\lbrace a_i x + b_i\rbrace $ is $-\frac{b_1-b_0}{a_1-a_0}$. The deficit from $1/2$ comes from the times the lines intersect with $x \in [-1,1], y \notin [-1,1]$ like $0.3 x + 0.9$ and $0.8 x + 0.5$ which intersect at $(0.8,1.14)$. $\endgroup$ Feb 22, 2014 at 20:09

1 Answer 1

3
$\begingroup$

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).

$\endgroup$
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$
    – Matt F.
    Feb 25, 2014 at 8:39
  • $\begingroup$ I also got about 0.02 using Mathematica, so I incorporated that into the answer. $\endgroup$ Feb 25, 2014 at 23:21

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.