log log binning

Una de las materias que hice el año pasado (estrictamente hablando, aún la estoy haciendo) fue Topología de Internet, con Nacho Alvarez-Hamelin. En ella estudié a Internet como sistema complejo, donde routers y/o ASs se interconectan y forman un grafo.

Una de las propiedades más características de los grafos es su distribución de grados. El grado es la cantidad de vértices que tiene un nodo. En el ejemplo de la izquierda, el nodo 4 tiene grado 3. La distribución de grados es una característica del grafo en su conjunto y no es otra cosa que contar cuántos nodos hay con grado 0, cuántos con grado 1, y así siguiendo. En el caso de la topología de Internet, no hay nodos con grado 0, ya que es una red totalmente conexa (triste sería estar conectado a ese router que no está conectado a nada más).

La topología de Internet (es decir, cómo se interconectan sus componentes) no se conoce a ciencia cierta (tema que quedará para otro post) pero hay algunos acercamientos académicamente aceptados. Uno de ellos es el de CAIDA que provee información sobre como están conectados los distintos sistemas autónomos. Esta data, después de modificar un poco su formato, puede ser analizada con el módulo Complex Systems Toolbox, para Scilab, un clon libre de Matlab.
Resulta ser que, al analizar la distribución de grados de la topología de Internet, uno se encuentra con una distribución de ley potencial (chocolate por la noticias, dirían los hermanos Faloutsos, que ya sabían esto desde 1999).

Esta ley de potencia (en inglés, power law) es una relación en que la frecuencia de un hecho cae de forma exponencial con respecto a la magnitud. Este tipo de distribuciones tiene una forma de panza hacia el eje de coordenadas y abunda en la naturaleza™, desde el crecimiento de los ríos hasta la popularidad de las personas en las redes sociales. Por su forma tan particular, se suele dibujar en ejes logarítmicos, quedando como una recta que se caracteriza por su pendiente (en el dibujo, b), que es el exponente de la curva en ejes lineales.

En estos dibujos, la curva es continua y elegante. Pero cuando uno va al mundo discreto de la modelización de fenómenos, la cosa cambia. Y mucho. Por ejemplo, este es el gráfico de la distribución de grados de la topología de AS, según CAIDA:

Los puntos rojos son las muestras discretas, las uní solo para que se aprecie mejor cuál va delante de cada cuál. Como se ve, la cosa no queda tan prolijita y agradable. Es que hay veces que la naturaleza™ se resiste a ser modelada con una fórmula y la estimación de al pendiente cuando se trata de datos experimentales puede ser complicada, sobre todo en la cola. Así es como llegamos al concepto de binning.

La idea es sencilla. Consiste en dividir el eje x es zócalos (bins) de tamaño fijo. Después tomar todas las muestras que caigan en un bin y promediarlas. Así, se grafica solo este promedio como un único punto que representa a todo el bin. Como estamos trabajando con ejes logarítmicos, el calculo del ancho de los bins requiere cierta aritmética, dado que estos se van ampliando exponencialmente (de forma tal que queden todos del mismo tamaño, o casi, al plotearlos). A esto lo llamamos log log binning.

Por suerte, el Complex Systems Toolbox tiene una función para hacer esta magia. Y aquí está el resultado:

Las muestras son las cruces rojas, mientras que los puntos verdes son los representantes de binning. Puede verse que están casi equidistantes, sobre todo después de 10. Por otro lado ¿no notan nada raro acá? Vamos por partes. En la parte inicial de la curva, ésta aparece por debajo de la línea de las cruces rojas. Esto empieza a tener poco sentido. Se supone que el promedio de un único punto es ese mismo punto.

Más grave aún es lo que ocurre en la cola. Ahí, esporádicos puntos (hay muchos ceros) generan una recta paralela al eje. Cuando uno promedia varios valores el resultado debería ser cada vez menor si la cantidad de ceros aumenta. Sin embargo, aquí la curva se suaviza hasta perder toda su inclinación.

Fue así como decidí mejorar esta funcion de log log binning (si, toda esta introducción para contarles esto... es que evidentemente soy muy pedante). A continuación, el mismo gráfico, resultado de mi propia implementación:

Algunas reimplementaciones por acá, fixeo de bugs por allá y ahora la pendiente se puede ver mucho más clara. Obvio que también podías leerte el paper de los hermanos Faloutsos, donde se explica que b está entre 2.1 y 2.4, pero no hubiese sido igual de divertido. Tuve que leer bastante y entender aritmética que había olvidado. Putié mucho contra scilab/matlab pero terminé descubriéndole cosas interesantes. En general, fue algo bastante entretenido.

