Calcula la media aritmética

Parece una pregunta muy sencilla: ¿Puedes escribir un programa que calcule la media aritmética de una lista de números? La respuesta también puede ser sencilla, simplemente iterando sobre la lista y sumando los números para al final dividirlos por la cuenta. Por ejemplo, en Java:

La respuesta, aunque sencilla, no es del todo correcta. Imagínate, por ejemplo, que tu función recibe una lista vacía, o incluso sin inicializar. Tu código fallaría espectacularmente. Cuando escribes una función, por simple que sea (me atrevería a decir especialmente si es una función muy simple, pues será más probable que la reutilicemos en otras partes del código), nunca confíes en los parámetros de entrada de la función. Una versión algo más robusta sería:

Pero aún no es del todo correcta. ¿Puedes adivinar por qué? En este caso, el problema es mucho más sutil. Imagínate que la lista es muy larga; no, mejor aún, muy muy muy larga. ¿Qué pasaría con la variable sum? ¡Un desbordamiento de enteros! Una manera muy sencilla de solucionar el este problema es cambiando el tipo de la variable a double:

¿Me creerías si te digo que la función aún se puede mejorar más? Si tienes un conocimiento decente de estructuras de datos, sabrás que es muy probable que List.size() es algo que merece la pena copiar en memoria o, aún mejor, evitarlo completamente usando un foreach:

A partir de aquí, aunque se pueden seguir mejorando más elementos de la función, dichas mejoras empiezan a ser debatibles y dependientes de detalles relacionados con la implementación (por ejemplo, dividiendo el resultado de la suma incrementalmente en lugar de sólo al final).

La lección que espero transmitir con esta entrada es que incluso "algoritmos" relativamente sencillos como la media aritmética pueden dar mucho juego cuando uno se para a pensar en las diferentes optimizaciones aplicables.

Los piratas sedientos [acertijo]

Mientras el señor Morcillo le explicaba a su amigo el pescador cómo el reparto del tesoro iba a producirse, estaba tan absorto en su retórica que no se dio cuenta de que uno de los piratas le estaba observando atentamente. Sorprendentemente, el pirata que no le quitaba ojo entendía español perfectamente y, puesto que era el pirata de menor rango, no estaba muy contento con la perspectiva del reparto del tesoro. Intentando retrasar su inevitable ventura, le propuso a los otros piratas decidir qué hacer con los prisioneros antes de proceder al reparto del tesoro. En un inusual gesto de misericordia, convenció a los otros piratas para que, en vez de arrojar a los pescadores (y al señor Morcillo) por la borda, les proporcionasen un pequeño bote de remos y así pudieran volver a la costa para difundir los rumores y alimentar la leyenda acerca de los temibles y sanguinarios piratas. Tras mucho debatir, los piratas decidieron tomar un descanso hasta el día siguiente, pues anochecería pronto y estaban sedientos de ron.

Desgraciadamente para el señor Morcillo y sus amigos, la aparente clemencia del pirata era sólo una estratagema ideada para engañar al resto. Cuando todos dormían, se hizo con el saco que contenía las 100 monedas y tomó el pequeño bote de remos para quedarse con todo el tesoro, no sin antes raptar al señor Morcillo como parte de su botín, pues un prisionero que le ayudase a remar le sería de gran ayuda. Unas horas después de su exitosa escapada, ambos exhaustos y sedientos de tanto remar, al fin avistaron la costa en la lejanía. El pirata, que no había dicho ni una sola palabra hasta ese momento, rompió su silencio para decirle al señor Morcillo que sus "servicios" ya no serían necesarios. Ante tal situación, el señor Morcillo, que no quería morir ahogado o deshidratado tratando de nadar la considerable distancia que les separaba de la costa, recordó algo que muy probablemente le salvó la vida en ese instante. Dada su experiencia explorando tierras distantes de agua potable, él siempre llevaba consigo no una sino dos cantimploras llenas de agua, y una tercera vacía por si las moscas. ¡Podría ofrecerle agua al pirata a cambio de mantener su vida! Si le diese todo el agua al pirata, posiblemente moriría de sed antes de alcanzar la costa, pero si le ofreciese la mitad entonces el pirata no lo vería suficiente, así que tendría que idear una manera de repartir el agua disponible entre los dos...

