Nada es infinito excepto…

…el desarrollo de Half-Life 2: Episodio 3 a manos de Gabe Newell.

Una obra de Abstruse Goose.

Publicado en Uncategorized | Etiquetado , , , , , , , | Deja un comentario

Calculadoras, senos y matrices

Después de dos entradas haciendo especial énfasis en la utilización de las matrices, creo que ya sabéis una de las patas de las que cojea este blog (pero como tenemos muchas, no nos preocupa).

Escribiendo la primera entrada acerca de las funciones generatrices me hice una pregunta muy tonta, pero que en realidad me comía por dentro…

¿cómo calculará una calculadora el seno de un ángulo?

Y pensé, cosa rara en mí, ‘…seguro que tiene implementada la serie de Taylor’.  ¡Tenía sentido! La serie de Taylor del seno en torno a x=0, con un error de no más de una centésima en el intervalo [-\pi,\pi], vimos que era,

\displaystyle f(x)=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\frac{x^9}{9!}

Aunque algo me escamaba: un algoritmo así requiere a priori un gran número de términos para obtener una buena aproximación y por tanto un buen número de multiplicaciones.

Así que empecé a buscar y encontré lo que parece ser el corazón de la mayoría de las calculadoras que se usan en la actualidad.

El algoritmo en cuestión se llama CORDICCoOrdinate Rotation DIgital Computer. Este algoritmo destaca por su simplicidad y por las operaciones necesarias para ejecutarlo: suma y bit shift, operaciones propias de la ALU de los microprocesadores. Esto hace de ORDIC un algoritmo muy rápido.

Veamos si soy capaz de explicarlo. Primero recordamos que, dado un vector en el plano u, éste puede girarse mediante la matriz,

\displaystyle R(\theta)=\begin{pmatrix}\cos\theta & -\sin\theta\\\sin\theta & \cos\theta\end{pmatrix}

Aplicando esta rotación a u, la relación entre el vector rotado, v, y u puede escribirse como,

\displaystyle \begin{cases}v_1 = \cos\theta \,u_1-\sin\theta \,u_2\\v_2 = \sin\theta \,u_1+\cos\theta \,u_2\end{cases}

que puede reescribirse también como,

\displaystyle \begin{cases}v_1 = \cos\theta \left(u_1-\tan\theta \,u_2\right)\\v_2 = \cos\theta\left(\tan\theta \,u_1+u_2\right)\end{cases}

La idea de CORDIC es aplicar sucesivas rotaciones a un vector inicial, de módulo o magnitud 1, hasta llegar al ángulo deseado. El vector inicial que suele tomarse por comodidad, y sentido común, es (1,0).

¿Por qué de módulo uno?

Porque todos los vectores de módulo 1 son de la forma,

\displaystyle (\cos\alpha,\sin\alpha)

para un cierto ángulo \alpha. Por tanto, el valor del seno, o coseno, de cualquier ángulo puede codificarse en un vector de módulo 1. 

Como comentábamos, el algoritmo consiste en realizar rotaciones. Rotaciones que no serán siempre en el mismo sentido y serán cada vez más y más pequeñas. De hecho, satisfaciendo,

\displaystyle \tan \theta_k = \pm\frac{1}{2^k}

El proceso es muy parecido al método de bisección: primero rotamos el vector inicial un ángulo de \theta_0 radianes y comparamos con el ángulo que buscamos \alpha. Si es menor, rotamos el vector en el mismo sentido que antes \theta_1 radianes, y en otro caso, rotamos en sentido contrario \theta_1 radianes…

Siguiendo con este proceso obtenemos una suma,

\displaystyle \theta_0+\theta_1+\theta_2+\theta_3-\theta_4+\theta_5-\theta_6-\theta_7-\theta_8+\theta_9+\cdots

que poco a poco (y no tan poco) se va pareciendo al valor de \alpha.

Metiendo la condición que hemos elegido para la tangente en las ecuaciones anteriores, vemos que en la rotación k+1 se tiene,

\displaystyle \begin{cases}v^{k+1}_1=\dfrac{1}{\sqrt{1+2^{-2k}}} \left(v^{k}_1-\dfrac{s}{2^k} v^{k}_2\right)\\v^{k+1}_2=\dfrac{1}{\sqrt{1+2^{-2k}}}\left(\dfrac{s}{2^k}v^{k}_1+v^{k}_2\right)\end{cases}

donde s será 1 o -1 dependiendo de si la rotación es antihoraria, o por el contrario, horaria.

¿Y cuántas rotaciones son necesarias?

Depende del nivel de detalle que queramos. Puede demostrarse que tras aplicar N+1 rotaciones se tiene,

\displaystyle \left|v^{N+1}_1 -\cos\alpha\right|\leq\frac{1}{2^N},\quad \left|v^{N+1}_2 -\sin\alpha\right|\leq \frac{1}{2^N}

Usando que,

\displaystyle 2^{-N} = 10^{-(\log_{10} 2)N} \approx 10^{-0.3 N}

vemos que tras 3 o 4 iteraciones del algoritmo se obtiene, como mínimo, una cifra significativa.

…tampoco converge muy rápido que se diga…

Toda la razón…pero como decíamos al principio, el algoritmo solo requiere de suma y bit shift (división por una potencia de 2). Aquí radica su fuerza.

Hombre…y multiplicación, ¿no?

¡No hace falta…casi! Realmente el factor \displaystyle \frac{1}{\sqrt{1+2^{-2k}}} es de normalización.

