Raíces y probabilidad

Hoy, como es habitual, os traigo el problema de la semana. Es el siguiente:

Calcular la probabilidad de que la ecuación de segundo grado con coeficientes reales

$ax^2+bx+c=0$

tenga raíces reales.

Se entiende dicha probabilidad en el caso límite cuando $N \to \infty$ , tomando coeficientes $a,b,c \in [ -N,N ]$ .

30 comentarios

Trackback | 2 Feb, 2010

Bitacoras.com
Dani | 2 de February de 2010 | 10:31

1/2
josejuan | 2 de February de 2010 | 10:45

Creo que no es 1/2, pero estoy en ello…
Dani | 2 de February de 2010 | 11:06

se trata de ver en qué proporción del cubo $\[ -N, N \]^3 \subset \mathbb{R}^3$ las variables aleatorias $X,Y,Z \sim \text{Unif}(-N,N)$ cumplen $Y^2 \geq 4 X Z$ , es decir, que el discriminante de $Xx^2 + Yx + Z = 0$ sea positivo.
$\mathbb{P}(Y^2 \geq 4XZ)=$
$\mathbb{P}(Y^2 \geq 4XZ | X\geq0)\mathbb{P}(X\geq 0)+\mathbb{P}(Y^2 \geq 4XZ | X \prec 0)\mathbb{P}(X \prec 0)$
Claramente por tratarse de VAs continuas la desigualdad estricta o no estricta da igual.
Ahora bien, si $X \succ 0$ , entonces la condición equivale a $Z \leq \frac{Y^2}{4X}$ , y entonces la proporción del cubo $\[ -N, N \]^3$ que nos interesa es la que está encerrada debajo de la gráfica de $z=\frac{y^2}{4x}$ para $x \geq 0$ (notad que no hay problema al acercarse a cero, pintadlo!)
Por otra parte, si $X \prec 0$ , entonces la condición es $Z \geq \frac{Y^2}{4X}$ , y como ahora la gráfica está “invertida” por cambiar el $x$ negativo el signo de todo, la proporción es la misma y basta con calcular el caso $X \succ 0$ . Tenía razón Josejua, no es $\frac{1}{2}$ , es $\frac{41}{72} + \frac{1}{24}\log(4)$ o algo así, ahora hago la cuenta.
Dani | 2 de February de 2010 | 11:30

En efecto veamos cual es la proporción en $\[0,N] \times [-N,N]^2$ que cae debajo de la gráfica de $z=\frac{y^2}{4x}$ . Veamos lo que ocurre entre el eje $z=0$ y la gráfica. Si $0\leq x_0 \leq \frac{N}{4}$ , entonces las parábolas $z=\frac{y^2}{4x_0}$ “tocan al techo”. En ese caso notamos que el punto en el que se “salen” de nuestro cubo es cuando $N=\frac{y^2}{4x_0} \Leftrightarrow y^2=4x_0N$ . Tenemos entonces que considerar en ese corte el area dada por los dos rectángulos laterales (cuando ya se ha salido la gráfica del cubo) que suman area igual a $2 \times N(N-2 \sqrt{x_0N})$ . Aparte de eso el area que cae debajo de la parabola se calcula como:
$\int_{-2\sqrt{x_0N}}^{2\sqrt{x_0N}} \frac{y^2}{4x_0} dy =\frac{4}{3}N\sqrt{x_0N}$ Resumiendo: en un corte $x=x_0$ para $0 \leq x_0 \leq \frac{N}{4}$ el area obtenida es:
$2N(N-2 \sqrt{x_0N}) + \frac{4}{3}N\sqrt{x_0N}$

Por otra parte si el corte es en $\frac{N}{4} \leq x_0 \leq N$ el area obtenida es simplemente
$\int_{-N}^{N} \frac{y^2}{4x_0} dy= \frac{N^3}{6x_0}$
Integramos para hallar el volumen:
$V= \int_{0}^{\frac{N}{4}}2N(N-2 \sqrt{xN}) + \frac{4}{3}N\sqrt{xN} dx + \int_{\frac{N}{4}}^{N}\frac{N^3}{6x} dx$
$= \Big[ 2N^2x - \frac{16}{9}(xN)^\frac{3}{2} \Big ]_0^{N/4} + \Big[ \frac{N^3}{6}\log(x) \Big]_{N/4}^{N}$
$=\frac{1}{2}N^3 -\frac{2}{9}N^3 + \frac{N^3}{6} \log(4)$ .