Puesto que el objetivo era quedarse con la mayor cantidad de agua posible, ideó el siguiente juego que le daría al pirata un suficiente grado de control que hiciese improbable su descontento con el reparto de agua:

1. El señor Morcillo llenaría la botella vacía con un porcentaje determinado de agua de la primera botella llena, que podría ser cualquier número entre 0% y 100% (ambos incluidos).
2. El pirata elegiría entre la primera botella y la que el señor Morcillo acababa de rellenar para bebérsela, y el señor Morcillo se bebería la que el pirata no había escogido.
3. Una vez ambos hayan bebido su ración de agua, el señor Morcillo llenaría una de las botellas vacías con un porcentaje determinado de la segunda botella, todavía llena de agua.
4. Si el pirata había elegido el porcentaje mayor en el primer reparto, entonces se quedaría con el porcentaje menor en el segundo. Por ejemplo, si el señor Morcillo divide la primera botella en 20 / 80 y el pirata elige quedarse con el 80%, evidentemente el señor Morcillo dividirá la segunda en 0 / 100 porque al pirata le corresponde la menor parte de la segunda botella.

Si ambas botellas contienen exactamente la misma cantidad de agua, y suponiendo que el señor Morcillo es capaz de rellenar las botellas vacías con el porcentaje exacto que desee, ¿cómo debería hacer el reparto para quedarse con la mayor cantidad de agua posible?

Los piratas lógicos: solución

Ésta es la solución al acertijo descrito en esta entrada. Si no lo has intentado solucionar por tu cuenta, te recomiendo que lo hagas antes de comenzar a leer el siguiente párrafo.

¿Cómo podía el señor Morcillo saber el reparto final de las monedas? La primera clave para solucionar el acertijo, es saber identificar que estamos ante un problema de teoría de juegos para 5 jugadores. La estrategia a seguir se basa en los mismos principios que otros juegos como el ajedrez o el póker, en los que cada jugador intenta minimizar su máxima perdida. Aunque sería perfectamente válido invertir el objetivo para que cada jugador maximice sus ganancias, me parece más fácil plantearlo como un problema minimax. De ahora en adelante, me referiré al pirata de mayor rango como P1 (pirata 1), P2 para el segundo, etc. De modo que P5 es el pirata de menor rango. Intuitivamente, mucha gente piensa que P5 se quedará con todas las monedas porque, desde el punto de vista de cualquiera de los piratas de menor rango, siempre será mejor que haya menos piratas para repartirse las monedas entre menos. Sin embargo, leyendo el procedimiento descrito en el acertijo, nos daremos cuenta de un detalle fundamental:

1. El pirata de mayor rango haría una proposición para el reparto de las monedas, y entonces todos los piratas votarían a favor o en contra del reparto (incluido el pirata que hace la proposición).
2. Si la votación resulta en una mayoría (50% o más de los votos) aceptando el reparto, se reparten las monedas y se acabó la historia.
3. Si el número de piratas que aceptan el reparto es menos de la mitad, el pirata que propuso el reparto será arrojado por la borda y el siguiente pirata hará una nueva proposición hasta que se acepte el reparto (vuelta al paso 1) o no queden más piratas.

Las letras en negrita indican que no es necesario tener más del 50% de los votos, porque con la mitad exacta ya sería suficiente para que el reparto fuera aprobado. Teniendo eso en cuenta, cuando queden 2 piratas, P4 y P5, el de mayor rango, es decir, P4, puede con su propio voto conseguir la mayoría. Evidentemente, siendo un pirata sanguinario y avaricioso, P4 propondría el siguiente reparto:

Pirata	Reparto
P4	100 monedas
P5	0 monedas

