| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1663.1 | Brute Force solution... | SSAG::LARY | Laughter & hope & a sock in the eye | Mon Sep 14 1992 01:44 | 32 |
| Since I can never remember the formula for solutions of a cubic, I tried a
graphical approach on this one. There will only be three real roots if:
(a) the cubic has two real inflection points (places where its slope is 0)
(b) The value of the cubic is =>0 at the left inflection point and <=0 at
the right inflection point. It will then intersect the x-axis 3 times
(or fewer times with one intersection being a tangent intersection,
yielding a double or triple root there).
Condition (a) is the same as the derivative having a positive discriminant, ie:
(1) b <= a�/3.
The conditions in (b) are obtained by substituting the roots of the derivative
of the cubic into the cubic, yielding
9ab - 2a� - 2*sqrt(a�-3b)� 9ab - 2a� + 2*sqrt(a�-3b)�
(2) -------------------------- <= c <= --------------------------
27 27
Now, the right side of (2) is less than 1 for all a,b in [0,1] with b <= a�/3,
whereas the left side of (2) is only => 0 when b => a�/4, so the left side must
be "clipped" into [0,1]. So, the probability of having 3 real roots is given
by the volume under the constraint equations (1) and (2), suitably clipped, or:
P = Int(a=0 to 1) Int(b=0 to a�/3) [right side of (2)] da db
- Int(a=0 to 1) Int(b=a�/4 to a�/3) [left side of (2)] da db
Or, P = 1/2880
(A lot less than I expected!)
|
| 1663.2 | an attempt at a start to solve this | STAR::ABBASI | Spell checking is a family value | Mon Sep 14 1992 02:34 | 33 |
|
all roots are real if
q^3+r^2 <= 0
where
q= 1/3 B - 1/9 A^2
and
r= 1/6 (BA-3C)- 1/27 A^3
so ask, what is probability that q^3+r^2 <=0 ?
or after expanding and simplifying:
what is probability that
1/27 B^3 - 1/108 B^2 A^2 - 1/6 BCA + 1/4 C^2 + 1/27 CA^3 <=0 ?
since B,A,C are all >= 0, then we must have
1/27 B^3 + 1/4 C^2 + 1/27 CA^3 <= 1/108 B^2 A^2 + 1/6 BCA --- (1)
for all roots to be real.
what is probability of (1) being true?
rewrite (1) as
4 B^3 + 27 C^2 + 4 CA^3 <= B^2 A^2 + 18 BCA -- (2)
so we ask, what is probability of (2) being true?
I leave the rest as an excersise for the reader, I want to go and sleep ;-)
/Nasser
|
| 1663.3 | | SSAG::LARY | Laughter & hope & a sock in the eye | Mon Sep 28 1992 15:10 | 15 |
| > 9ab - 2a� - 2*sqrt(a�-3b)� 9ab - 2a� + 2*sqrt(a�-3b)�
>(2) -------------------------- <= c <= --------------------------
> 27 27
>
>Now, the right side of (2) is less than 1 for all a,b in [0,1] with b <= a�/3,
>whereas the left side of (2) is only => 0 when b => a�/4, so the left side must
>be "clipped" into [0,1]...
Of course, it goes without saying that the right side is also >= 0 for all
a,b in [0,1] (he said, scrambling hard to regain his lost rigor)...
[Actually, it isn't all that obvious, but you can use the handydandy inequality
"sqrt(1-x)� >= 1 - 3x/2 for x in [0,1]" to prove it, and the Binomial Theorem
to prove the inequality...]
|
| 1663.4 | | VMSDEV::HALLYB | Fish have no concept of fire. | Mon Sep 28 1992 17:01 | 2 |
| p.s., a hack BASIC Monte Carlo program, run for mega-trials,
numerically verified Richie's answer.
|
| 1663.5 | Onward... | SSAG::LARY | Laughter & hope & a sock in the eye | Mon Sep 28 1992 21:23 | 20 |
| Thanks for verifying it!
Now, of course, as is customary in MATH notes, we need to generalize the
problem. Let P(N) be the probability that a unary Nth degree polynomial
with uniform random coefficients in [0,1] has all real roots.
(1) Prove that P(N) > 0 when N > 0. This looks like it would be easy if
I knew enough algebra/analysis, but I can't get a handle on it...
(2) Given (1),
P(1) = 1
P(2) = 1/12 (easy to derive)
P(3) = 1/2880 (from note 1663.1)
P(4) = ??
P(N) = ?? (closed form function of N)
Sum(N=1 to inf) P(N) = ????? (numeric value)
|