No nos podemos olvidar de sumarle todo lo que queda en $z\leq 0$ , puesto que esto también contribuye por cumplirse las condiciones en está región. Tiene volumen $2N^3$ , y todo junto da: $N^3 ( \frac{41}{18} + \frac{1}{6} \log(4) )$ . Dividimos por el volumen total, que es $4N^3$ para obtener la proporción

$\frac{41}{72} + \frac{1}{24}\log(4)$ ,
que por mi post anterior es la probabilidad pedida.
josejuan | 2 de February de 2010 | 11:46

Sí, eso es lo que me salía a mí, pero no encontré una forma de reducir el volumen.
M | 2 de February de 2010 | 13:03

Muy buena, Dani! Ese es el valor pedido.
Dani | 2 de February de 2010 | 14:15

es curioso que no haya que tomar ningún límite, es decir, que la probabilidad sea la misma sea cual sea el cubo en el que escojas los coeficientes. Sería interesante plantearse la misma pregunta exigiendo, por ejemplo, $a^2 + b^2 + c^2 \leq M$ y luego tomar $M \rightarrow \infty$
josejuan | 2 de February de 2010 | 14:48

Creo que en tal caso, estaríamos aproximando el cubo a una esfera y por tanto, cuando M aumenta, la diferencia es menor.

Es decir, el conjunto de probabilidades que “estan” en la esfera y no en el cubo (conteniendo uno al otro) aumenta proporcionalmente al volumen interior de ambos respecto al exterior.

Vaya, que la solución tiende asintóticamente a la tuya del problema inicial.

Además debería ser bastante rápido, pues el volumen interior aumenta cúbicamente.

Creo…
josejuan | 2 de February de 2010 | 14:57

Resolviendo numéricamente (Montecarlo):

http://jose-juan.computer-mind.com/jose-juan/img/gt/gfx1.png
josejuan | 2 de February de 2010 | 14:59

Habría que ver si el “trocito” que la esfera nunca llega a alcanzar (del cubo) se aproxima a cero o rebaja la cota…
josejuan | 2 de February de 2010 | 15:06

Uhm… en el infinito ¿un cubo y una esfera tienen el mismo volumen?, sí, pues entonces parece que da igual qué estructura convexa se elija, la solución debería tender asintóticamente a tu solución inicial (sea una esfera, un prisma, etc…).

Sería interesante ver entonces si un perímetro no convexo del problema (la restricción a ‘a’, ‘b’ y ‘c’) mantiene su estructura en el infinito o la pierde.
josejuan | 2 de February de 2010 | 15:12

Ugh! vale, creo que no tiene que ver con el tamaño del recinto, sino con la proporción de soluciones reales versus complejas por unidad de volumen, por lo que curiosamente si tomamos una estructura tubular (por ejemplo la representación 3D típica de enlaces químicos) ¡la solución tendería al mismo valor!

¿no?
josejuan | 2 de February de 2010 | 15:16

Y ya por divagar del todo, en un entorno del 0, hemos visto (numéricamente) que hay más soluciones complejas que reales, ¿cómo entonces se distribuyen dichas soluciones en todo el espacio? dicho de otra forma, aun cuando las soluciones reales y/o complejas fueran densas en todo el espacio, ¿cómo de densas son en un sitio y en otro? (ya hemos visto que “cerca” del cero cambian).

Sería algo así como obtener la representación de un campo vectorial (un gas, etc…).

Perdón por el desvarío.
antonio | 2 de February de 2010 | 16:24

Mi intuicion me ha fallado.
Si me hago la pregunta cómo la probabilidad de que las soluciones no sean imaginarias, parece que tengo que comparar el área de un rectángulo abierto (parte del plano complejo) con el área de un segmento cerrado [-N,N].Y yo diría probablilidad cero.
Parece que las soluciones prefieren situarse en la recta real más que en el plano complejo.
josejuan | 2 de February de 2010 | 17:27

En fin, espero que no me echen por pesado…

Si hacemos rodajas en el plano B, entonces la representación de 4AC es una silla de montar, que divide las soluciones reales y complejas.