En lugar de aplicarlo en cada iteración, multiplicamos el acumulado al final del proceso. El algoritmo queda como sigue: primero las rotaciones,

\displaystyle \begin{cases}v^{k+1}_1=v^{k}_1-\dfrac{s}{2^k} v^{k}_2\\v^{k+1}_2=\dfrac{s}{2^k}v^{k}_1+v^{k}_2\end{cases}

y al final, la normalización,

\displaystyle \begin{cases}v^{N+1}_1 \leftarrow L_{N+1} v^{N+1}_1\\v^{N+1}_2 \leftarrow L_{N+1} v^{N+1}_2\end{cases}

donde \displaystyle L_{N+1}=\prod_{k=0}^{N}\frac{1}{\sqrt{1+2^{-2k}}}.

…¡entonces se multiplica!

 …¡pero sólo una vez!

Dependiendo del grado de aproximación que busquemos necesitaremos una constante de normalización u otra, pero ésta no dependerá del ángulo.

Por ejemplo, si queremos poder aproximar el seno y el coseno de un ángulo con hasta 20 cifras significativas basta guardarnos 70 constantes,

\displaystyle L_1,\ldots,L_{69}, L_{70}

y usar la adecuada en función del número de rotaciones.

Última pincelada: el algoritmo CORDIC fue desarrollado en 1959 por Jack E. Volder con fines militares y debemos comentar que su uso no se restringe al cálculo del seno y el coseno: puede adaptarse a funciones trigonométricas e hiperbólicas en general.

Espero que ahora cuando os pregunten,

…¿cómo calcula el seno una calculadora?

no digáis Taylor; decid CORDIC.

Os propongo echarle una ojeada a los siguientes artículos acerca del tema,

  1. CORDIC: How Hand Calculators Calculate de Alan Sultan.
  2. How Do Calculators Calculate Trigonometric Functions? de Jeremy M. Underwood y Bruce H. Edwards.

Esta entrada participa en El Carnaval de las Matemáticas de Abril de 2012, que tiene por anfitriones a DesEquiLIBROS. Lectura y Cultura.

Publicado en Uncategorized | Etiquetado , , , , , , , , , , , , , | 4 comentarios

Sobre gaussianas, dinosaurios y fiestas de cocktail (II)

Como ya vimos en la anterior entrega de este tema cuando sumamos N variables aleatorias con distribuciones de probabilidad idénticas la distribución de probabilidad resultante tiende a ser una gaussiana cuando N tiende a infinito.

¿Pero tienen que estar identicamente distribuídas sí o sí?

Pues aquí se puede ver una de las curiosidades del Teorema del Límite Central, y es que es un teorema que admite que se relajen mucho las condiciones. Dicho de otro modo, si no están identicamente distribuídas no dará una gaussiana perfecta cuando sume infinitas variables aleatorias, pero la distribución resultante seguirá pareciéndose mucho a
una gaussiana.

¿Y cómo mides lo que se parece una distribución a una gaussiana?

Existen múltiples métodos pero uno de los más extendidos es el apuntamiendo o kurtosis. Este parámetro, muy relacionado con el cuarto momento estadístico, mide cómo se concentran los valores de una distribución numérica en torno a su media. Esto, dicho de otra manera, significa que mide cómo de gaussiana es una distribución. La expresión de abajo detalla cómo se puede calcular la kurtosis de un conjunto de N muestras discretas.

\displaystyle g = \frac{N \cdot \sum_{i=1}^{N}(x_{i} - \mu)^4}{(\sum_{i=1}^{N}(x_{i} - \mu)^2)^2} - 3

Sí, muy interesante. ¿Y la aplicación? 

Para ver la aplicación de la que quería hablaros nos tenemos que vestir de gala. El “cocktail party problem” es uno de los problemas clásicos de la matemática y la teoría de la información. Supongamos que estamos en una fiesta en una sala cerrada. Hay varios invitados que conversan entre ellos, un grupo de música tocando música ambiental y los canapés están un poco secos (esto no es relevante pero suele pasar).  Por dicha sala hay distribuidos unos micrófonos captando el sonido ambiente. ¿Puedo obtener cada una de las conversaciones de la sala por separado observando únicamente las capturas de sonido ambiental?

La imagen de abajo pretende ilustrar este problema y ayudar a la comprensión del mismo. En este caso tenemos cuatro invitados hablando sobre sus temas, cada uno de ellos se puede modelar como una variable aleatoria con una distribución de probabilidad propia e independiente de las demás (esto es muy importante) y sus voces como observaciones de estas variables aleatorias (s1, s2, s3 y s4).

Además hemos dispuesto cuatro micrófonos por la sala capturando cada uno de ellos una suma de las voces de la sala. Sin embargo como cada uno de ellos está en  una posición distinta de la sala captara unas voces con más intensidad que otras. Matemáticamente hablando esto significa que tenemos una matriz de mezcla A, que multiplicada a la matriz de observaciones S nos da la matriz de capturas U.

\displaystyle U= \begin{pmatrix}u_{1}\\u_{2}\\u_{3}\\u_{4}\end{pmatrix}=\begin{pmatrix}a_{11}&a_{12}&a_{13}&a_{14}\\a_{21}&a_{22}&a_{23}&a_{24}\\a_{31}&a_{32}&a_{33}&a_{34}\\a_{41}&a_{42}&a_{43}&a_{44}\end{pmatrix}\begin{pmatrix}s_{1}\\s_{2}\\s_{3}\\s_{4}\end{pmatrix}=A \cdot S

