El problema de Trebisonda
Hay un estupendo divulgador y matemático, llamado John Allen Paulos, que entre otras cosas se dedica a escribir una columna en la que analiza matemáticamente eventos de actualidad. Su columna es tal vez el mejor argumento en contra de los que piensan que la matemática no tiene aplicaciones en la vida cotidiana. Uno de los ejemplos más célebres que Paulos trató fue la polémica, hace cuatro años, del recuento de Florida. Paulos demostró que el resultado de la votación estaba dentro del margen de error de las máquinas contadoras. En otras palabras, para todo efecto el resultado era un empate, conceptualmente idéntico a que la diferencia de votos entre Bush y Gore hubiese sido cero patatero: lanzar una moneda al aire hubiese sido un método igualmente válido para determinar el Presidente de los EEUU. Deprimente, pero cierto.
Otra de las grandes contribuciones de Paulos, a mi juicio, es demostrar lo torpe que es el mecanismo de análisis probabilístico intuitivo que todos poseemos. Es ese mecanismo el que hace que la gente, por norma general, le tenga más miedo a subirse en un avión que a meterse en un coche, siendo que su probabilidad de morir objetiva es mucho mayor en el segundo caso que en el primero.
Este tipo de análisis nos revela que no tenemos cultura matemática, y eso es lo que Paulos se empeña en mostrarnos. El último ejemplo en nuestro país es un obispo que confunde tasas de fallo de preservativos con probabilidad de contraer el SIDA, como si la prevalencia de esta enfermedad fuese del 100% en la población sexualmente activa y la infección segura en todos los casos. Es deplorable, pero más triste aún es que nadie le corrija con los argumentos adecuados, los matemáticos.
En ese sentido, hace unos meses se desató una polémica en el foro de Actualidad Nacional de Terra sobre cuál sería la probabilidad de lo que ocurrió con el tema de los cadáveres mal identificados del Yak-42, es decir, la probabilidad de identificar mal treinta cuerpos de treinta, si dejamos esa identificación al puro azar, como parece más que probable que ocurrió en Trebisonda. No quiero frivolizar con el tema. Por el contrario, me parece fundamental hacer este cálculo para entender si las explicaciones dadas hasta ahora --y las que tendremos sin duda como parte de la investigación judicial-- tienen sentido. Y sin embargo, cuando uno se enfrenta a algo tan triste como el accidente del Yak-42, estoy seguro de que habrá personas para las que someter lo sucedido a un frío análisis matemático les sonará a frivolidad y falta de respeto por las víctimas.
Yo pienso que, por el contrario, alguien debería hacer este análisis. No es sorprendente, dado lo que digo arriba sobre la falta de cultura matemática que adolecemos, que nadie lo haya hecho. Pero la juez tendría que pedirlo, algún diario deberia haberlo investigado. Y la razón es que si el número que obtenemos es, digamos, 0,10, podemos pensar que los identificadores son algo gafes, pero que la posiblidad de que se hayan equivocado al azar es factible. En cambio, si el número es uno entre un millón, tendríamos que empezar a preguntarnos seriamente qué sucedió en Trebisonda, pues el simple azar no podría explicarlo.
Como nadie ha hecho este análisis, y dado que en mi despedida del foro de Terra un forista se permitió dudar de que estuviera dentro de mis capacidades hacerlo (nada me acicatea más que un aguijonazo en pleno orgullo), pasé el día de ayer analizando el problema, y quisiera ahora publicar los resultados de mi análisis.
Con esto también quiero que esta bitácora se abra a otras temáticas. En la descripción de la misma he dicho que me gustaría hablar de cultura. Pues es lo que me dispongo a hacer, porque la matemática --la ciencia, en general-- es cultura, por mucho que este concepto le cueste entenderlo a la gran mayoría de los humanistas.
En todo caso, hagamos historia. Ya había yo adelantado una respuesta cuando el tema surgió por primera vez, pero Carlos me hizo ver que era errónea. En efecto, yo había supuesto sin pensarlo demasiado que cada identificación individual era un evento independiente, lo cual es claramente falso. Si un cuerpo es identificado de forma incorrecta, es evidente que ese hecho produce automáticamente una segunda identificación falsa. Además de la mia se adelantaron varias soluciones, pero la que más la que menos todas tenían algún problema, y la mayoría de las veces el problema era esa suposición falsa de independencia.
Al reconocer mi error, dije que el problema probablemente debía abordarse estudiando las permutaciones. Es lo que haré ahora.
Identificar los cuerpos es equivalente a ordenar una lista. Hay un solo orden totalmente correcto. Vamos a abstraer el problema. Vamos a suponer, sin pérdida de generalidad --pues una numeración arbitraria siempre se puede hacer corresponder biunívocamente con cualquier otra numeración arbitraria-- que el orden totalmente correcto es el siguiente:
1 2 3 4 5 6 7 .... 28 29 30
En esta lista, cualquier cambio supondrá dos o más errores (ya hemos visto que un solo error es imposible). Ahora bien, esos "cambios" no son otra cosa que permutaciones. Por ejemplo, la lista:
3 2 1 4 5 6 7 ... 29 28 30
es una permutación de la lista original que contiene dos cambios, el 1 con el 3 y el 29 con el 28. Llamemos ciclos a esos cambios, y representémoslos de la siguiente forma:
[1 3]
quiere decir que el 1 se ha cambiado al 3 y el 3 al 1.
Claramente, puede haber cambios más complejos. La lista
1 2 3 4 5 6 7 8 9
y su permutación
3 8 4 7 2 9 1 5 6
se relacionan a través de los siguientes cambios:
El 1 al 3 a su vez al 4 a su vez al 7 a su vez al 1
El 2 al 8 a su vez al 5 a su vez al 2
El 6 al 9 a su vez al 6
El concepto de ciclo va quedando claro: en todos los casos anteriores hay una serie de cambios que terminan volviendo al primer elemento, m0, cerrando el ciclo. Es evidente que el ciclo siempre se cierra. Los números con los que contamos son finitos, por lo que tienen que repetirse tarde o temprano. Y como un número dado mk sólo puede tener un predecesor, es imposible que mk sea predecesor de ningún otro elemento que ya esté en la lista, salvo m0.
Un poco de notación:
El primer ciclo de arriba lo representaremos como
[1,3,4,7]
El segundo como
[2, 8, 5]
y el tercero, como ya habíamos quedado, como
[6, 9]
Todo esto en el entendido de que [1,3,4,7] es idéntico a [3,4,7,1], a [4,7,1,3], etcétera.
No es difícil demostrar que toda permutación puede expresarse como un conjunto de ciclos y viceversa.
Ahora bien, fijémonos en un caso particular. Un ciclo con un solo elemento, al que llamaré evidente y algo traviesamente "monociclo", representa un elemento que no cambia de sitio. En nuestro ejemplo, es una identificación correcta.
Por ello, nuestro problema se reduce a contar las permutaciones que no contengan monociclos. Éstos serán los casos favorables. Divididos entre los casos posibles, nos dará nuestra probabilidad.
Continuaré con esto más tarde, pues no lo he terminado. Me he decidido a publicar porque no quería dejar la bitácora abandonada por dos días, sobre todo al principio de su funcionamiento. Pero en todo caso, el que quiera continuar con la respuesta al problema por su cuenta haría bien, me parece, en consultar los llamados números de Stirling de segundo tipo, que cuentan el número de formas en que se pueden dividir N objetos en k ciclos. Si a este número se le restan los monociclos, ya tenemos nuestro problema terminado. La alternativa de la fuerza bruta, por supuesto, siempre es posible.
Un saludo a todos, y muchísimas gracias a los que han dejado un comentario. En particular Mindingui, que se ha prodigado y a quien leeré luego con más calma.
Otra de las grandes contribuciones de Paulos, a mi juicio, es demostrar lo torpe que es el mecanismo de análisis probabilístico intuitivo que todos poseemos. Es ese mecanismo el que hace que la gente, por norma general, le tenga más miedo a subirse en un avión que a meterse en un coche, siendo que su probabilidad de morir objetiva es mucho mayor en el segundo caso que en el primero.
Este tipo de análisis nos revela que no tenemos cultura matemática, y eso es lo que Paulos se empeña en mostrarnos. El último ejemplo en nuestro país es un obispo que confunde tasas de fallo de preservativos con probabilidad de contraer el SIDA, como si la prevalencia de esta enfermedad fuese del 100% en la población sexualmente activa y la infección segura en todos los casos. Es deplorable, pero más triste aún es que nadie le corrija con los argumentos adecuados, los matemáticos.
En ese sentido, hace unos meses se desató una polémica en el foro de Actualidad Nacional de Terra sobre cuál sería la probabilidad de lo que ocurrió con el tema de los cadáveres mal identificados del Yak-42, es decir, la probabilidad de identificar mal treinta cuerpos de treinta, si dejamos esa identificación al puro azar, como parece más que probable que ocurrió en Trebisonda. No quiero frivolizar con el tema. Por el contrario, me parece fundamental hacer este cálculo para entender si las explicaciones dadas hasta ahora --y las que tendremos sin duda como parte de la investigación judicial-- tienen sentido. Y sin embargo, cuando uno se enfrenta a algo tan triste como el accidente del Yak-42, estoy seguro de que habrá personas para las que someter lo sucedido a un frío análisis matemático les sonará a frivolidad y falta de respeto por las víctimas.
Yo pienso que, por el contrario, alguien debería hacer este análisis. No es sorprendente, dado lo que digo arriba sobre la falta de cultura matemática que adolecemos, que nadie lo haya hecho. Pero la juez tendría que pedirlo, algún diario deberia haberlo investigado. Y la razón es que si el número que obtenemos es, digamos, 0,10, podemos pensar que los identificadores son algo gafes, pero que la posiblidad de que se hayan equivocado al azar es factible. En cambio, si el número es uno entre un millón, tendríamos que empezar a preguntarnos seriamente qué sucedió en Trebisonda, pues el simple azar no podría explicarlo.
Como nadie ha hecho este análisis, y dado que en mi despedida del foro de Terra un forista se permitió dudar de que estuviera dentro de mis capacidades hacerlo (nada me acicatea más que un aguijonazo en pleno orgullo), pasé el día de ayer analizando el problema, y quisiera ahora publicar los resultados de mi análisis.
Con esto también quiero que esta bitácora se abra a otras temáticas. En la descripción de la misma he dicho que me gustaría hablar de cultura. Pues es lo que me dispongo a hacer, porque la matemática --la ciencia, en general-- es cultura, por mucho que este concepto le cueste entenderlo a la gran mayoría de los humanistas.
En todo caso, hagamos historia. Ya había yo adelantado una respuesta cuando el tema surgió por primera vez, pero Carlos me hizo ver que era errónea. En efecto, yo había supuesto sin pensarlo demasiado que cada identificación individual era un evento independiente, lo cual es claramente falso. Si un cuerpo es identificado de forma incorrecta, es evidente que ese hecho produce automáticamente una segunda identificación falsa. Además de la mia se adelantaron varias soluciones, pero la que más la que menos todas tenían algún problema, y la mayoría de las veces el problema era esa suposición falsa de independencia.
Al reconocer mi error, dije que el problema probablemente debía abordarse estudiando las permutaciones. Es lo que haré ahora.
Identificar los cuerpos es equivalente a ordenar una lista. Hay un solo orden totalmente correcto. Vamos a abstraer el problema. Vamos a suponer, sin pérdida de generalidad --pues una numeración arbitraria siempre se puede hacer corresponder biunívocamente con cualquier otra numeración arbitraria-- que el orden totalmente correcto es el siguiente:
1 2 3 4 5 6 7 .... 28 29 30
En esta lista, cualquier cambio supondrá dos o más errores (ya hemos visto que un solo error es imposible). Ahora bien, esos "cambios" no son otra cosa que permutaciones. Por ejemplo, la lista:
3 2 1 4 5 6 7 ... 29 28 30
es una permutación de la lista original que contiene dos cambios, el 1 con el 3 y el 29 con el 28. Llamemos ciclos a esos cambios, y representémoslos de la siguiente forma:
[1 3]
quiere decir que el 1 se ha cambiado al 3 y el 3 al 1.
Claramente, puede haber cambios más complejos. La lista
1 2 3 4 5 6 7 8 9
y su permutación
3 8 4 7 2 9 1 5 6
se relacionan a través de los siguientes cambios:
El 1 al 3 a su vez al 4 a su vez al 7 a su vez al 1
El 2 al 8 a su vez al 5 a su vez al 2
El 6 al 9 a su vez al 6
El concepto de ciclo va quedando claro: en todos los casos anteriores hay una serie de cambios que terminan volviendo al primer elemento, m0, cerrando el ciclo. Es evidente que el ciclo siempre se cierra. Los números con los que contamos son finitos, por lo que tienen que repetirse tarde o temprano. Y como un número dado mk sólo puede tener un predecesor, es imposible que mk sea predecesor de ningún otro elemento que ya esté en la lista, salvo m0.
Un poco de notación:
El primer ciclo de arriba lo representaremos como
[1,3,4,7]
El segundo como
[2, 8, 5]
y el tercero, como ya habíamos quedado, como
[6, 9]
Todo esto en el entendido de que [1,3,4,7] es idéntico a [3,4,7,1], a [4,7,1,3], etcétera.
No es difícil demostrar que toda permutación puede expresarse como un conjunto de ciclos y viceversa.
Ahora bien, fijémonos en un caso particular. Un ciclo con un solo elemento, al que llamaré evidente y algo traviesamente "monociclo", representa un elemento que no cambia de sitio. En nuestro ejemplo, es una identificación correcta.
Por ello, nuestro problema se reduce a contar las permutaciones que no contengan monociclos. Éstos serán los casos favorables. Divididos entre los casos posibles, nos dará nuestra probabilidad.
Continuaré con esto más tarde, pues no lo he terminado. Me he decidido a publicar porque no quería dejar la bitácora abandonada por dos días, sobre todo al principio de su funcionamiento. Pero en todo caso, el que quiera continuar con la respuesta al problema por su cuenta haría bien, me parece, en consultar los llamados números de Stirling de segundo tipo, que cuentan el número de formas en que se pueden dividir N objetos en k ciclos. Si a este número se le restan los monociclos, ya tenemos nuestro problema terminado. La alternativa de la fuerza bruta, por supuesto, siempre es posible.
Un saludo a todos, y muchísimas gracias a los que han dejado un comentario. En particular Mindingui, que se ha prodigado y a quien leeré luego con más calma.
posted by Luis Fernando Areán | 3:33 p. m.
10 Comments:
No es trivial el problema. Y no tiene solución sencilla, al menos no la veo. Efectivamente, el problema debe abordarse mediante permutaciones (pero no solo). El número de casos posibles sería 30!, que es un número de 32 cifras. La forma de cálculo que veo sería sumar las probabilidades (casos) de acertar al azar los 30 (ésta es fácil, 1 entre 30!), acertar 29 (esta es imposible, sería 0), acertar 28 (ésta hay que calcularla), etc, hasta llegar a la probabilidad de 1 único acierto. La diferencia con 30! serían los casos con ningún acierto y el cociente entre ambas cifras, la probabilidad de no tener ningún acierto haciendo las identificaciones al azar. Para cada caso hay que hacer combinaciones de 30 tomados de 28 en 28, 27 en 27, etc. y cada caso multiplicarlo por las permutaciones sin acierto (explicar todo esto en texto es casi imposible, yo me veo incapaz).
Se puede plantear una hoja de excel e ir aumentando n (número de identificaciones). Sin llegar a n=30, se ve que la serie converge rápidamente y a partir de n=7, la probabilidad (con dos decimales) es constante. Concretamente, esta probabilidad (recordemos, de no acertar ninguna identificación, haciéndolas al azar) sería de un 36,79%. Es decir, si todo lo que nos han contado es cierto, hay una apreciable probabilidad de que las identificaciones se hicieran al azar.
Sobre lo de las elecciones en Florida, decirle que trata el tema con superficialidad. O se dan más datos o es mejor no extraer conclusiones (lo del empate). Desconozco el estudio que cita, pero puedo imaginar que basándose en los datos del fabricante de las máquinas de recuento y el número de votos del Estado, el autor plantea que la diferencia de votos entre ambos candidatos es inferior al "margen de error". Esto, dicho así, científicamente está falto de información. Es imprescindible, para sacar conclusiones, citar el "margen de confianza" con el que plantea el cálculo. Así, supongamos que siendo dicho margen del 99%, la diferencia de votos del margen de error sean 1.200 votos. ¿Que significa esto? Que si esa diferencia es la que se da a favor de un candidato, la probabilidad de que sea el ganador "verdadero" es del 99%. Si la diferencia de votos es menor, el margen de confianza será del 98% o del 95%, pero nunca se puede hablar de empate (probabilidad del 50% de que haya ganado uno de los dos), porque sea cual sea la precisión de las máquinas, para eso la diferencia de votos debería ser 0.
El nivel de confianza, por cierto, lo establece con su criterio quien hace el estudio (o quien lo encarga), por ello debe figurar obligatoriamente en la ficha técnica de las encuestas.
En el caso de Florida, con la diferencia de votos de Bush y la precisión de las máquinas, se podría decir que el nivel de confianza de su victoría es, quizás, del 97,5% y que eso es muy poco. Pero no es un empate. Si la diferencia hubiera sido mayor, desde el momento en que las máquinas pueden errar, la probabilidad de victoria "real" nunca sería 1, sino el 99,99999%.
No se si he sido muy pedagógico. Estudié esto hace muchos años y estoy escribiendo de memoria. Pero una cosa debe quedar clara, estamos hablando de PROBABILIDAD, por tanto, podemos hablar de niveles del 98%, del 95% o del 83% (según el error intrínseco de las máquinas), pero si el número de votos del recuento oficial es mayor para un candidato, la probabilidad de que esta candidato haya sido el más votado "realmente", siempre será superior al 50%.
Separemos la ciencia de los juicios de valor.
Un cordial saludo.
Nota: Por favor, no plantee preguntas tan difíciles, que llega la navidad y hay que dedicar el tiempo a otros menesteres.
En efecto, no he encontrado una forma sencilla de abordar el problema. Parece que sólo la alternativa de la fuerza bruta funciona.
En cuanto a lo de Florida, intentaré buscar el mensaje original de Paulos. Es posible que no lo haya reflejado bien.
Un cordial saludo.
Lo prometido es deuda. Éste es el artículo original de Paulos. SI quiere, lo analizamos luego:
http://abcnews.go.com/Technology/WhosCounting/story?id=97488&page=1
Un saludo.
He estado echando un vistazo al artículo y es más periodístico que otra cosa.
Además, no va por donde yo suponía (dado el error intrínseco del recuento y la escasa diferencia de votos en los resultados oficiales, el nivel de confianza de los resultados sería bajo, comparado con el normal en un resultado electoral).
Más bien, se refiere a que el número de votos sobre los que hay reclamación supera a la diferencia entre uno y otro candidato. Bueno, pues si. Pero así ocurrió y no caben muchas más vueltas.
Y en cuanto a lo de Buchanan, tampoco veo muy claro lo que quiere decir. No vale plantear una recta de regresión con n-1 valores y luego
comparar con el 1 restante. Al menos sin más datos. Debería cuantificar esa desviación y asignarle una probabilidad.
Bueno, al fin y al cabo, como decía es un artículo y no un estudio científico. Sí que es ilustrativo el ejemplo que plantea con la probabilidad del juego de cara y cruz. Pero tampoco da mucho más de si.
Sobre el cálculo de arriba, si tengo tiempo lo formularé un poco mejor, dentro de las limitaciones del medio. Al releerlo me parece que no queda ni medio claro.
Saludos y buen fin de semana.
Ijon (no me deja entrar con el nick)¿?
Tampoco a mí se me ocurre como expresar de forma sencilla el cálculo necesario. Sin embargo, es muy sencillo escribir un programa que simule el proceso.
Tras un millón de repeticiones de la prueba, con 30 elementos estas son las probabilidades de acertar:
0,0.367256
1,0.368433
2,0.183768
3,0.061426
4,0.015396
5,0.003118
6,0.000515
7,0.000076
8,0.000010
9,0.000002
10..30: 0
Es decir, era ligeramente más probable acertar uno que ninguno. Y la probabilidad de acertar al menos uno era casi el doble que la de no acertar ninguno.
Hola, buenos días. Me he entretenido un poco con esto el fin de semana así que voy a intentar formular un poco el cálculo según indicaba arriba a grandes rasgos:
La probabilidad de cero aciertos es obviamente el número de casos con cero aciertos, partido por el número de casos totales. Este número de casos totales es permutaciones de 30 = 30! = 2,65*10E32.
A su vez, el número de casos con cero aciertos será el número de casos totales menos (el número de casos con 30 aciertos + número de casos con 28 aciertos + número de casos con 27 aciertos + ..... + número de casos con 3 aciertos + número de casos con 2 aciertos + número de casos con 1 acierto).
Formulemos estos casos:
1 + 0 + combinat(30;28)*p2 + combinat (30;27)*p3 + combinat (30;26)*p4 + ..... + combinat(30;3)*p27 + combinat (30;2)*p28 + combinat (30;1)*p29.
El número de casos con 30 aciertos es obviamente 1.
El número de casos con 29 aciertos es 0.
El número de casos con 28 aciertos será el producto de:
Las combinaciones posibles de 30 elementos tomados de 28 en 28, o sea combinat(30;28) = 30!/(28!*(30-28)!) = (30*29)/2 = 435
y:
p2 = Las permutaciones de los 2 elementos restantes (30-28) en las que nínguno de los 2 elementos está en posición de acierto. Las permutaciones de 2 elementos son 2 (1,2) y (2,1). De esas solo en una (la segunda) no hay acierto. Por tanto p2 = 1.
El número de casos con 27 aciertos será igualemente el producto de:
Las combinaciones de 30 elementos tomados de 27 en 27, o sea, combinat(30;27) = 30!/(27!*(30-27)!) = (30*29*28)/(3*2) = 4060.
y:
p3 = Las permutaciones de los 3 elementos restantes (30-27) en las que ninguno de los 3 elementos está en la posición de acierto. Las permutaciones de 3 elementos son 3! = 3*2*1 = 6, veamos: (1,2,3); (1,3,2); (2,1,3); (2,3,1); (3,1,2); (3,2,1). De estos 6 casos, hay solo dos sin acierto: (2,3,1) y (3,1,2). Por tanto, p3=2.
........
El número de casos con 1 acierto será el producto de combinat(30;1)*p29
Ahora viene el problema ¿como calculamos p29? Pues haciendo el mismo cálculo pero en lugar de con 30 identificaciones con 29. A su vez, para este cálculo necesitamos p28 y así sucesivamente.
Veamos el cálculo de p4. Lo podemos hacer "a pelo" (para n=4, son 24 casos) o aplicando la fórmula de arriba:
p4 serán los casos totales (4!=4*3*2*1=24) menos (los casos de 4 aciertos más los casos de tres aciertos más los casos de dos aciertos más los casos de 1 acierto):
p4 = 4! - (1 + 0 + combinat(4;2)*p2 + combinat(4;1)*p3)
calculando las combinaciones y usando los valores de p2 y p3 que hemos visto arriba, tenemos para p4:
p4 = 24 - (1 + 0 + 6*1 + 4*2) = 24 - 15 = 9
Esto es, el número de permutaciones de 4 "sin acierto" son 9.
De igual modo calcularemos p5 (sale 44) e iremos ascendiendo hasta p30. Para ello es conveniente recurrir a la hoja de cálculo lógicamente.
No es inmediato, pero es un cálculo, no el recurso a la fuerza bruta que plantea "anónimo".
La probabilidad así obtenida, es del 36,79% (para cero aciertos).
Espero que haya quedado más claro.
Un saludo.
Anónimo no soy. Me olvidé de firmar como Carlos :-P
A mí me daba una probabilidad similar, pero tenía errores en mi programa. En efecto, parece no haber otra forma de calcular esto que a través de una regresión.
En todo caso, parece confirmarses lo que habíamos planteado: que la probabilidad seguramente sería finita, enteramente dentro de los límites de lo esperable.
Un abrazote, y si no nos vemos por aquí u otro sitio, felices fiestas!
PD. Lo mismo para Pedro e Igon
Felices fiestas y feliz viaje.
Ijon, yo tengo una duda sobre el problema. El problema creo que no se debería centrar a los 30 identificados, sino que debería intervenir tb los 62 que es la población. Es decir aqui se toman 30 y con las placas indetificativas de esas 30 personas. Lo que se está calculando es que el orden de de las identificaciones de 30 personas coincidan con la posición de esas 30 personas. Pero no se valora que se tomen grupos de 30 personas y que haya placas de indetificaciones de 62 que ni si quiera coicidan con la persona, no solo que se la cambien con otro, si no que no coincidan. No se si me he explicado bien, pero me parece una buen reflexión a valorar.
Saludos
Publicar un comentario
<< Home