Si vamos montando las sillas de montar a lo largo del eje B (superponiendo proyecciones sobre planos B) tenemos una especie de parabólica de sillas de montar.

Y ya está, ni espacio vectorial ni gases ni leches…
M | 2 de February de 2010 | 18:56

Aunque no estoy nada puesto en el asunto, josejuan, mucho me temo que el valor de la probabilidad pedida depende la distribución asumida para los coeficientes. Asumiendo que los tres coeficientes son independientes y se distribuyen uniformemente en un cubo entonces la respuesta es la que ha dado Dani (aprox. 0’6272067…).

Sin embargo, si se considera que los coeficientes son independientes con distribución normal (con media cero), entonces la probabilidad aumenta a 0’64851… Esto es consecuencia de la fórmula de Kac: para n=2 el número esperado de raíces reales es 1.29702… y se obtiene la probabilidad dividiendo entre dos (posibles raíces). Ver

http://mathworld.wolfram.com/KacFormula.html

http://arxiv.org/abs/math/9501224

Por otro lado, para el caso que plantea Dani los coeficientes ya no son ni siquiera independientes. Para este caso, estoy revisando las cuentas (integración triple).
josejuan | 2 de February de 2010 | 19:39

Desde luego en poco rato me ha dado tiempo a decir muchas tonterías, sin embargo, la distribución de los coeficientes siempre se ha supuesto uniforme en el espacio considerado (pues no se ha dado ninguna), lógicamente si se cambia la distribución de probabilidad de los coeficientes cambiará la probabilidad de obtener una raíz real o compleja ¡pues las raíces dependen funcionalmente de los coeficientes!.

El caso que plantea Dani de restringir los coeficientes a cumplir a^2+b^2+c^2<=N (si no lo he interpretado mal) no cambia la distribución, únicamente el espacio muestral (claro, si cambiamos el espacio muestral forzosamente cambiará la distribución, pero estamos hablando del tipo de distribución) y cuando el tamaño tiende a infinito, dicho espacio es equivalente tenga la forma que tenga el “recinto” inicial, siempre que sea convexo.

Mi majadero error (entre otros) ha sido pensar que las soluciones podían ser (+ o -) densas en el espacio cuando están perfectamente delimitadas (claro b^2>=4ac).

Esto en cuanto a la forma del espacio muestral (un cubo, una esfera, etc…), ahora añadiendo el tema de la distribución, pues podríamos usar una que diera más importancia a unas y a otras, por ejemplo, podríamos establecer que la función de densidad es siempre 0 cuando el signo de A y C coinciden, en cuyo caso se incrementará notablemente la probabilidad de una raíz real (claro, ¡es 1!).

Uff… me veo en la oblicación de disculparme, mi berborrea (caotica) es hoy “ladrillante”.
Dani | 2 de February de 2010 | 19:48

Si el soporte de la fución de densidad conjunta de las VAs $X,Y,Z$ es $B(0,M)=\{ x \in \mathbb{R}^3 : ||x||\leq M \}$ no pueden ser independientes, ya que es obvio que no se pueden factorizar como el producto de las respectivas funciones de densidad de $X,Y,Z$ . Para poner un ejemplo, si sabemos que $X=0$ , $Y,Z$ pueden variar en un círculo de radio $M$ , mientras que si $X=\frac{M}{2}$ sólo lo podrán hacer en uno de radio $\frac{M\sqrt{3}}{2}$ . Esto cambia completamente la situación, y no veo nada obvio que vaya a dar el mismo resultado.
Dani | 2 de February de 2010 | 19:50

creo que viene de perlas la frase que discutimos hace nada:

“La generación de números aleatorios es una cuestión demasiado importante para dejarla al azar.”
Donald Knuth
M | 2 de February de 2010 | 20:38

Haciendo las cuentas para la cuestión de Dani, debo reconocer que me sorprendió al principio que no obtuviera el mismo resultado. Tras revisar las cuentas creo que para el caso que plantea Dani el resultado es el mismo que se obtiene asumiendo independencia y normalidad (o al menos se le aproxima bastante). Ahí van mis cuentas para ver que ahora la probabilidad es $0.648511787\ldots$ (y de nuevo veremos que es independiente del radio de la esfera)