O dicho de otra manera, cada uno de los micrófonos capta una combinación lineal {u1,u2, u3, u4} de las observaciones { s1, s2, s3 y s4} de las variables aleatorias mencionadas. ¿Cómo puedo, a partir de u1, u2, u3 y u4, recuperar s1, s2, s3 y s4?

La idea para resolver este problema es bastante sencilla. Vamos a construir una captura sintética y que sea una combinación lineal de las capturas obtenidas:

\displaystyle y =\sum_{i=1}^{4} b_{i}u_{i} =\sum_{i=1}^{4} c_{i}s_{i}

Como y es una combinación lineal de capturas será a su vez una captura, es decir una combinación lineal de las observaciones. La idea consiste en encontrar unos valores de bi tal que tres de los valores ci sean ceros o arbitrariamente bajos en comparación con el restante, para poder obtener de este modo alguna de las observaciones originales.

¿Y qué valores pones en bi? ¿Te los inventas? ¿Vas probando?

Aquí viene lo más bonito de todo y donde todo encaja con el anterior capítulo de esta entrada. Como hemos supuesto que las distintas variables aleatorias son independientes cualquier combinación lineal de ellas, por el Teorema del Límite Central, tenderá a tener una distribución de probabilidad más gaussiana que cualquiera de las originales.

Por ello, se puede ver como evoluciona la kurtosis de y en función de los valores de bi  y quedarnos con aquellos que maximicen la no-gaussianidad de y. De este modo se consigue obtener, si no las observaciones s1, s2, s3 y s4, la solución que garantiza la mayor independencia entre los resultados de salida.

¿Y en realidad cuantos micrófonos necesitas?

El número de micrófonos debe ser igual o mayor que el número de fuentes de sonido (es decir, variables aleatorias) que se quieren discriminar, siendo tanto mejor esta discriminación cuantos más micrófonos se tengan. Sin embargo la dificultad de computación aumenta mucho con el número de micrófonos, ya que cuanto mayor sea este número mayor será la dimensión del espacio en donde evaluar la kurtosis. Por esto, hay que llegar a un compromiso entre calidad de extracción y capacidad de computación (lo que se traduce en recursos y tiempo).

 Para acabar (se oyen gritos de júbilo al final de la sala), decir que este procedimiento se llama Independent Component Analysis (ICA). Y es un procedimiento muy utilizado en señales biomédicas. Por ejemplo, en electrocardiogramas, donde se dispone de muchos parches (“micrófonos”) y queremos observar la evolución del corazón (“1º invitado honorífico”) pero se nos cuelan otro tipo de señales como la respiración de los pulmones (“2º invitado, éste se ha colado en la fiesta”), la señales miográficas de los músculos (“3º invitado, otro gorrón”), etc.

¡Un saludo y perdonad el chorrazo!

Nota: Hay gente que llama a este teorema Teorema Central del Límite. A mi me parecen las dos traducciones igual de correctas  pero me sale de manera más natural la primera. 🙂

Publicado en Uncategorized | Etiquetado , , , , , , , , | 1 comentario

Cuestión de escalas

Vía xkcd.

Publicado en Uncategorized | Etiquetado , , , , , | Deja un comentario

Codificando información: funciones generatrices (I)

Una de las flechas imprescindibles en el carcaj de un matemático, lista para atacar un problema, es sin duda la serie de Taylor, útil debido, oficialmente, al matemático inglés Brook Taylor. Recordamos que la serie de Taylor nos permite expresar una función regular f(x) como un polinomio, presumiblemente de infinitos términos, de coeficientes proporcionales a derivadas sucesivas de la función en un punto a. Es decir,

\displaystyle f(x) = f(a)+ f'(a)(x-a) + \frac{f''(a)}{2!}(x-a)^2 + \frac{f^{(3)}(a)}{3!}(x-a)^3+\cdots

Esto nos permite escribir funciones clásicas como el seno, el coseno o la exponencial en la forma,

\displaystyle \sin x = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + \cdots

\displaystyle \cos x = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^8}{8!} + \cdots

\displaystyle e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots

¡Con qué alegría pones puntos suspensivos…! 

Los puntos suspensivos indican lo que parece: una suma infinita,

\displaystyle e^x = \sum_{k=0}^\infty \frac{x^k}{k!}

Cuando las hay, nada bueno puede pasar. Afortunadamente, no es el caso de las funciones anteriores, ya que su desarrollo en serie converge al valor de f(x) para todo x\in\mathbb{R}

Pero en la mayoría de los casos, la convergencia de tales series se dará únicamente en un entorno del punto a sobre el que se desarrolla la función f(x).

Aún así estos desarrollos en serie son fantásticos, ya que nos dan aproximaciones arbitrariamente buenas de la función en cuestión y dependiendo del caso, con unos pocos términos de la serie.

Por ejemplo, para la función seno restringida al intervalo [-\pi,\pi] se tiene,

\displaystyle \left|\sin x - \left(x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\frac{x^9}{9!}\right)\right| < 0.01

Cometemos un error de, a lo sumo, una centésima utilizando la aproximación de Taylor del seno en lugar del propio seno

De hecho, la aproximación es de orden 9.

Un seno en el intervalo [-\pi-\epsilon,\pi+\epsilon] y su serie de Taylor hasta orden 9.

Pues bien, aunque parezca mentira, esta entrada no está dedicada a la serie de Taylor. No estamos interesados en si la serie aproxima mejor o peor a la función. Lo que realmente nos interesa son los coeficientes del polinomio de Taylor.

En los desarrollos para el seno, el coseno y la exponencial se observa que los coeficientes forman las sucesiones numéricas,