P4, por supuesto, se votaría a si mismo y P5 votaría en contra. Como P4 tiene la mitad o más de los votos, el reparto es aprobado y P5 se queda con nada. Sorprendentemente, añadir otro jugador no cambia mucho la lógica. Si quedan los piratas P3, P4 y P5, P3 tiene que proponer un reparto que le de al menos uno de los votos de P4 y P5. El pirata P5 sabe que, si P3 se va al agua, P4 se queda con todo y él con nada. Este juego, como el ajedrez y al contrario que el póker, es un juego de informacion perfecta, porque todos los piratas tienen la misma información y pueden deducir no solo su estrategia óptima, sino también la de los demás piratas. Entonces P3 sabe que, si él pierde la votación y acaba en el agua, P5 se quedaría con nada (el reparto sería el descrito anteriormente). Como el peor caso para P5 es quedarse con nada, por poco que le ofrezca P3 ya estaría minimizando su máxima perdida y debería aceptar el reparto sea lo injusto que sea. Sabiendo eso, P3 propondría el siguiente reparto:

Pirata	Reparto
P3	99 monedas
P4	0 monedas
P5	1 moneda

Entonces podemos estar seguros de que, si P3 decide hacer la anterior proposición, nunca se dará el caso en el que queden 2 piratas porque P5 aceptara el reparto. ¿Pero que pasa si añadimos otro jugador mas? P2, al igual que P3 en la anterior situación, solo necesitaría un voto para, junto con el suyo, obtener la mayoría. Sin embargo, el peor caso (la máxima perdida) de cada uno de los piratas ha cambiado. P4 sabe que, si P2 no gana la votación, se quedará sin ninguna moneda. Por tanto, si P2 le ofrece tan solo una moneda, debería aceptar puesto que es una mejora respecto a su máxima perdida posible. Para P5, cuyo mejor caso es quedarse con una sola moneda, también debería aceptar si se le ofrece un reparto igual a su mejor caso (esa afirmación es debatible pero, desde un punto de vista lógico  ¿para qué iba a arriesgarse si le ofrecen un reparto igual a su máxima ganancia posible?). Por lo tanto, los posibles repartos a hacer serían:

Pirata	Reparto 1	Reparto 2
P2	99 monedas	99 monedas
P3	0 monedas	0 monedas
P4	1 monedas	0 monedas
P5	0 moneda	1 moneda

A partir de este punto, añadir un quinto jugador es trivial si aplicamos la misma lógica. P1 sólo tiene que igualar el mejor casi posible (o mejorar el peor caso si este es cero monedas) para otros 2 piratas y, así, obtendrá la mayoría de los votos evitando ser arrojado por la borda:

Pirata	Reparto 1	Reparto 2	Reparto 3
P1	98 monedas	98 monedas	98 monedas
P2	0 monedas	0 monedas	0 monedas
P3	1 monedas	1 monedas	0 monedas
P4	1 monedas	0 monedas	1 monedas
P5	0 moneda	1 moneda	1 monedas

La pregunta interesante ahora podría ser, ¿qué pasa si extrapolamos esto a un problema con N piratas?

Los piratas lógicos

El señor Morcillo pronto se dio cuenta de que eso de vivir en Guinea Ecuatorial no era tan buena idea como le pareció al principio. Hacía demasiado calor y, además, el español que hablaba allí la gente le resultó más bien extraño. Por suerte para el señor Morcillo, visitando el mercado local encontró a un grupo de pescadores con rumbo a la península ibérica, ¡podría volver a casa con ellos! Y sólo le pedían a cambio 100 monedas. Una vez entregado el dinero, se embarcó en el pequeño bote con destino a España. Desgraciadamente, la suerte no estuvo de su lado por mucho tiempo y, apenas unas horas después de comenzar el viaje, fueron abordados por piratas. Puesto que la tripulación estaba compuesta por un pequeño grupo de humildes pescadores no había mucho que los temibles piratas pudieran saquear pero, cuando encontraron la pequeña bolsa de tela que contenía las monedas, la situación cambió drásticamente.

Uno de los piratas que abordaron el pequeño bote de los pescadores

Aunque el señor Morcillo se esperaba que los piratas fueran irracionalmente salvajes, puesto que él y sus amigos pescadores fueron hechos prisioneros y maniatados, estos le demostraron ser capaces de un gran uso de la razón. Él era incapaz de entender lo que los piratas decían pero uno de los pescadores le iba traduciendo mientras ellos decidían qué hacer con las monedas. Al parecer, los 5 piratas habían decidido repartirse el tesoro de una manera muy peculiar, el procedimiento era:

1. El pirata de mayor rango haría una proposición para el reparto de las monedas, y entonces todos los piratas votarían a favor o en contra del reparto (incluido el pirata que hace la proposición).
2. Si la votación resulta en una mayoría (50% o más de los votos) aceptando el reparto, se reparten las monedas y se acabó la historia.
3. Si el número de piratas que aceptan el reparto es menos de la mitad, el pirata que propuso el reparto será arrojado por la borda y el siguiente pirata hará una nueva proposición hasta que se acepte el reparto (vuelta al paso 1) o no queden más piratas.

Evidentemente, todas las monedas eran del mismo valor y no se podían romper ni dividir en partes. Los piratas podrían hablar entre ellos pero, puesto que son piratas, no podrían confiar los unos en los otros. Además, no había 2 piratas que fueran del mismo rango, es decir, cada pirata tenía un rango distinto al de todos los demás.

Como eran 5 los piratas, su amigo el traductor rápidamente le dijo al señor Morcillo que, evidentemente, varios iban a ser arrojados por la borda y, tal vez, serían capaces de luchar contra el resto de sus captores puesto que les superarían en número. Sin embargo, el señor Morcillo no estaba tan seguro de ello. De hecho, el señor Morcillo sabía que, si los piratas hacían un buen uso de la lógica, sólo había 3 maneras posibles de repartirse las monedas (dando por supuesto que ninguno de los piratas quería ser arrojado por la borda y que todos querían maximizar el número de monedas en su propiedad). Si tenéis curiosidad por saber cómo el señor Morcillo fue capaz de adivinar el reparto, puedes verlo aquí, ¡pero os recomiendo que intentéis sacarlo por vuestra cuenta!

Inverosímil

Después del desastre causado al enviar un trozo de hojalata a Marte, nuestro hipotético protagonista el señor Morcillo (me parece más adecuado que hablar en segunda persona), decidió retirarse a una vida de paz y tranquilidad, lejos de la civilización, ¿y qué mejor sitio que Guinea Ecuatorial? Bueno, en realidad hay otros muchos sitios, pero el señor Morcillo no anda muy puesto en idiomas, ni tampoco en historia contemporánea porque de haber sabido que en Guinea Ecuatorial hay una de las dictaduras más opresoras del mundo, nunca habría ido allí.  Aunque algo bajito, muy moreno no es pero, entre reformas laborales y otras mamandurrias varias, tan quemado estaba que pasaba desapercibido entre la población pigmea local. No le sería fácil adaptarse a sus costumbres, pero después de unas pocas decenas de años seguro que se sentiría como en casa.

He aquí un mapa, para los despistados. Licencia CC Wikimedia Commons

Tan lejos de la civilización y, por consiguiente, cualquier forma de entretenimiento moderno, el señor Morcillo tenía que hacer algo para mantener su mente ocupada, que eso de estar en territorio salvaje parece muy interesante en supervivientes pero en realidad aburre bastante. Después de muchas horas intentando ejercitar poderes paranormales sobre la fauna local de cabras, que aparentemente sólo funciona si eres George Clooney, desarrolló cierta curiosidad sobre la verdadera altura de los pigmeos. ¿Cuál será la estatura del pigmeo medio?
Por desgracia, medir a todos y cada uno de los pigmeos no era una solución viable. Una de las maneras más comunes de resolver este tipo de problemas es tomando una muestra representativa de la población. Una vez tenemos un número de sujetos más manejable, podremos estimar la media y extrapolar ese número al total de la población. Si lo que estás pensando es que con tomar la media aritmética de la muestra ya obtendríamos la solución a nuestro problema, estás equivocado y te recomiendo que sigas leyendo.

El señor Morcillo, posando con parte de la muestra de la población. Licencia CC Wikimedia Commons