La nueva implementación de log log binning ya está en el trunk de Complex Systems Toolbox y seguramente estará disponible en la próxima versión. También incluí novedades para graficar distribución de grados cuando los grafos son dirigidos y algunas otras pequeñeses de formato.

La ley de Benford y la vida real (tm)

Lo prometido. Hoy me gustaría hablarles algo que no tenía idea que existía y que me encontré en el apéndice 9 del libro La Proporción Áurea de Mario Livio. Es de esos sorprendentes conceptos que destruyen la intuición. Por un lado es simple desde lo formal, pero esconde algo casi mágico. Dicho concepto es: La ley de Benford

Para los que no hicieron click en el link anterior y dado que la entrada en la Wikipedia en español sobre el tema deja bastante que desear (estoy corrigiéndola), acá está mi breve explicación:

La ley de Benford, también conocida como la ley del primer dígito, dice que, en los números que existen en la vida realTM, la primer cifra tiene muchas más posibilidades de ser 1 que otro valor. Además, según crece este primer dígito, más improbable es que se encuentre en la primera posición.

A por un ejemplo, que seguro es más fácil. Tomemos una tabla con estadísticas cualquiera, como ser el área o población de las provincias argentinas, la capacidad de los estadios del mundo, los muertos por accidentes de tránsito o las estadísticas de visitas en tu blog. Como todo en estadística, mientras más grande la muestra mejor, así que vayan a por tablas realmente grandes.

Intuitivamente, uno podría pensar que, para cualquier número, las posibilidades que empiece con 1 son las mismas que con 9. Es decir, al agarrar una pelota de números cualquiera de la vida realTM se podría llegar a creer que, si la cantidad es lo suficientemente grande, más o menos 1/9 de la muestra empezarán con 1 (nótese que no tiene sentido que los valores empiezen en 0, por lo que las opciones son 9). Esto es porque creemos que los números que estamos analizando se comportan como si fuesen aleatorios. Si tiramos una moneda al aire una gran cantidad de veces, cerca de la mitad de las oportunidades será seca. Es algo que aprendimos hace mucho y nos parece intutivo que la naturaleza se comporte así. Como si $deity hubiese tirado un dado gigante para decidir el largo de un río, la población de un país o el precio de las acciones en el MERVAL.

Como en mi disco todavía tengo los datos utlizados para el post la chica bajo la curva (dating pool) voy a utilizar la cantidad de casados, por provincia, por edad (puede descargarse desde acá). En mi caso son 30843 regitros. Esta linea de bash cuenta cuantos de los valores empienzan con cada cifra:

$ for i in $(cat provincia_indec.csv | grep años | cut -d ';' -f 4); do echo ${i:0:1}; done | sort | uniq -c
10350 1
5581 2
3550 3
2744 4
2159 5
1903 6
1815 7
1406 8
1335 9

Puede verse que el 33.56% de las cifras empiezan con 1 y que, mientras mayor es el valor del primer dígito, menor es la cantidad de ocurrencias.

En efecto, nuestro nuevo amigo Benford describe este fenómeno y nos dice que, la probabilidad p de que el dígito d aparezca en el primer lugar está dado por la siguiente fórmula:

En el ejemplo anterior, el dígito 1 se encuentra en 10350/30843=0.336 de los casos. Puede verse que la predicción de la fórmula es bastante buena, ya que log10(1+1)=0.301. En la siguiente figura puede verse como se ajusta la fórmula a los datos de la práctica (primer dígito de la cantidad de personas casadas por provincia, por edad según el censo 2001):

De hecho, la misma fórmula puede aplicarse a más de un dígito. Por ejemplo, la probabilidad de que una cifra empiece con 42 (primer dígito 4, segundo 2) es log10(1+1/42)=0.010219. Modificando levemente el script (${i:0:2}) podemos estudiar la cantidad de cifras por la repetición de sus primeros dos números y compararlos con su valor teórico:

Impresionante.. no?

¿Y porqué pasa esto? Ocurre que a las magnitudes del mundo realTM están distribuidas de forma logarítmica.

Recordemos la fórmula: p(d)=log10(1+1/d)=log10(d + 1) − log10(d)
Es decir, cuenta cuántos números hay entre d y d+1 dentro de la escala logarítmica.