\displaystyle \left\{0,1,0,-\frac{1}{3!},0,\frac{1}{5!},0,-\frac{1}{7!},\ldots\right\}

\displaystyle \left\{1,0,-\frac{1}{2!},0,\frac{1}{4!},0,-\frac{1}{6!},\ldots\right\}

 \displaystyle \left\{1,1,\frac{1}{2!},\frac{1}{3!},\frac{1}{4!},\frac{1}{5!},\frac{1}{6!},\frac{1}{7!},\ldots\right\}

respectivamente. Como hemos visto, la obtención de cualquiera de los términos de la sucesión se recupera a partir de estas funciones calculando,

\displaystyle \frac{f^{(k)}(0)}{k!}

Podríamos decir entonces, que los polinomios de Taylor de una función codifican sucesiones de números. Pero, y lo contrario, ¿también es verdad? Quiero decir,

¿una sucesión de números cualquiera puede codificarse en una función?

Debemos distinguir dos casos: el caso finito y el caso infinito. En este caso, finito significa una sucesión de números la cual es cero a partir de cierto índice, es decir, la sucesión tiene un número finito de números distintos de cero.

Pongamos entonces que tenemos una sucesión de números finita, para fijar ideas, la siguiente,

\displaystyle \left\{1,2,3,4,0,-1\right\} \sim \left\{1,2,3,4,0,-1,0,0,0,\ldots\right\}

Esta sucesión de números puede codificarse en el siguiente polinomio,

\displaystyle f(x) = 1+2x+3x^2+4x^3-x^5

Como es de esperar, los coeficientes del polinomio de Taylor de una función que es un polinomio son los coeficientes del propio polinomio El caso finito no tiene más: codificamos la sucesión con un polinomio del grado que toque. El caso de una sucesión infinita tiene mas chicha. Al igual que antes, empezamos con un pequeño ejemplo: supongamos que queremos codificar en una función la sucesión,

\displaystyle \{1,1,1,1,1,\ldots\}

Esta función será,

\displaystyle f(x) = 1+x+x^2+x^3+x^4+\cdots = \sum_{k=0}^\infty x^k

Pero claro, esta expresión no es cerrada. No tiene sentido codificar una sucesión infinita de números, con una función expresada como una serie infinita. Para eso, nos quedamos con la sucesión.

Vamos a intentar expresar f(x) de una manera más simple, más compacta. Primero escribimos,

\displaystyle f(x)=1+ \sum_{k=1}^\infty x^k

Escrito de la forma anterior, vemos que podemos sacar factor común x en el sumatorio infinito, obteniendo,

\displaystyle f(x) = 1+x\sum_{k=1}^\infty x^{k-1} = 1 + x\sum_{k=0}^\infty x^k

La serie que acompaña a la x en la última igualdad…

¡es la propia función!

Haciendo esta observación podemos escribir lo siguiente,

\displaystyle f(x) = 1 + x f(x) \quad \Rightarrow \quad f(x) = \frac{1}{1-x}

Muchos conoceréis la última función. Exacto, es la conocida fórmula para la serie geométrica.

Se dice que 1/(1-x) es la función generatriz de la sucesión \{1\}_{k=0}^\infty.

Pero cuando la función es evaluada en, por ejemplo, x=2 se tiene…

Totalmente de acuerdo, se obtiene algo sin sentido,

\displaystyle \frac{1}{1-2} = -1 = 1+2+2^2 + 2^3 + 2^4 +\cdots = \infty

Esto se debe a que la convergencia de la serie de Taylor de la función al valor de la función solo se da para valores de x tales que |x|<1.

Aún así, como decíamos antes, solo estamos interesados en la obtención de una sucesión numérica a partir de una función, y para esto, no es necesaria la convergencia de la propia serie. Es decir, trabajamos con las igualdades en un sentido formal.

Veamos algún ejemplo más. Supongamos que queremos codificar la sucesión,

\displaystyle \left\{0,1,4,9,16,25,36,\ldots\right\}

Es decir, la sucesión de los cuadrados perfectos. La función que la genera será,

\displaystyle f(x) = \sum_{k=0}^\infty k^2 x^k = \sum_{k=1}^\infty k^2 x^k

Usamos un truco parecido al de antes. Sacamos factor común x y vemos que,

\displaystyle f(x)=x\sum_{k=1}^\infty k^2 x^{k-1}=x\sum_{k=1}^\infty k\cdot(k x^{k-1})

Esta claro. El cuerpo nos pide escribir,

\displaystyle k x^{k-1} = \frac{d (x^k)}{dx}

y después, por ejemplo, intercambiar el orden de la derivada y el sumatorio. En condiciones normales, habría que preocuparse por cuestiones de convergencia pero afortunadamente, operamos formalmente.

Por tanto f(x) puede expresarse como,

\displaystyle f(x)=x\sum_{k=1}^\infty k\frac{d (x^k)}{dx}=x\frac{d}{dx}\sum_{k=1}^\infty k x^k = x \frac{d}{dx}\left(x\frac{d}{dx}\sum_{k=1}^\infty x^k\right)

donde en la última igualdad hemos seguido el mismo proceso que en las líneas anteriores. Observamos que el último sumatorio, que aparece en la línea anterior, lo conocemos: es casi la función generatriz de la sucesión \{1\}_{k=0}^\infty,

\displaystyle \sum_{k=1}^\infty x^k=\frac{1}{1-x}-1=\frac{x}{1-x}

Un pequeño inciso…

Mini-teorema (Desplazamiento hacia la derecha)