Consideramos la ecuación $ax^2+bx+c=0$ , con $a,b,c$ uniformemente elegidas en una esfera de radio $R$ : $a^2+b^2+c^2\leq R^2$ . Queremos hallar la probabilidad de que $\Delta:=b^2-4ac\geq 0$ . Notar que si $sign(a)\neq sign(c)$ entonces la probabilidad es uno, y para el caso $sign(a)=sign(c)$ podemos asumir sin pérdida de generalidad que $a,c\geq 0$ . Entonces, como nos movemos en un cuarto de la esfera, la probabilidad buscada será $p=\frac{1}{2}+\frac{1}{2}\frac{1}{\frac{\pi}{3}R^3}I_1$ , donde $I_1:=\iiint_{\Omega_1} \chi(\Delta)da\; db\; dc$ , siendo $\chi$ la función característica (vale 1 si el argumento es no negativo, y cero en otro caso), y $\Omega_1:=\{(a,b,c)/\;a,c\geq 0,\;a^2+b^2+c^2\leq R^2\}$ .

Integraremos primero repecto a $b$ . Fijados $a,c$ , tendremos $4ac\leq b^2\leq R^2-(a^2+c^2)$ , y como $b$ puede ser positivo o negativo, tendremos que $I_1=\iint_{\Omega_2} 2(\sqrt{R^2-(a^2+c^2)}-2\sqrt{ac})=:I_2$ , con $\Omega_2:=\{(a,c)\geq 0, \;a^2+c^2+4ac\leq R^2\}$ .

Calculamos $I_2$ en polares: $a=\rho cos \theta$ , $c=\rho sin \theta$ , con $\theta\in[0,\pi/2]$ (pues $a,c\geq 0$ ). De $a^2+c^2+4ac\leq R^2$ , obtenemos $0\leq \rho \leq \frac{R}{\sqrt{1+2sin(2\theta)}}=:\rho^*(\theta)$ . Luego:

$I_2=2\int_0^{\frac{\pi}{2}} \int_0^{\rho^*(\theta)} (\sqrt{R^2-\rho^2}-\rho\sqrt{2sin(2\theta)})\rho d\rho\;d\theta$ .

Integrando respecto a $\rho$ obtenemos que $I_2=\frac{2R^3}{3}\int_0^{\frac{\pi}{2}} \left(1-\dfrac{\sqrt{2sin(2\theta)}}{\sqrt{1+2sin(2\theta)}}\right)d\theta$ , y esta integral parece que no se expresa de modo elemental (el Mathematica no la calcula).

Así pues $p=\frac{1}{2}+\frac{1}{\pi}\int_0^{\frac{\pi}{2}} \left(1-\dfrac{\sqrt{2sin(2\theta)}}{\sqrt{1+2sin(2\theta)}}\right)d\theta\doteq 0.648511787\ldots$
Dani | 2 de February de 2010 | 21:35

fantástico! me sigue pareciendo muy curiosa la invarianza por escala que ocurre tanto al elegir un cubo o una esfera como soporte de densidad para coeficientes uniformemente distribuidos. Por otra parte, ¿por qué precisamente en el caso de la esfera obtenemos la probabilidad correspondiente a una distribución normal? posiblemente la simetría tenga algo que decir ahí, pero no veo la relación así de primeras. Además, en todo caso la simetría sugeriría que haciendo crecer el radio coincidiría en el límite, sin embargo parece ser que coinciden aunque escojamos una esfera muy pequeña! $b^2 \geq 4ac $ es una condición tan arbitraria y tan sencilla que me pregunto ideas interesantes detrás de todo esto…
con alguna otra condición similar, será también cierta la correspondencia coeficientes uniformes en esfera-normal + independcia?
por desgracia las cuentas se vuelven bastante horribles a la hora de probar con ejemplos…
Alonso Montero | 3 de February de 2010 | 08:14

Realicé una simulación, y si comprendí bien el problema, la probabilidad es de 61.8%.
josejuan | 3 de February de 2010 | 10:22

“Dani”, tanto el cubo como la esfera están centrados en el origen, por tanto, dada la ecuación

$z^{2}=4xy$

tenemos un doble cono (vaya, un cono normal y corriente) revolucionado sobre el eje X=Y.

Tanto el truncamiento del cubo como de la esfera sobre el cono es independiente de la escala.

