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$ Commented 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$ Commented 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$ Commented 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
    Commented 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$ Commented 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$
    – user44143
    Commented 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

You must log in to answer this question.

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