Si A(x) es la función generatriz de la sucesión \{a_k\}_{k=0}^\infty, entonces x A(x) es la función generatriz de la sucesión \{0,a_0,a_1,a_2,\ldots\}. Es más, x^n A(x) genera la sucesión \{0_1,0_2,\ldots,0_n,a_0,a_1,a_2,\ldots\}.

Metiendo x/(1-x) en la expresión de f(x), y derivando, obtenemos,

\displaystyle f(x)=\frac{x(x+1)}{(1-x)^3}=\frac{1}{1-x}-\frac{3}{(1-x)^2}+\frac{2}{(1-x)^3}

Esta función tiene a los cuadrados perfectos por coeficientes de Taylor. He expresado f(x) como suma de fracciones simples para hacer la siguiente observación: sabemos que,

\displaystyle \frac{d}{dx}\left(\frac{1}{1-x} \right)= \frac{1}{(1-x)^2},\quad \frac{d^2}{dx^2}\left(\frac{1}{1-x}\right)=\frac{2}{(1-x)^3}

Un segundo inciso…

Mini-teorema (Derivada de una sucesión)

Si A(x) es la función generatriz de la sucesión \{a_k\}_{k=0}^\infty, entonces A'(x) es la función generatriz de la sucesión \{ka_k\}_{k=1}^\infty. Es más, A^{(n)}(x) genera la sucesión \{k(k-1)\cdots (k-(n-1))a_k\}_{k=n}^\infty.

Supongamos que no conocemos los coeficientes de Taylor de la función f(x) que acabamos de calcular. Ayudados del resultado recién enunciado vamos a calcularlos sabiendo únicamente que,

\displaystyle \frac{1}{1-x} \quad \longleftrightarrow \quad \{1\}_{k=0}^\infty

Por el teoremilla anterior sabemos que,

\displaystyle \frac{1}{(1-x)^2} \quad \longleftrightarrow \quad \left\{k\right\}_{k=1}^\infty=\left\{(k+1)\right\}_{k=0}^\infty

\displaystyle \frac{2}{(1-x)^3} \quad \longleftrightarrow \quad \left\{k(k-1)\right\}_{k=2}^\infty=\left\{(k+2)(k+1)\right\}_{k=0}^\infty

Con esto y la descomposición en fracciones simples de f(x) es fácil deducir que la sucesión generada por la función es,

\displaystyle \frac{x(x+1)}{(1-x)^3}\quad \longleftrightarrow\quad\{1\}_{k=0}^\infty-3\left\{(k+1)\right\}_{k=0}^\infty+\left\{(k+2)(k+1)\right\}_{k=0}^\infty

Operando término a término con las sucesiones anteriores se obtiene,

\displaystyle\left\{1-3(k+1)+(k+2)(k+1)\right\}_{k=0}^\infty=\left\{k^2\right\}_{k=0}^\infty

que es lo que esperábamos. Como vemos, no ha sido necesario liarse a derivar la función para sacar su coeficientes de Taylor, lo cual habría sido una opción tan válida como ésta.

De hecho, con un poco más de esfuerzo puede sacarse la función generatriz de la sucesión,

\displaystyle \{P_n (k)\}_{k=0}^\infty con P_n (k) un polinomio de grado n

Muy bien…ve cortando ya el tema, que esto no da más de sí…

¡Qué no da más de sí! Os recomiendo a los que penséis así, y a los que no por supuesto, que no os perdáis la próxima entrega…y para ir abriendo boca os recomiendo echarle un vistacillo a la sucesión de Fibonacci.

Publicado en Uncategorized | Etiquetado , , , , , | 4 comentarios

Sobre gaussianas, dinosaurios y fiestas de cocktail (I)

Esta mañana estaba haciendo limpieza de mi escritorio cuando me fijé en la vieja versión que tengo de Parque Jurásico, de Michael Crichton. No pude evitar cogerlo y hojear un poco sus páginas hasta que una figura me llamó la atención dentro del libro y pensé que sería una manera estupenda de presentarme en este blog.

Os pongo en situación. Tenemos a nuestros conocidos Dr. Grant (doctor en paleontología), Dra. Sattler (doctora en paleobotánica) e Ian Malcom (doctor en matemáticas) iniciando su visita por las instalaciones del Jurassic Park. John Hammond, magnate de la ingeniería genética y fundador del parque no deja de repetir que las instalaciones son seguras y que “no han reparado en gastos” en ello.

Para demostrarlo llevan al grupo de invitados a la sala de control y allí Ray Arnold, ingeniero de sistemas, tiene una discusión con Ian Malcolm sobre los sistemas de control de los habitantes del parque, concretamente sobre la población de procompsognátidos, los cuales fueron incluidos en el parque en tres tandas genéticas diferentes.

[…]

– En realidad, tengo una pregunta. – dijo Malcolm-. Nada más que una pregunta de investigación científica: usted nos mostró que puede hacer el seguimiento de los procompsognátidos y que puede mostrar, visualmente, a cada uno de ellos. ¿Puede hacer alguna clase de estudios sobre ellos, pero como grupo: medirlos, o lo que fuere? Si yo quisiera conocer su altura o su peso…

Arnold estaba apretando botones: otra pantalla se encendió:

Click en la imagen para agrandar

– Podemos hacer todo eso y, además, con mucha rapidez. […] Aquí puede usted apreciar que tenemos una distribución normal de Poisson  para la población animal: muestra que la mayoría de los animales se apiña alrededor de un valor promedio, y que unos pocos son o mas grandes o más pequeños que el promedio y se encuentran en los extremos descendentes de la curva.