La mejor explicación que recibí para este fenómeno habla de un cambio de escala. Supongamos por un momento que la distribución de los primeros dígitos de lo largo de los ríos, lo alto de las montañas, lo profundo de los posos es constante. Ahora imaginemos que $deity se levanta una mañana y duplica el tamaño del planeta (o del universo, ustedes elijen). Las medidas que empezaban por 1 hora pasan a empezar por 2 o 3 (160*2=320). Lo que empezaba por 2 ahora lo hace por 4 o por 5 (290*2=580). El 3 se va a 6 o 7 (384*2=768). El 4 a 8 y 9.

¡Pero todos aquellas medidas que empezaban por 5, 6, 7, 8 y 9 ahora empiezan por 1! Si realizamos esta operación varias veces los valores se amontonan rápidamente en los iniciados por 1, generando la escala logarítmica en cuestión. Y acá está el tema. La mayoría de los valores de la vida realTM son resultados de multiplicaciones.

El siguiente gráfico invita a comparar las superficies rojas (valores que inician con 1) y azules (valores que inician con 8) para estudiar sus probabilidades de ocurrencia en el primer dígito:

Las distribuciones que cubren muchos órdenes de magnitud (que varían mucho entre número y número) cumplen relativamente bien con la ley de Benford. Sin embargo puede no ocurrir así siempre:

Nótese que la clave está en las grandes magnitudes (recuerden la explicación del universo que se duplica). Existen tablas de números de la vida realTM que no cumplen la ley dada que estan acotadas en cuento a su rango, por ejemplo los datos del cierre del MERVAL de los últimos 3 años. Si bien son números grandes, su máximo y mínimo es acotado. Imagino (no tengo uno a mano) que los precios unitarios de los productos en un ticket de supermercado tampoco se agustan a la ley por razones parecidas. La tabla de goleadores de un torneo de fútbol padece el mismo trauma. ¿Se les ocurre algún otro ejemplo excepcional a la regla?

Espero hayan aprendido algo nuevo y ahora quieran a la matemática un poquito más :)

PD: Me olvidaba. Tarea para el hogar: Demostrar que la vida realTM incluye a Fibonacci ;)

la chica bajo la curva (dating pool)

Hace poco más de un año, como muchos de ustedes seguramente, leí esta simpática tira de XKCD. En ese momento empecé a buscar datos sobre la población para ver que tan real era ello. La pseudo-investigación se fue de cause y terminé en cualquier parte hasta que lentamente perdí el rumbo sin la más mínima intención de retomarlo.

Un par de semanas atrás, y por razones que no viene al caso, volví al tema desde cero. En este caso llegué a cosas medianamente concretas (dentro del delirio, claro). Así que aquí están algunos de los resultados que me gustaría compartir con ustedes.

Introducción:

Para aquellos que no tienen idea de los que estoy hablando, una breve introducción. En la famosa tira cómica se plantea una sencilla hipótesis que puede resumirse en la siguiente pregunta: "¿a partir de qué edad tus posibilidades de tener pareja empiezan a bajar?"

Para esto tengamos en cuenta dos elementos:

  • A mayor edad, menores las posibilidades de soltería. Es decir, si una persona tiene 20 años es más probable de que esté soltera a que ocurra lo mismo con alguien de 40 años.
  • A mayor edad, mayor es el rango de edad de los candidatos. Para poner un ejemplo, no es lo mismo que una persona de 40 salga con otra de 55 que un joven de 18 salga con alguien de 33. Es claro no hay edades para el amor, pero estamos hablando de posibles candidatos. Incluso hablamos de las posibilidades de tener cosas en común, de fijarse en el otro. Randall Munroe, el autor de la tira, propone una fórmula a la que llama "standard creepiness rule" (algo así como "regla estándar de viejo-verdez", asquerosidad, o algo del estilo). Según él (y muchos parecen coincidir), las personas no salen con alguien que tenga la mitad de su edad más siete. Por ejemplo, en mi caso y con 27 años, mi cota inferior está dada por (27/2)+7=20.5, lo que parece bastante razonable o, al menos, políticamente correcto. Esta misma fórmula también sirve como cota superior, ya que uno es el límite inferior de alguien mayor. Para mi edad corresponde a 40 años porque 40=(27-7)*2. Nótese que para una persona de 20 años sus candidatos van entre 17 y 26, mientras que para alguien de 30 sus opciones van entre 22 y 46. Se supone que hay más personas entre el segundo rango que el primero, al menos hasta que la taza de mortalidad empieza a hacer de las suyas.

Primera aproximación:

Lo interesante de esta situación es la posibilidad de analizarla con datos reales. Son datos que existen, que se preguntan en los censos, pero que no siempre están disponibles para cualquier mortal. Por suerte el INDEC (Instituto Nacional de Estadística y Censos) provee la información de una forma que, aunque críptica para el recién llegado, resulta interesante cuando uno le encuentra la vuelta. Así que fue allí a donde fui, a buscar el universo de la población argentina.

Tomando toda la población mayor a 14 años, por edades simples y situación conyugal, calculé la cantidad de personas candidatas para cada edad, tiendo en cuenta los rangos de edades de esos posibles candidatos. Consideremos candidatos a las personas no casadas (solteros, divorciados, separados legales y viudos). Aquí el gráfico:

Nótese la forma de W-invertida de la gráfica. El máximo absoluto se encuentra a los 27 años. Es decir, en este momento me encuentro en el cenit de la soltería. Es interesante observar, que después del punto de inflexión de los 41, a los 47 vuelve a haber un máximo. Llamemos a este punto El club de la divorciadas ;). Las estadísticas demuestran que la frase "la vida da revancha" tiene fundamento estadístico.

Pero los valor absolutos siempre me parecieron lejanos. Soy de los que disfruta hablar en términos de porcentaje, de probabilidades, es decir, en términos relativos. Así fue como generé este segundo gráfico, con la intención de responder a la pregunta "Si conozco a 100 personas dentro de mi rango de edad, ¿cuántas estarán no-casadas?":

Así, la cantidad de personas sin compromisos maritales dentro de un rango, sobre la cantidad total de personas de ese rango da un porcentaje de disponibilidad para cada edad. Acá la cosa se pone algo más pesimista, asegurando una clara caída hasta los 44 años, edad desde la cual se inicia un tímido y poco constante ascenso.

Segunda aproximación:

Esta visión es más egocentrista y está pensada en términos totalmente propios. En lo personal, estoy interesado por personas de género femenino, que no solo no estén casadas, sino que además no convivan en pareja (las considero personas en relaciones lo suficientemente fuertes como para quitarlas del conjunto de candidatas). A estas limitaciones le sumaré la restricción geográfica de que tenga residencia dentro de mi ciudad natal y alrededores, por lo que solo tendré en cuenta personas dentro de Buenos Aires y conurbano bonaerence. La ubicación geográfica puede acarrear cambios culturales que tengan efectos en la situación conyugal de las personas, por lo que considero importante tenerlo en cuenta.

Felizmente INDEC tiene una forma rápida de filtrar por estas restricciones, así que seleccioné las regiones geográficas y construí un filtro donde solo se refiera a personas de sexo femenino que no estén conviviendo con una pareja.

Nuevamente, las mismas gráficas:


Esta vez la W-invertida refleja un máximo absoluto muy diferente al inicial, 53 años. Tal vez se parezca más al modelo que, creo que intuitivamente, proponía Munroe. En el gráfico de porcentajes, la caída es mucho más brusca y profunda, perdiendo más de una decena de puntos en su mínimo, que además se da bastante antes, a los 38 años. La pendiente de ascenso es empinada y termina por provocar mayores valores hacia el final de la esperanza de vida que la aproximación anterior.

Suposiciones y limitaciones:

Estos análisis son un emporio de suposiciones y limitaciones. Después de todo, dicen que la estadística es la ciencia del prejuicio. Acá una lista de suposiciones que pueden ser ampliamente discutibles:

  • Los homosexuales y religiosos existen en cantidades despreciables. Así que todo hombre soltero busca una mujer y viceversa.
  • Las personas con alguna relación de pareja no convivientes son consideradas disponibles. El INDEC no pregunta acerca de estado amoroso de las personas.
  • La cantidad de personas con n y medio edad es la mitad de la cantidad de personas con n edad.
  • La fórmula "standard creepiness rule" es válida. Aunque posiblemente pueda repetirse la experiencia con fómulas que mejor se ajusten a cada cultura. En lo personal, creo tener poco en común con alguien de 40 años. De hecho, formulas independientes para el hombre y la mujer creo que serían más aplicables. Tal vez los hombres tiene un target más orientado a la izquierda del eje. Pero es medio que gusto de cada uno.
  • La información del censo corresponde a datos de 2001. Extrapolarlos no tiene sentido, ya que insertaría muchísimo error. Lo dicho, lo interesante son los números en proporciones.
  • La definición de "candidato" esta dada por edad, género, posición geográfica y estado conyugal. No se contempló gustos y esas cosas de esas que hace que las parejas funcionen... o eso dicen :P.