En la imagen creo que se ve claramente:
http://jose-juan.computer-mind.com/jose-juan/img/gt/cono.png

- blanco, espacio en que signo(x)=-signo(y) y por tanto son todas soluciones reales.
- rojo, espacio en que signo(x)=signo(y) que comparten la esfera y el cubo.
- azul, espacio en que signo(x)=signo(y) que únicamente está en el cubo.

Mi hipótesis (refutada por el cálculo de “M”) era que esa “esquinita azul” se “diluía” en el infinito. Pero ahora (como muchas veces “a toro pasa’o”) se ve fácilmente que la proporción se mantiene para todo N.
Dani | 3 de February de 2010 | 11:31

jejeje qué boitos los dibujos, tengo que aprender a hacer cosas así
sin embargo te equivocas en cuanto a que la figura no es un cono. eso haría las cosas muuuucho más simples jejeje
para ver que no es un cono fíjate que si cortásemos con cualquier plano que contenga a su supuesto eje de rotación (necesariamente sería por el dibuo $x=y, z=0$ ), tendríamos que obtener dos rectas con el mismo ángulo interno independientemente del plano con el que cortemos. con z=0 se tiene x=0 o y=0, lo que daría un ángulo interno de $\frac{\pi}{2}$ , mientras que si cortas con x=y obtienes $|z|=2|x|$ que no tiene el mismo ángulo interno.
Por su naturaleza eso tiene “algo” de hiperbólico.
josejuan | 3 de February de 2010 | 11:51

Es verdad, no es un cono “de verdad”.

Dada la expresión

$z^{2}=4xy$

tenemos una “especie” de cono revolucionado sobre el eje X=Y (Z=0 para ser exactos) en la que la diferencia con un cono “de verdad” (de los buenos) está dada por

$4xy=x^{2}+y^{2}$

es decir

$x=y(2\pm \sqrt{3})$

y por tanto la deformación del cono es lineal y proporcional a la constante y respecto los signos de los ejes X e Y, por lo que “las ovejas que entran por las que salen” el resultado viene a ser el mismo (aunque por supuesto antes estaba mal).

Es decir, si hacemos el corte, obtenemos dos líneas con ángulos diferentes, pero la recta con ángulo mayor en uno de los conos es la recta con menor ángulo en el cono simétrico y al revés (con la otra recta).

Y así, volvemos a tener la misma figura escalemos lo que escalemos.

(Digo yo, porque la verdad, me empieza a dar vueltas la cabeza…)
M | 3 de February de 2010 | 13:12

Decir que definitivamente las probabilidades en el caso de normalidad y en el caso de la esfera de Dani sí coinciden (exactamente). La integral de Kac para $n=2$ (divida por dos)

$\frac{2}{\pi}\int_0^1 \displaystyle{\sqrt{\frac{1}{(1-t^2)^2}-\frac{9t^4}{(1-t^6)^2}}}$

coincide con la integral que puse en mi último comentario

$1-\frac{1}{\pi}\int_0^{\frac{\pi}{2}} \dfrac{\sqrt{2sin(2\theta)}}{\sqrt{1+2sin(2\theta)}}d\theta$ .
Dani | 4 de February de 2010 | 12:31

tienes alguna idea para explicar este hecho, M?
M | 5 de February de 2010 | 00:25

Dani, la verdad es que no tengo ni idea. Sin embargo según se puede leer en el abstract del trabajo de Edelman y Kostlan (enlace al arxiv que indiqué en un comentario previo)

“We show that the expected number of real zeros is simply the length of the moment curve $(1,t,\ldots,t^n)$ projected onto the surface of the unit sphere, divided by $\pi$”

y en el último párrafo de la página 5 del pdf: “If the $a_i$ are independent standard normals, then the vector $a$ is uniformly distributed on the sphere $S^n$ ” (además vimos que la probabilidad no dependía del radio de la esfera y esto parece consecuencia de la normalización del vector de coeficientes que se hace en esa página).

Habría que leerse bien el trabajo (según los autores sólo requiere matemáticas asequibles, y así parece en las primeras páginas). Ahí puede estar la clave del asunto.
Trackback | 6 Feb, 2010

Twitter Trackbacks for Raíces y probabilidad | Gaussianos [gaussianos.com] on Topsy.com