– Cabría esperar esa clase de gráfico – comentó Malcolm.

– Si, cualquier población biológica saludable exhibe esa clase de distribución. Bien, […]¿hay más preguntas?

– No  – contestó Malcolm – Creo que con eso prácticamente se contestó todo. Ya me he enterado de lo que necesitaba saber.

Desde ese mismo momento Malcolm sabe que algo va mal. Aun no ha salido al parque y ya sabe que las cosas van muy mal y están fuera de control.

“¿Cómo? ¿Qué ha visto de raro en esa gráfica si todo era normal?”

Pues básicamente, eso, que la distribución es normal o lo que es lo mismo, que aun siendo una distribución de Poisson se aproxima mucho a una distribución gaussiana  y aquí es donde entra el tema del que quería hablaros hoy: el Teorema del límite central, uno de los teoremas más importantes de la teoría de la probabilidad:

Teorema del límite central: Sea X_1,X_2,\ldots,X_n un conjunto de variables aleatorias, independientes e idénticamente distribuidas de una distribución con media \mu y varianza \sigma^{2} \ne 0. Entonces, si n es suficientemente grande, la variable aleatoria

\displaystyle X^{*}=\frac{1}{n}\sum_{i=1}^{n}X_{i}

tiene aproximadamente una distribución normal con \mu_{X^{*}} = \mu y  \sigma^{2}_{X^{*}} = \sigma^{2}/n.

Pongamos un ejemplo para ilustrar este teorema. Imaginemos que tenemos un dado normal de seis caras (D6). Como somos gente honrada este dado es ideal y tiene una distribución de probabilidad uniforme, o dicho de otro modo, todas sus caras tienen la misma probabilidad de salir. ¿Qué probabilidad tengo de sacar un resultado dado si voy tirando varios de estos dados a la vez? En la imagen de abajo se pueden ver las distribuciones de probabilidad para los casos en que tiramos uno, dos, cuatro y ocho dados al mismo tiempo.

Como podéis apreciar, desde el momento en que tiramos más de cuatro dados la gaussianidad de la distribución empieza a ser apreciable y, cuantos más dados tiremos más se parecerá esa distribución a una gaussiana. Por ello, nuestro célebre matemático Ian Malcolm está tan preocupado desde el momento en que vio la distribución normal, pero dejemos que sea él quien se lo explique a Henry Wu, director y científico del departamento de ingeniería genética:

– ¿Nota algo en ese gráfico? – preguntó Malcolm [refiriéndose al primer gráfico de este post].

– Es una distribución de Poisson – Dijo Wu-. Curva normal.

– ¿No dijo usted que introdujo los compis en tres tandas?

– Si…

– Entonces, debió obtener un gráfico con picos en cada una de las tres tandas independientes que se introdujeron – manifestó Malcolm, al tiempo que pulsaba el teclado-: Como esto.

Click en la imagen para agrandar

Pero no obtuvo ese gráfico – objetó Malcolm-. El que realmente obtuvo se corresponde a una población que se reproduce.  Sus compis se están reproduciendo.

Efectivamente, la única manera que hay de que se pasara de una gráfica inicial con tres lóbulos a la gráfica normal es que el número de sujetos se fuera multiplicando, como sucedía con los dados, es decir que los compis estuvieran reproduciéndose de forma descontrolada. A mí me parece que la conclusión del señor Malcolm es bastante acertada. No voy a ahondar más en el libro y os dejo que seáis vosotros quienes lo leáis, porque realmente está mejor que la película que ya de por sí es una maravilla del cine.

“Bueno, ¿Y esto para qué sirve? ¿Tiene utilidad? ¿Y las fiestas de cocktail del título?”

Un poco de paciencia que eso lo dejo para otra entrada.

¡Saludos a todos!

Publicado en Uncategorized | Etiquetado , , , , , , , | 6 comentarios

Real como la vida misma

Genial as usual: Spiked Math Comics.

Publicado en Uncategorized | Etiquetado , , | Deja un comentario

No quiero cañones, prefiero a los delfines

por .

Publicado en Uncategorized | Etiquetado , , , , , | Deja un comentario

Sobre Cantor, Hausdorff y la que armaron (II)

En la entrada anterior vimos que el conjunto de Cantor era grande y pequeño a la vez. La forma tradicional de medir conjuntos no parece suficientemente precisa.

Pero… ¿cuál es esa forma tradicional?

Pensemos por un momento en que queremos calcular el área de un mesa, con ciertas irregularidades, o lo que es lo mismo, no es cuadrada. Para fijar ideas, una mesa triangular.

¿Cómo calcularíamos su área, sin recurrir a la conocida fórmula?

Una forma: cubriéndola de mesitas cuadradas y calculando el área de las mismas. Cuanto más pequeños sean esos cuadrados mejor nos aproximaremos a las esquinas de la mesa triangular y, en definitiva, mejor aproximaremos al área real de la mesa.

Este proceso es básicamente el que se representa en la imagen siguiente.

Lo que vengo a decir se resume con la siguiente frase:

Los cuadrados son reglas para medir objetos de dos dimensiones…

…al igual que las reglas de toda la vida, o segmentos de recta, nos permiten medir objetos unidimensionales y los cubos nos permiten medir volúmenes tridimensionales.

…¿y pueden usarse cuadrados, por ejemplo, para medir segmentos de recta?