Todo lo necesario para repetir la experiencia se encuentra acá. Enjoy it ... que yo voy a estar buscando a esa chica bajo la curva :)

fútbol y matemática, unidos por cumpleaños en común

No, no me refiero a que el fútbol y la matemática cumplan años el mismo día. Vamos por partes.

Antes que nada, una aclaración: aquellos que me conocen saben que a mí el fútbol, como cultura, me es tosco. No se por qué, tal vez algún prejuicio o trauma de la infancia, así que me siento bastante tonto hablando del tema. La razón por la que el siguiente experimento tiene al fútbol de protagonista está justificada en la página 149 del libro Matemática... estas ahí? de Adrián Paenza (que puede bajarse aquí para uso personal).

En la página a la que me refiero el autor explica, con no mucho detalle, la mal llamada Paradoja del Cumpleaños. Para quien no suele hacer clicks sobre los links, una definición fugaz sobre qué es: por más increíble que parezca, en un grupo de 23 personas existe el 50,73% de probabilidad de que dos personas cumplan años el mismo día del año.

En el mismo libro, Paenza propone:

Y si quieren poner esto a prueba, la próxima vez que participen de un partido de fútbol (once jugadores por equipo, un árbitro y dos jueces de línea), hagan el intento. Tienen más de 50% de posibilidades de que con las 25 personas haya dos que cumplan años el mismo día. Como esto es claramente antiintuitivo para muchos de los que participen del partido, quizás ustedes puedan ganar alguna apuesta.

Como últimamente juego poco al fútbol, decidí hacer la experiencia con los partidos del último torneo (Apertura ‘07) de la Liga Argentina. La idea es sencilla: tomar cada partido, averiguar qué jugadores fueron titulares, quién fue el árbitro y sus correspondiente fechas de nacimiento y ver si la teoría coincide con la práctica. Excluí de la experiencia a los jueces de línea, ya que conseguir sus datos era muy complicado y, después de todo, alcanza con 23 para que la esperanza matemática esté de nuestro lado (además, estrictamente hablando, no están dentro de la cancha :P).

Después de algunos scripts para parsear el fixture y un poco de trabajo manual me hice de una lista de partidos, con los jugadores y árbitros. La parte más complicada fue obtener las fechas de nacimiento. Estos últimos datos salieron de fuentes dispersas y no se que tan confiables, por lo que si algún lector friki encuentra algún error agradezco me lo haga saber.

Luego, con un poco de mi mediocre Python, escribí algunas lineas para ver en cuantas canchas del torneo coexistieron personas que pueden juntarse a festejar sus cumpleaños.

Los datos, los resultados y las conclusiones fueron:

  • En el torneo hubo 189 partidos. Son 20 equipos que jugaron todos contra todos, a excepción de Gimnasia vs Arsenal.

  • Participaron 484 personas, entre jugadores y árbitros.
  • Los nombres de pila más populares, en orden, son Juan, Pablo, Diego y Cristian.
  • Las colisiones se dieron siempre de a pares. Es decir, no hubo 3 o más personas en el mismo partido que cumplan años el mismo día.
  • En 11 partidos hubo dos pares de colisiones. Esto es curioso, porque se trata del 5,82% de los casos, cuando las probabilidades de que ocurran dos colisiones es del 22,5%.
  • En 4 partidos hubo tres pares de colisiones. Esto también es curioso, porque se trata del 2,11% de los casos, cuando las probabilidades de que ocurran tres colisiones es del 8,52%. Una de estas colisiones fue el superclásico River vs Boca.
  • La gran conclusión: hubo colisiones de cumpleaños en 94 partidos, lo que representa 49,74% del total de partidos.

El detalle de los resultados puede verse acá.

Querido pragmático experimentófilo, no se trata de otra tragedia de la ciencia. Afortunadamente, la matemática es la única ciencia donde la teoría siempre coincide con la práctica. Pero en el juego de las probabilidades, y si bajo la influencia de Paenza, hubiésemos apostado a todos los partidos del último campeonato, tal vez habríamos perdido algo de plata. Faltó un solo partido más con colisión para que la ganancia esté de nuestro lado... será el próximo campeonato.

El porcentaje 49,74% coincide casi a la perfección con la teoría. Es simpáticamente cercano (a 0,99 puntos) al número predicho, y es mucho más alto de lo que un simple mortal intuitivista podría haber arriesgado a primera vista :-).

Todos los archivos están codificados en utf-8. Las fechas están en formato día/mes/año