Vistas de página en total

lunes, 31 de octubre de 2011

Una taba con sesgo

http://www.elpais.com/videos/sociedad/Azarosa/taba/elpepusoc/20111027elpepusoc_4/Ves/

El desafío de esta semana es el siguiente: a partir de la serie aleatoria de bits conseguida lanzando repetidamente una misma taba, obtener una serie de bits -que necesariamente será más corta que la serie de partida- que no se pueda distinguir de la que produce una moneda sin trucar, es decir: obtener una serie de bits aleatoria y sin sesgo.

La solución a este desafío debe incluir una breve explicación de las operaciones y los pasos que llevan desde la serie de bits de la taba hasta una serie aleatoria de bits sin sesgo. La solución ha de funcionar usando una única taba, que puede ser cualquiera: por ejemplo, una de las tres que yo tengo aquí u otra taba que vosotros tengáis.

La idea es convertir una serie sesgada por ejemplo de unos y ceros en una serie no sesgada, es decir que sea tan probable encontrar unos como ceros.
Lo primero que pensé es en una forma de onda donde los unos son valores positivos y los ceros valores negativos.

Así pensé en sustituir los unos y los ceros por otra cosa, por ejemplo por cambios de signo. Así nos sale que es tan probable el 1 (cambio a positivo) como el cero (cambio a negativo). Pero hay un problema: que nos sale una serie 0,1,0,1,0,1,0,1

¿Cómo arreglarlo para que salga una serie aleatoria en función de la original?


Simplemente cogiendo los números originales de 2 en 2 y tomando solo los que tienen un cambio es decir 01 y 10 que los convertiremos en 1 y 0 respectivamente.


Ejemplo

Serie original

01110110011110101111


01 11 01 10 01 11 10 10 11 11


01 01 10 01 10 10


1 1 0 1 0 0


Matemáticamente: Si la probabilidad de que salga un 1 es X y la de que salga un 0 es Y, siendo X distinto de Y, la serie es sesgada, pero la probabilidad de que salga 10 es XY y la de que salga 01 es YX, es decir igual y por tanto la serie es no sesgada.

Finalmente la serie final va a ser sensiblemente inferior a la original. En el caso de que no hubiera sesgo quedaría 50% * 50% = 25%. Y el valor se aproximaría a cero en función de lo sesgada que esté la serie original.

lunes, 3 de octubre de 2011

Una paradoja electoral

http://www.elpais.com/videos/sociedad/paradoja/electoral/elpvidsoc/20110929elpepusoc_1/Ves/

Se quiere elegir a un representante entre varios candidatos. Muchos dirían que las matemáticas que intervienen en el proceso se reducen a contar el número de votos. Y, sin embargo, en cuanto se examina la situación con un poco de detalle, se ve que surgen fenómenos extraños.

Imaginemos que, en unas elecciones a las que se presentan siete candidatos, uno de ellos recibe el 40% de los votos, y que el 60% restante se reparte de igual manera entre los otros seis. Sin pensarlo dos veces declaramos ganador por mayoría simple al primer candidato. Ahora bien, si pidiéramos a los votantes que dijeran no solo cuál es su candidato preferido, sino también quién es el que menos les gusta, podría darse la circunstancia de que todos aquellos que no han votado al candidato ganador lo colocasen en último lugar. Y entonces se habría declarado ganador a un candidato que es... ¡el que menos gusta por mayoría absoluta!
Este fenómeno se conoce como paradoja de Borda, en honor al matemático e ingeniero francés Jean-Charles de Borda, que vivió en el siglo XVIII. Precisamente con la intención de que el resultado de las elecciones se ajustase mejor a los gustos de los votantes, Borda introdujo un nuevo método de recuento en el que cada elector coloca a todos los candidatos en orden de preferencia. Por cada votante, si el candidato está en la última posición recibe un punto; si está en la penúltima, dos; en la tercera por el final, tres; y así sucesivamente. A continuación se suman todos los puntos y se declara ganador al que más tiene.
Por ejemplo, en una elección en la que cuatro personas eligen entre tres candidatos A, B y C ordenados del siguiente modo:
Votante 1: A>B>C
Votante 2: C>B>A
Votante 3: B>C>A
Votante 4: A>B>C
Así, el candidato A recibe 3+1+1+3=8 puntos, B recibe 2+2+3+2=9 y C recibe 1+3+2+1=7, luego se declara ganador a B. Ahora bien, el método de Borda da un ganador que podría ser distinto del ganador por mayoría. De hecho, si solo hubiésemos tenido en cuenta el candidato preferido, el ganador habría sido A, que tiene 2 votos, en lugar de 1 como B y C.
Y el desafío de la semana es el siguiente: supongamos que n candidatos se presentan a unas elecciones, ¿qué porcentaje de apoyos tiene que recibir como mínimo un ganador por mayoría para que podamos asegurar que también sería el ganador si el recuento de los votos se hubiera realizado según el método de Borda?

Suponiendo que hay uno que ha obtenido más votos que los demás y ha obtenido el X% de los votos en primer lugar. Suponemos que hay N candidatos.
Vamos a ver cuál es el caso peor para él:
X*N votos + (1-X) votos.
A su vez el caso peor para él es que hay otro que obtenga el máximo posible, que sería:
(1 - X) * N + X*(N - 1)
Igualamos las dos expresiones y nos queda:
XN + 1 - X = N - XN + XN - X
XN + 1 = N

X = (N -1) / N

 Es decir para el caso de 2 el 50% , el caso de 3, 66.66%,... para N = 10, el 90 % de los votos.