¿Por qué la media de la muestra no es suficiente? Porque con la media estamos asumiendo que la distribución de la estatura es completamente uniforme y, además, descartamos parámetros importantes a tener en cuenta como la varianza o el tipo de distribución. Para una distribución normal, una simple media aritmética acaba resultando en una aproximación bastante decente y en muchos casos puede ser suficiente, pero no es la manera más correcta. ¿Y si tuviéramos un método que, además de ser más correcto, funcionase con otro tipo de distribuciones conocidas? Pues lo tenemos, y se llama estimación por máxima verosimilitud.

Cualquiera que tenga una mínima idea de estadística sabrá que la distribución de la estatura, además de ser un tipiquísimo ejemplo, suele ser aproximadamente una distribución normal o gaussiana; en otras palabras, la campana de toda la vida. Una vez conocida la distribución correspondiente a nuestra muestra, simplemente estimamos el verdadero valor de la media mediante la estimación por máxima verosimilitud. Para hacer tal estimación, básicamente estaremos aplicando ingeniería inversa sobre la función de densidad correspondiente a la distribución que creamos sea la más aproximada a la distribución real. Las matemáticas detrás de estos conceptos son más feas que una nevera por detrás, así que me voy a limitar a describir los pasos a seguir conceptualmente:

1. Encontrar la función de densidad conjunta de todas las estimaciones. Que en cristiano es lo mismo que coger la función de densidad que hayamos elegido, y meter los valores que hayamos medido (multiplicando cada función, porque las probabilidades conjuntas siempre se multiplican).
2. Como el verdadero valor de la media es desconocido, el resultado del paso anterior debería estar en función de tal valor como variable. Entonces sólo queda maximizar la ecuación resultante para, dadas nuestras mediciones, encontrar el verdadero valor de la media con el que es más probable que nuestras mediciones sean las correspondientes a la distribución elegida.

Visualización realista de los pasos a seguir para la estimación de máxima verosimilitud. Licencia CC Wikimedia Commons

¡Y ya está! El método que conceptualmente es tan poco complejo es un pilar fundamental para la aplicación práctica de nuestros conocimientos sobre estadística usando mediciones reales. Uno de los ejemplos prácticos más importantes son los modelos lineares que, los conozcas o no, nos afectan a tí, a mí y al señor Morcillo todos los días en cosas como los precios en el súper, la tarifa de la luz, el pronóstico del tiempo... Y otra infinidad de ejemplos que me sería imposible de enumerar.

El problema de Diffie-Hellman

Se puede escribir mucho sobre el protocolo de cifrado de Diffie-Hellman, incluyendo interesantes historias sobre cómo realmente no fue el primer protocolo de cifrado asimétrico, al contrario de lo que muchos piensan. Esta entrada va a ser un poco densa para los que no estén medianamente puestos en el tema, y no va sobre criptografía. Espero poder hablar del protocolo de cifrado de Diffie-Hellman al completo más adelante, pero esta vez me gustaría centrarme en un pequeño detalle que he visto en la versión inglesa de la Wikipedia sobre la descripción del problema propuesto por Diffie-Hellman, cuya versión en español no existe, por cierto. Si vais a la descripción del problema, podréis leer lo siguiente:

Given an element g and the values of gx and gy, what is the value of gxy?

Formally, g is a generator of some group (typically the multiplicative group of a finite field or an elliptic curve group) and x and y are randomly chosen integers.

Lo que viene a ser en la lengua de Cervantes algo así como:

Dado un elemento g y los valores de gx y gy, ¿cuál es el valor de gxy?

Formalmente, g es un generador de algún grupo (típicamente el grupo multiplicativo de un cuerpo finito o un grupo correspondiente a una curva elíptica) y x e y son números enteros elegidos al azar.

palangifiles.com Creative Commons.

No sé a vosotros, pero ese segundo párrafo me parece la típica afirmación que se prueba por intimidación. Voy a intentar arrojar algo de luz sobre el asunto así que, ya que los cobardes se habrán marchado hace unas cuantas líneas, puedo decir que esta entrada es sobre teoría de grupos y álgebra abstracta. Corred insensatos.