¡Por supuesto! Pero claro, un segmento de recta siempre puede meterse en un rectángulo de área arbitrariamente pequeña…por tanto, medido con esa regla, un intervalo tiene medida cero. Lo mismo ocurre si intentamos medir el área del triángulo anterior mediante la regla tridimensional, los cubos.

Y al contrario claro. Si intentamos medir el área de una mesa cubriéndola con intervalos llegaremos a que la medida de la mesa es infinita.

Como decíamos en la primera entrada: todo depende de la regla utilizada.

¿Y si no estamos midiendo con la regla adecuada el conjunto de Cantor?

Pero esto es absurdo. O bien tiene una dimensión, o tiene dos, o tres…o sencillamente no tiene y es un conjunto discreto de puntos.

…¿y por qué no una regla entre una y dos dimensiones?

Ésta fue la idea que tuvo Felix Hausdorff, matemático alemán cuyas mayores contribuciones se engloban dentro de la topología.

Su idea fue, en esencia, la siguiente: al igual que antes, recubrimos nuestro conjunto a medir F \subset \mathbb{R}^n con conjuntos U_k, cuadrados o no, de manera que todos ellos tengan un diámetro  que no exceda un número fijo \delta>0. Esto es,

\displaystyle F \subset \bigcup_{k=1}^\infty U_k  con  \displaystyle |U_k| = \sup\{|x-y|\,:\,x,y\in U_k\}\leq \delta

El diámetro del conjunto nos da una idea de lo grande que es el conjunto, a lo largo de cualquiera de las dimensiones.

De entre todos los recubrimientos que nos podamos imaginar, nos quedamos con aquel para el que el número,

\displaystyle \sum_{k=1}^\infty |U_k|^s

sea mínimo. Este número lo denotaremos por \mathcal{H}^s_\delta(F).

Hasta aquí nada muy raro, ¿no?

Si lo pensamos un momento, es lo que hacemos normalmente: aproximar la medida del conjunto por la medida de los cuadraditos, la cual es su longitud elevado a la dimensión que toque…

Pero a nosotros, en la suma anterior, nadie nos obliga a poner un exponente s entero, ¿verdad? Pues bien, la propuesta de Hausdorff va precisamente en esa dirección, proponiendo como definición de dimensión,

\displaystyle \text{dim}_H F = \inf\{s\,:\, \mathcal{H}^s (F)=0\}

donde \mathcal{H}^s (F), denominada medida de Hausdorff, se define por,

\displaystyle\mathcal{H}^s(F)=\lim_{\delta\rightarrow 0}\mathcal{H}^s_\delta(F)

…¿calculamos la dimensión del conjunto de Cantor?

¡Claro! En la entrada anterior vimos que para calcular la medida tradicional del conjunto de Cantor calculábamos su longitud en cada fase de su contrucción. Esto es, 2^n intervalos de longitud 3^{-n} en la fase n.

Veamos como varía \mathcal{H}^s(\mathcal{C}) con s,

\displaystyle \mathcal{H}^s(\mathcal{C}) = \lim_{k\rightarrow\infty} 2^k\left|\frac{1}{3^k}\right|^s = \begin{cases} \infty,\quad s< \log 2/\log 3\\ 1,\,\,\,\quad s=\log 2/\log 3\\ 0,\,\,\,\quad s> \log 2/\log 3\end{cases}

Sí, es lo que parece. La dimensión de Hausdorff del conjunto de Cantor es

\displaystyle \frac{\log 2}{\log 3} = 0,630929...

Podríamos decir entonces que el conjunto de Cantor, y similares, se mide con cubos de dimensión 0,630929. 

Puede que a muchos de vosotros os resulte un resultado tonto, poco impresionante o inútil. Bueno, pues para quitar ese mal sabor de boca al lector interesado y desengañado, unos cuantos datos:

La costa de Reino Unido tiene dimensión de Hausdorff,

1,25

Es decir, no es una curva y , ‘costa’ y ‘Reino Unido’ no son términos matemáticos. Todo depende de la regla con que midamos por supuesto: eso incluye recorrer la costa en coche y ver que recorremos unos 15000 kilómetros.

El objeto fractal que nos comentaba un amigo, Sergio Hernández, en la entrada anterior: la esponja de Menger. Ésta tiene dimensión,

\displaystyle \frac{\log 20}{\log 3}\approx  2,7268

Otro conocido por el público en general, el conjunto de Mandelbrot. Éste es especial, ya que su dimensión,

2

es compartida por su frontera. Podríamos poner el siguiente pésimo símil: pelas una naranja, te la comes y cuando vas a tirar los trozos de la piel que han sobrado, ¡te encuentras otra naranja!

En el vídeo vemos de manera cristalina una propiedad (mejor dicho: la propiedad) que caracteriza a los fractales, en particular del conjunto de Cantor: la autosimilaridad, lo que significa que a diferentes escalas el objeto presenta siempre el mismo patrón.

Terminamos donde empezamos: el cerebro humano. Su superficie tiene una dimensión de,

2,79

Cerebro humano

Para profundizar más en este tema, de infinitas ramificaciones, os recomiendo,

  1. Fractal Geometry: Mathematical Foundations and Applications de K. J. Falconer.
  2. The Fractal Geometry of Nature de Benoît B. Mandelbrot.

Clouds are not spheres, mountains are not cones, and lightening does not travel in a straight line…[Benoît B. Mandelbrot]

Publicado en Uncategorized | Etiquetado , , , , , , , | Deja un comentario

Sobre Cantor, Hausdorff y la que armaron (I)

Hay objetos raros en matemáticas. Objetos verdaderamente complejos. Pese a su complejidad, muchos de ellos tienen una construcción realmente simple.