Lo primero y más básico, un grupo no es nada más que un conjunto de números ligados a una operación. Por ejemplo, los números pares y la suma forman un grupo. Cada grupo tiene ciertas características; todos los grupos son cerrados, pero un grupo puede ser finito o infinito, cíclico o no cíclico, conmutativo o no… Por ahora solo voy a centrarme en esas tres primeras características.

Volviendo al ejemplo de los números pares, son claramente un grupo cerrado, porque no importa con qué números del grupo hagamos la operación (recordemos que nuestro grupo está formado por los números pares y la suma, todo grupo tiene una operación definida), el resultado siempre va a formar parte del grupo. En términos más simples, siempre que sumes dos números pares el resultado va a ser otro número par. Resulta que también es un grupo infinito, porque hay un número infinito de elementos que pertenecen al grupo. Cuando creas que tienes una lista con todos los números pares, añade 2 al ultimo y ya tienes otro numero par... ad infinitum. Hasta ahora nada complicado, pero el concepto de grupo cíclico tal vez sea algo más complejo para los que no hayan visto antes álgebra abstracta.

Retículo de particiones del conjunto {1,2,3,4}. Wikimedia Commons

En un partido de fútbol, un equipo podría marcar cualquier número de goles, porque los goles se marcan de uno en uno. En álgebra estaríamos hablando del conjunto de números naturales asociados a la suma. Si eliges un número positivo, no importa cuál, en teoría ése podría ser el número de goles marcados por un equipo. En baloncesto, suponiendo que no existieran ni tiros libres ni triples, cada canasta vale dos puntos. En ese caso, ningún equipo bajo ninguna circunstancia podría tener un resultado impar porque, como decíamos antes, siempre que sumes dos números pares (en este caso 2 es siempre uno de esos números), el resultado será otro número par. En el ejemplo del fútbol, cualquier número natural puede ser generado si sumamos 1+1+1… Suficientes veces, por eso, ese determinado grupo es un grupo cíclico y tiene el numero 1 como generador. En el segundo ejemplo, dado un número impar, no podría generar ese número no importa cuántas veces realice la operación 2+2+2+2… Por lo tanto, 2 no es un generador para el conjunto de números naturales bajo la suma. Sin embargo, si consideramos el conjunto de números pares, ¡2 sí es un generador! Dame cualquier número par, que si sumo 2+2+2+2… suficientes veces, llegaré a ese resultado. Como tiene un generador, ese grupo es un grupo cíclico.Entonces pues, ambos grupos son cíclicos. El primero tiene 1 como generador y el segundo tiene el número 2 como generador.

Las raíces complejas bajo multiplicación son un ejemplo de grupo cíclico. Wikimedia Commons

¿Y a qué viene todo este rollo sobre teoría de grupos para entender el protocolo de cifrado de Diffie-Hellman? Pues volvamos a la primera línea de nuestra definición del problema:

Dado un elemento g y los valores de gx y gy, ¿cual es el valor de gxy?

Ahora en vez de la suma nuestra operación es la multiplicación. Observemos dos posibles casos: g puede ser un generador o no. Si g no es un generador, no importa cuántas veces realice la operación g × g × g × g… va a haber algún numero perteneciente al mismo grupo que nunca podría ser parte del resultado. Si suficientes números son excluidos del resultado, ¡estaremos comprometiendo la seguridad de nuestra clave! Imagina que g fuese 2. En ese caso, mi clave privada y la clave compartida sólo podrán ser una potencia de 2. Con un poquito más de información, como la longitud de la clave, intentar adivinarla sería un juego de niños. Y por eso es importante que g sea un generador para su grupo, o que al menos su clase residual (el conjunto de elementos que g podría generar) sea suficientemente grande. Así, cuando tenemos un numero en común, g, y tú realizas la operación g × g × g × g… y veces, o sea,  gy , y me mandas el resultado; y yo hago la operación gy × gy × gy × gy… x veces, lo que viene a ser simplemente gxy, un atacante tendrá muchas claves que probar hasta que dé con el mismo resultado que yo obtuve con esa operación. Con un poco de suerte, serán demasiadas claves para que acierte a tiempo, entonces mi clave será segura.