Uno de estos objetos es el conjunto de Cantor. Dicho conjunto se construye a partir del intervalo [0,1] y en fases.

La que podríamos denominar fase cero es el propio intervalo,

\displaystyle \mathcal{C}^0=[0,1]

En la fase uno nos comemos el tercio central del intervalo, quedando el conjunto,

\displaystyle \mathcal{C}^1=[0,1/3]\cup [2/3,1]

Iterando el proceso una vez más llegamos a la fase dos, en la que hemos eliminado el tercio central de los subintervalos anteriores,

 \displaystyle \mathcal{C}^2=[0,1/9] \cup[2/9,1/3]\cup [2/3,7/9]\cup [8/9,1]

Comiendo y comiendo los tercios centrales de los subintervalos llegamos al conocido conjunto de Cantor \mathcal{C}, que puede escribirse como,

\displaystyle \mathcal{C}=\bigcap_{k=0}^\infty\mathcal{C}^k=\lim_{k\rightarrow\infty}\mathcal{C}^k

La última igualdad se tiene por la propiedad \mathcal{C}^k \supset \mathcal{C}^{k+1}.

Conjunto de Cantor \mathcal{C}^k para k=0,1,2,3.

Con este conjunto en la mano nos surgen al menos dos preguntas. Empezamos con la segunda.

¿Cuánto mide este conjunto? 

 Si nos fijamos con atención en la construcción de \mathcal{C}, vemos que en cada fase k sobreviven 2^k intervalos de longitud 3^{-k}. Por tanto la medida del conjunto de Cantor parece ser,

\displaystyle m\left(\mathcal{C}\right)=\lim_{k\rightarrow\infty}\left(\frac{2}{3}\right)^k=0

A priori, un conjunto pequeño.

¿A qué se parece este conjunto?

Con parecer nos referimos en el sentido de la numerabilidad. En particular, queremos saber si \mathcal{C} es numerable, en cuyo caso existiría una correspondencia biyectiva con el conjunto de los números naturales \mathbb{N}, o por el contrario no numerable. El conjunto de los números reales \mathbb{R} es un caso de estos últimos.

Pues bien, el conjunto de Cantor \mathcal{C} es no numerable. Es decir, este conjunto tiene más números que números naturales hay, que enteros, que racionales, que pares naturales ordenados \mathbb{N}\times \mathbb{N}, …y que cualquier otro conjunto numerable imaginable (todos ellos equivalentes al de los naturales).

Podemos decir más.

Todo número real, y en particular todo número en el intervalo [0,1], puede representarse en otras bases, a parte de la decimal. Por ejemplo, en base 3.

En esta base, todo número x\in [0,1] puede expresarse mediante una sucesión de números a_i, dados por la expresión,

\displaystyle x=\sum_{k=1}^\infty \frac{a_k}{3^k} = (0,a_1a_2a_3\ldots)_3   con   a_k=0,1,2.

Calcular estos a_k es sencillo: dividimos el intervalo [0,1] en tres. Si x cae en el primer segmento a_1=0, si cae en el segundo a_1=1 y si cae en el tercero a_1=2. Posteriormente volvemos a dividir cada segmento en tres y elegimos a_2 siguiendo el mismo criterio que antes para cada segmento…

Procediendo de esta manera hasta que nos cansemos obtenemos el número x en base 3.

Notamos que a_k=1 solo cuando x cae en algún tercio central, cosa que no ocurre en el conjunto de Cantor, porque siempre nos comemos el tercio central.

Este pequeño comentario demuestra que todo elemento x\in\mathcal{C} es de la forma,

\displaystyle x=(0,a_1a_2a_3\ldots)_3   con   a_k=0,2.

Esto puede traducirse como,

Los números del conjunto de Cantor son básicamente sucesiones de ceros y unos

Y también una sucesión cualquiera de ceros y unos es básicamente un número del conjunto de Cantor.

Pero entonces…si tengo cualquier número binario, ¡tengo cualquier número!

Exacto. Veamos los siguientes ejemplos para convencernos de ello.

Pongamos que tenemos en base 3 el número x=(0,02202)_3, el cual pertenece al conjunto de Cantor. Éste es básicamente el número binario y=(0,01101)_2. Ahora traducimos este número,

\displaystyle y=(0,01101)_2=\frac{0}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\frac{0}{2^4}+\frac{1}{2^5}=0,40625

Ahora al revés. Supongamos que tenemos el número,

x=0.\overline{1304347826086956521739}

Este número en binario pasa a ser, y=(0.\overline{00100001011})_2, que se corresponde con el elemento del conjunto de Cantor,

(0.\overline{00200002022})_3

Para el carro…¿el conjunto de Cantor tiene al menos tantos números como hay en el intervalo unidad…y mide cero?

Si. Mide cero, con la regla que hemos usado para medir el conjunto.

Por último, una pequeña nota: la correspondencia entre la expresión en 0’s y 2’s y los números binarios no es uno a uno.

Pongamos que tengo el número del conjunto de Cantor (0,020\overline{2})_3. Sustituímos doses por unos y obtenemos (0,010\overline{1})_2=(0,011)_2. Si tomamos este número y vamos hacia atrás obtenemos (0,022)_3\neq (0,020\overline{2})_3.

Por tanto, esta aplicación que va del conjunto de Cantor \mathcal{C} en el intervalo [0,1] no es biyectiva, pero sí sobreyectiva.

Publicado en Uncategorized | Etiquetado , , , , , , , , , , , | 3 comentarios