Siguiendo con el tema de la semana he pedido un par de reviews y me he metido un poco  más a fondo en teoria de juegos. Lo primero para no perderme ha sido el clasificar todos los juegos simetricos, de dos jugadores con dos posibles movimientos (C y D, Colaborar o Desertar) y cuatro posibles resultados: cobramos R si ambos colaboramos, S si Colaboramos pero el contrario Deserta, T en el caso reciproco, y P si ambos desertamos. En principio hay 24 posibles formas de ordenar los cuatro valores, y con el convenio R>P se reducirian a 12. La clasificación, incluyendo tambien juegos asimetricos, la hicieron en los sesenta Rapoport and Guyer (“A taxonomy of 2×2 games” , aunque es mas facil encontrar en la red una mas reciente de Robinson and Goforth del año 2005.

Podemos ver los distintos juegos sobre el plano T-S: Dado que tanto T como S pueden ser estar en tres posiciones respecto a P<R, tenemos nueve juegos:

                  |         ||
       Mixed      | Pure    ||
       Delight    | Delight ||       Hero
                  |         ||
------------------+---------++------------------S=R
  Mixed Harmony   | Harmony ||     Chicken
==================+=========++==================S=P
                  |         ||
     Coordination |  Stag   || Prisoner Dilemma
                  |  Hunt   ||
                 T=P       T=R

Además en los casos Coordination, Harmony y Hero puede que T sea mayor que S o lo contrario, lo que nos define, cortando esos sectores en diagonal tres juegos mas, y ya tenemos el total de 12. En el caso especial de R=P=0 es posible intercambiar T y S, y solo quedarian Hero, Coordination y Prisoner Dilema (o MD).

En la práctica se suele normalizar con P=0 y R=1, y estudiar un cuadrado con S en [-1 .. 1] y T en [0 .. 2], lo que captura esencialmente cinco juegos: Chicken, PD, SH, y los dos triangulos en los que se ha divido Harmony (a veces al triangulo inferior se le llama “No Conflict”). Esto se hace asi porque realmente las propiedades de equilibrio del juego pivotan sobre si S es mejor o peor resultado que P y si T es mejor o peor resultado que R. Esto es, alrededor del punto (T=1,S=0) en la normalizacion habitual.

El juego del “bote de una loteria de un solo numero” que hemos jugado en los dos post anteriores esta un poco fuera de la normalizacion: vemos que tiene la propiedad de que S=R=0,  llamando “Colaborar” al hecho de no comprar el billete (sí, suena raro, pero se trata de mantener el convenio R > P), P=bote/2 – ticket < 0, y T =Bote – Ticket > 0. Se trata pues de un caso limite de Chicken: cuando los dos jugadores compran billete, ambos pierden, al igual que cuando ninguno de los dos conductores del chicken gira para apartarse. La unica complicacion es que en esta normalizacion no podriamos estudiar bien el caso en el que el bote crece tanto que se hace mayor que dos veces el ticket, pero la verdad es que tampoco vamos a hacerlo; ya fue suficiente con dos posts sobre la loteria dichosa.

Lo que si que me interesa por encima de esta clasificacion es una circunstancia que puede marcar diferencias cuando el juego se plantea repetidas veces: los casos en los que a los dos jugadores les mereceria mas la pena pactar para ir llevandose alternativamente S + T en vez de R + R.  Esta linea S+T > 2R, o simplemente S+T > 2 en la normalizacion habitual, deberia tener algun efecto en la clasificacion, pero al no afectar para la construccion de los equilibrios de Nash tampoco afecta a las simulaciones con modelos evolutivos, al menos no en los casos mas comunes. Se podria decir que el juego no es capaz de explotar adecuadamente los “recursos naturales”.

En el caso concreto de Chicken (Snowdrift, Hawks and Doves), calculemos el equilibrio mixto. Si el primer jugador tiene una probabilidad p de jugar “C”, y el segundo una probabilidad q de lo mismo, el cobro del primer jugador sera a la larga:

p q  R + p (1-q) S + (1-p) q T + (1-p) (1-q) P

o, ya con R=1, P=0, y separando terminos

p ( q (1-S-T) + S) ) + q T

la condicion de equilibrio es que el termino multiplicando p sea nulo, esto es

q= S / (S+T-1)

Y cuando toda la poblacion ha evolucionado hacia el punto de equilibrio q el valor extraido por cualquier jugador es a la larga el dado por la primera ecuacion poniento tambien p=q, esto es

S T / (S+T-1)

Incidentalmente, notad que la condicion de equilibrio es una recta que pasa por S=0, T=1. En cierto modo esta familia de rectas, para q entre cero y uno, va interpolando desde el dilema del prisionero hasta Harmony. La recta para q=1/2 es paralela a la diagonal S=T.

Otra pregunta seria, sabiendo que en el equilibrio el valor extraido por jugador va a ser este p ( p (1-S-T) + S) ) + p T, ¿cual seria la estrategia mixta que maximiza la extraccion de valor?. Derivando la funcion, tendriamos la condicion

0 =  2 p (1-S-T) + (S+T)

con solucion

p = (S + T) / 2(S+T-1)

que extraeria un valor por jugador de

[(S + T) / 2(S+T-1)]  ( [(S + T) / 2(S+T-1)]  (1-S-T)  + (S+T) ) = [(S + T) / 2(S+T-1)] (  (S+T) /2)) =
= (S+T)^2 /  4(S+T-1)

Si  (S+T)/2 = S, entonces el equilibrio de Nash es tambien la mejor estrategia mixta a la hora de extraer valor. Esto es la diagonal S=T, que en realidad ni siquiera es dominio de Chicken.

Lejos de esta diagonal,  el equilibrio de Nash es una estrategia ineficaz, la diferencia seria:

(S+T)^2 /  4(S+T-1) – S T / (S+T-1)  =   (S-T)^2 /  4(S+T-1)

Es interesante que las soluciones de mayor eficacia dependen solo de S+T, esto es, forman rectas antidiagonales, perpendiculares a la S=T. Una forma grafica de visualizar por tanto la “solucion eficaz” para un juego (1,S,T,0) es proyectar, o trasladar, perpendicularmente la coordenada (S,T) a la diagonal y tomar la solucion de Nash para el juego resultante, llamemosle (2, S+T, S+T, 0).

Otra cosa que podemos observar mirando la forma de p en funcion de S+T, esto es (S + T) / 2(S+T-1), es que p < 1 solo si (S+T) > 2 ó si (S+T)<0.  La primera de estas condiciones es tambien, como emos mencionado más arriba, la condicion para que empieze a merecer la pena ponerse de acuerdo para jugar CD o DC alternativamente en vez de jugar por el Reward. A medida que va aumentando (S+T), el valor de p va descendiendo hacia 1/2, confirmando el metodo “gráfico” que hemos sugerido en el parrafo anterior.

Por otra parte, si (S+T)/2 es pues el maximo valor extraible por jugada si los jugadores pudieran adoptar algun metodo para ponerse de acuerdo, otra forma de leer las ecuaciones es que el valor optimo (S+T)/2 recibe de partida una correccion (S+T)/ 2(S+T-1) por el hecho de quedarnos limitados a usar soluciones de estrategia mixta, sin memoria ni contexto de las jugadas anteriores.

La cuestion que quiero enfocar en el siguiente post es. ¿hay alguna modificacion del juego, en terminos de reglas de evolucion, que permita equilibrios sobre estrategias mixtas mas eficaces que el equilibrio de Nash? Esto puede ser factible porque las reglas de update en una simulacion tienen en realidad influencia sobre el punto de equilbrio. La cuestion es si se puede aprovechar esa influencia para  ajustarse al optimo de extraccion de una manera razonable, o si simplemente nos desplazamos hacia otro equilibrio sin poder relacionarlo con el óptimo. Pero eso ya sera para el fin de semana.

First of all, congratulations to the winners. Lets try to collect here the final data of the  jackpot run:  Reminder, the jackpot prize comes from an extraction of 5 numbers from 69 plus another of 1 number between 26. This was chosen purposefully last year, to produce this kind of big prizes once in the yer. (69 5) times 26 is 292 201338, ticket price is $2 and you can expect a return from minor prizes setting the price to a lower $1.58. The number of players was unknown, but  from the increase of the jackpot it can be napkin-guessed to be around 635M, (no idea why the estimation of wired is a lot lower, say 170M, and on the other hand (1500-947.9)/0.34/2 is even greater, 800M. Perhaps it should be estimated from the cash-payout, which is a 62% of the jackpot?).  There has been, or it is claimed so, three winners that will share the big prize. The number of players increases faster than linear with the size of the jackpot, fitting well with quadratic (!) or exponential function.

Now, back to the game-theoretical considerations of yesterday.

We assume a god-given jackpot, a “resource” to be harvested, having always the same value, and players having no memory of previous winners, so that they only can choose between buying or not the offered tickets. They can do it by having a internal preference q1,q2,… between 0 and 1 and drawing a random number to decide.

One point of the lottery is that our result if we do not play is simply zero, not losses -except moral ones if some friend wins, of course-. In the general formula for the expected win, with p our own mixed strategy,

p f(q1,q2,q3,…) + (1-p) g( q1,q2,q3,…)

the function g is zero. This means that whatever mixed strategy the other players choose, the total expected win will always be proportional to our own probability p of playing. This also means that if f(…) were non zero, we should always counter by moving to a pure strategy, either p=1 or p=0. So this kind equilibrium happens only when p is cancelled out because  f(…) itself is equal to g(…) ; in  this case g() is zero, and then the expected benefit in the long run for all the players will be zero. Generically the benefit will be exactly the same as the pure strategy of not playing at all.

Another argument for not to play is to minimize your expected loss if you are completely unsure of the other partners strategy: if g(…) is zero but f(q1,q2,q3…) can be less than zero, then p=0 is your escape option.

Of course all of this is a tragedy because a god-given jackpot could be harvested. Ideal goal is to coordinate all players to buy only exactly the 292 201338 combinations, and share the prize.  The question is, can it be done, or approximated, without a fully forceful central coordination?  I leave it open.

What about populating the lotto world with hawks and doves? This is, the players can be either fanatic, always play for this amount of jackpot, or pessimistic, never playing. A initial population of doves could gradually mutate to hawks in order to extract some benefit for the resource, but at some point the probability of fighting hawk vs hawk should stop the mutation and keep a fixed level of players against no players. Is this point also given by the same equilibrium that above? If so, is the total resource extraction again zero? I have run some simulations and it seems that the proportion of hawks evolves to be slightly smaller that the expected point of zero benefit, but still near enough to attribute the discrepancy to finite size effects, and finite number of trials. Of course, that implies another philosophical question, given the fact that real games have a finite number of trials, should we recalculate for only a few trials?

There is, to me, some lack of intuition here. One could think that the idea in a lottery is to keep adding players until the probability of benefit becomes zero again, and that in hawks and doves we keep turning doves into hawks also in the same way, until the benefit extracted from the game becomes zero. This seems consistent with setting to zero the above equation, for the case g(q) =0, f(q)= q (P/2-T) + (1-q) (P-T), is

p (P-T) + p q (-P/2)

and then f(…) =0, exhausting but if there is some small prize or penalisation K when we do not play, the intuition fails, as then we need the partial respect to p of

p f(q1,q2,q3,…) + (1-p) K

and we get f(…) = K and the total expected benefit equal to K, not zero. So in principle if K is still positive there is room to turn doves to hawks even beyond the equilibrium point. The general solution  q (P/2-T) + (1-q) (P-T) = K is   q=   2 (1-T/P) –  2K/P

Ok, the powerball lottery of tomorrow, Jan  13th, 2016.  Some of the math has been already done here and there. So I was thinking another approach: Lets assume that a couple of Forbes-listed guys likes to play lotto in this favorable situation.
Think Gates and Buffet, or any of your preferred top ten or whatever corporations they own, or the corporations themselves (This is also considered by Andy Kiersz).

According numbers in “is-the-powerball-lottery-profitable“,
the total ticket cost is, at 2$ each number, $584M -$93.4 (prices) – $175M (self-jackpot) = 280M. And the jackpot price is 1.3 billion. Share between both players, it is still 650M
IRS tax is not problem for them, the corporations have an army of lawyers taking care of it, it is irrelevant for them, and  same with other expenses as buying some lottery franchise, workers, management etc.

So should they play? Well, obviously yes if they are the only two players. They are still going to get $370M worst case. This is not very interesting.

What about two weeks ago, when the prize was only $528M?  Sharing the price they get $264M, less than the cost of the, er, “ticket”. So they are into a sort of
snowdrift or chicken game, (or hawks, doves or whatever bird you like):

           G Passes     G buys ticket
B Passes     0, 0         0, 248M
B Buys    248M, 0      -16M, -16M

(the numbers come from the differences 528-280=248 and 264-280=-16)

With pure strategies there are two situations with Nash equilibrium: either (G Buys, B Passes) or the reciprocal. In such situations, nobody has
incentive to change his move. But this fact is not help to decide what to play, specially
in a situation without memory of the previous games.

There is also a mixed equilibrium. Consider the
mixed strategies where G and B decision of buying the game has a
probability p, q, respectively. So G’s expectation of benefit is

p(1-q) 248M – p q 16M

and if B sets his mixed strategy to q= 248/264 = 0.9394 then G’s expectation is
zero independently of q. And same exchanging the roles.

Warning: I have an issue here: if I want to look for evolutionary stable strategies, I’d think I should set p=q, differentiate the above expectation, and look for extremes, and then I get p=q=124/264=0.4697. Obviously this value of (p,q) is not a Nash equilibrium because one player can move p fully up to  1.0 and get a benefit from it.  But it is better: in the long run it gets about 58M of benefit for each player in average, instead of zero. Cooperation emerging from symmetry?

So, should G and B just throw a random number and then decide to play only if this
number is less than 0.9429? At least it looks rational.

Does it get more interesting with more players? Not a lot more, because the realistic number of tickets sold is estimated to be equivalent to three or four billonaire players. Well, lets see For a 1.3B jackpot to be unprofitable, we
need at least five, so that 1300/5 – 280 = -20 < 0. Lets say we have
other three players from the top 20 (hey, looking at the list there are some
math-minded guys in fact: Brin, Page, Bezos… rational enough to proceed
via game theory :-). Regrettably the calculation of the mixed strategy
becomes more complicated: we need to consider five separate probabilities
and the fact that we have situation with zero to five people sharing
the jackpot.

I think we could do a guess by assuming that the equilibrium solution sets everybody
to an expectation of zero losses (and zero benefit). This really works in the
previous case, setting p=q and asking p ( 248M – p *260M) = 0, but I am not sure about generalizing. Well, if we do, we ask

0= p^5 (1300/5 – 280)
+ 4 p^4(1-p) (1300/4 – 280)
+ 6 p^3(1-p)^2 (1300/3 – 280)
+ 4 p^2(1-p)^3 (1300/2 – 280)
+ p (1-p)^4 (1300 – 280)

to wolfram alpha, we see that there is only a root between zero and one:

p = 0.92857…

So the mixed strategy could be to play only if rnd() < 0.92857. Of course if the other four players adhere to this strategy, it is true that the extant player gets zero losses (and zero benefit) for any mixed strategy he chooses.

Again, consider two weeks ago, when we only had $528M in the jackpot. Then

0= p^5 (528/5 – 280)
+ 4 p^4(1-p) (528/4 – 280)
+ 6 p^3(1-p)^2 (528/3 – 280)
+ 4 p^2(1-p)^3 (528/2 – 280)
+ p (1-p)^4 (528 – 280)

gives p=0.32384…

I am not sure what those solutions mean. It is clear that if the players were able to
coordinate they could choose to form a cartel, only one of them playing each
week and thus extracting the same benefit but only at the cost of one “full ticket”. If
they are able to evolve to such understanding, this is a topic for
Evolutionary Game Theory. But then, as I said in the red warning above, we perhaps want to define stability from the derivative of the expectation function across the diagonal.

 

En el post anterior hemos demostrado, a regañadientes, que que la probabilidad de empate en 3030 votantes, cuando no hay conocimiento de la distribucion de voto (y por tanto se considera que puede tomar uniformemente cualquier calor en el intervalo [0,1]),  da 1/3031=0.0329%. El gran problema de las demostraciones verbales de este resultado  es que pueden inducir generalmente a errores muy terribles en otros calculos. Esto ocurre a la hora de considerar qué resultados, o “casos”, son equiprobables. La uniformidad no implica equiprobabilidad.

Un ejemplo curioso, en el que con el mismo hilo argumental conseguimos erroneamente la respuesta correcta, es el siguiente problema: la probabilidad de ganar en la apuesta de sacar cara tirando una moneda, de equilibrio desconocido, como máximo dos veces. Los distintos posibles lances del juego son

1. ) saco cara y gano,
2. ) saco cruz pero luego cara,
3. ) saco cruz y cruz.

Como tengo tres casos, y dos de ellos me son favorables, la probabilidad de ganar es de 2/3.

¡El resultado es correcto! Pero el argumento es una mierda, es falso, esta asumiendo que la probabilidad de cada uno de esos tres casos es 1/3 cuando en realidad la del primero es 1/2, la del segundo 1/6 y la del tercero 1/3. Resulta que un medio y un sexto suman dos tercios, pero ha sido más suerte que industria.

Revisemoslo. Es facil ver que la probabilidad del tercero de los casos es 1/3.  Si la probabilidad de sacar cara es “p”, dado que desconocemos cual es el valor concreto de p, integramos sobre todos los posibles y tenemos

P(cruz,cruz)=\(\int_0^1 (1-p)^2 dp \) = 1/3

Bueno, este 1/3 sí que coincide con el del estimado “verbal”.  Por supuesto, si supieramos que la moneda esta perfectamente equilibrada, no integramos sobre todos los posibles, sino solamente sobre p=1/2, la formula en ese caso seria, usando la delta de dirac

P^{1/2}(cruz,cruz)= \(\int_0^1 \delta(p-0.5) (1-p)^2 dp\) = 1/4

Pero seria otro cantar. Volvamos al ejemplo y calculemos el segundo de los casos:

P(cruz, cara)=\(\int_0^1 p(1-p) dp\)=  1/2 – 1/3 = 1/6

Y por supuesto el primer caso

P(cara, cualquiera) =\(\int_0^1 p \; dp\) = 1/2

Por cierto que aqui es donde comenta David Ruescas que suele ocurrir otro error,  igualar el caso de p desconocida con el de p=1/2, porque para una tirada de una sola moneda (o para tiradas de multiples monedas todas diferentes) es correcto usar 1/2 como reflejo el desconocimento sobre esa moneda. No lo es cuando hacemos multiples tiradas de la misma ni, como en el caso de una votacion, cuando estamos extrayendo una muestra de una unica poblacion, cuyo porcentaje de opiniones, desconocido, equivaldria al p de la moneda.

Es posible, claro esta, hacer una argumentacion “verbal” correcta y decir que tenemos tres casos, 1′) cara y cara, 2′) cara y cruz y 3′) cruz y cruz, dada uno con una probabilidad de 1/3 cuando tomamos el valor de p desconocido. Pero asi de oido, el argumento es igual que el erroneo; lo que le da valor es calcular las integrales: las de 3′ ya las hemos hecho y da 1/3, obviamente lo mismo la de 1′, y la de 2′ s mas sutil pues ha de sumar dos “casos elementales”

P { caras=1, cruces=1 } =\(\int_0^1 (p(1-p)+(1-p)p)) dp \) = 1 -2/3 = 1/3

Como era de esperar. Y naturalmente, con una moneda perfectamente equilibrada

P^{1/2}{ caras=1, cruces=1 }= \(\int_0^1 \delta(p-0.5)(p(1-p)+(1-p)p))dp \) = 1/4 + 1/4 = 1/2

O con dos monedas desconocidas, por supuesto, seria otra historia:

P^{p,q} { caras=1, cruces=1 } =\(\int_0^1 \int_0^1 (p(1-q)+(1-p)q)) dp\;dq\)  = 1/2

El señor que propuso este ejemplo y el razonamiento incorrecto que sin embargo daba en una situacion peculiar la solucion correcta (esto es, para una moneda de propiedades desconocidas, pero no para una moneda equilibrada) fue un asambleista revolucionario, un tal D’Alembert. De hecho, intentó añadir a la seccion de “Probabilite” de la Enciclopedia unas cuantas paginas con lo que el veia como paradojas del calculo de probabilidades -más complicadas que esta- pero Diderot le obligó a quitarlas. Con el tiempo, y una vez llegó a tener conocimiento de los escritos de Bayes, D’Alembert suavizo sus posturas, pero al parecer este ejemplo todavia se quedo en la memoria de su discipulo Laplace, que lo empleó en las paginas de introduccion a sus leyes de la probabilidad.

Podeis leer más de la historia de D’Alembert  y sus problemas con la probabilidad -no son el tema principal que tocamos aquí- en este trabajo de historia de Michael Paty. En cuanto al texto de Laplace, aunque esta disponible en la wikipedia, quizas sea interesante ponerlo aqui mismo. Tened en cuenta que Laplace esta simplemente hablando del caso con una moneda bien equilibrada y que se limita a referirse a su maestro de pasada, sin concretar las circunstancias concretas. Simplemente he tomado este mismo ejemplo porque parece el mas sencillo con p en una distribucion uniforme pero tres casos no equiprobables.

---

 

I^er Principe.Le premier de ces principes est la définition même de la probabilité qui, comme on l’a vu, est le rapport du nombre des cas favorables à celui de tous les cas possibles.

II^e Principe.Mais cela suppose les divers cas également possibles. S’ils ne le sont pas, on déterminera d’abord leurs possibilités respectives dont la juste appréciation est un des points les plus délicats de la théorie des hasards. Alors la probabilité sera la somme des possibilités de chaque cas favorable. Éclaircissons ce principe par un exemple.

Supposons que l’on projette en l’air une pièce large et très mince dont les deux grandes faces opposées, que nous nommerons croix et pile, soient parfaitement semblables. Cherchons la probabilité d’amener croix, une fois au moins en deux coups. Il est clair qu’il peut arriver quatre cas également possibles, savoir, croix au premier et au second coup ; croix au premier coup etpile au second ; pile au premier coup et croix au second ; enfin pile aux deux coups. Les trois premiers cas sont favorables à l’évènement dont on cherche la probabilité, qui, par conséquent, est égale à  ; en sorte qu’il y a trois contre un à parier que croix arrivera au moins une fois en deux coups.

On peut ne compter à ce jeu que trois cas différens, savoir : croix au premier coup, ce qui dispense d’en jouer un second ; pile au premier coup et croix au second ; enfin pile au premier et au second coup. Cela réduirait la probabilité à , si l’on considérait, avec d’Alembert, ces trois cas comme également possibles. Mais il est visible que la probabilité d’amener croix au premier coup est , tandis que celle des deux autres cas est  ; le premier cas étant un évènement simple qui correspond aux deux évènemens composés, croix au premier et au second coup, et croix au premier coup, pile au second. Maintenant, si, conformément au second principe, on ajoute la possibilité de croix au premier coup, à la possibilité de pile arrivant au premier coup et croix au second, on aura pour la probabilité cherchée, ce qui s’accorde avec ce que l’on trouve dans la supposition où l’on joue les deux coups. Cette supposition ne change point le sort de celui qui parie pour cet événement : elle sert seulement à réduire les divers cas à des cas également possibles.

Ayer el empate de la CUP nos dio a todos una buena oportunidad para refrescar nuestros instintos sobre la distribucion binomial. En cuanto salio el resultado de 1515 la opcion 1 vs 1515 la opcion 2, un monton de gente pensamos ¿cual es la probabilidad de empatar tirando 3030 monedas a cara o cruz?

Bien, obviamente numero de conjuntos posibles de 1515 cruces divido entre el total de conjuntos de cruces posibles, esto es (3030 1515) = 3030! / (1015! 1515!) dividido entre 2^3030. Un 1.45 % aproximadamente. O, usando la estadistica de la distribucion binomial con p=0.5 y 3030 extracciones:

(3030 1515) * (0.5)^1515 * (1-0.5)^1515

Bien. Y en estas empiezan a circular por la red dos discusiones. Una filosofica, por supuesto, sobre el concepto de probabilidad y si es aplicable en el caso de la toma de posiciones en un debate. Otra, mas tecnica, asumiendo que aqui lo que teniamos era una muestra de 3030 extracciones sobre alguna probabilidad subyacente, y cual era la matematica aplicable. Porque resulto que hubo muchos que opinaron que la probabilidad de empate era 1/3031, usease apenas un 0.03 %.

Las disculpas, por anticipado, son a todos estos que mantuvieron en la discusion que el resultado 1/3031 era válido, de alguna manera.  El unico argumento que se dio en twitter no iba precisamente muy bien para justificar su validez. Lo dio un profe de matematica aplicada de sevilla, que en 140 caracteres resumia:

Regla de Laplace para 3030 votos SÍ/NO de #ANECUP: 0/3030, …, 3030/0 dan 3031 casos posibles. Casos favorables: EMPATAR 1, NO EMPATAR 3030 (@mario_bilbao)

¿Regla de Laplace? ¿Casos favorables ente casos posibles? Pero eso es justo lo que hemos hecho en las tiradas de moneda, numero de conjuntos favorables entre numero de conjuntos posibles. No tiene sentido esa explicacion. Asi que cientos de personas nos aprestamos, yo entre los primeros, a replicar con explicaciones detalladas de como la binomial hacia que los 3031 casos posibles no fueran equiprobables. Por supuesto con p=0 tan solo seria posible el caso 3030 votos NO, y con p=1 solo seria posible 3030 votos SI, con una probabilidad cero de empate. Entre p=0 y el p=0.5 la probabilidad de empate se ira incrementando desde cero a 0.01449…   pero no se ve como el 0.03% sea especial. Parece claramente un error.

Por otro lado cuando alguna neurona me recordaba de mecanica estadistica la emergencia de casos donde conseguias cierta equiprobabilidad de configuraciones, y donde el rio suena agua lleva… puede que el señor Bilbao, que a fin de cuentas habrá pasado sobre estas ecuaciones muchas veces, recordara el resultado pero no la explicacion. Finalmente esta mañana @ruescasd, que habia dado independientemente el mismo 0.03% como estimacion conservadora, me lo ha explicado: ocurre si en vez de asumir p=0.5 o p en una banda 0.4 … 0.6 etc asumes que no sabes nada de la distribucion subyacente y escoges p al azar entre cero y uno.

Lo voy a poner en negrita, como me recomiendan en los comentarios:  en ausencia de información, el cálculo de la probabilidad de empate debe hacerse considerando todas los posibles valores de p, no p=0.5

¿Como se puede hacer esto? Es facil dicho para programadores: en la simulacion de la votacion en vez de usar

pvoto = 0.5
a =[ 1 if k > pvoto else 0 for k in npr.random(size=SIZE)]

usamos

pvoto = npr.random()
a =[ 1 if k > pvoto else 0 for k in npr.random(size=SIZE)]

Y cuando repetimos el experimento muchas veces entonces la probabilidad de empate convergera  a 1/3031, porque a fin de cuentas el numero “pvoto” no es mas que un numero random mas de los 3030 que hemos sacado, y cada uno de ellos tiene la misma probabilidad de estar en el medio. Es lo mismo que cuando sacamos tres hay un 33% de posibilidades de que el primero sea el que este enmedio, o cuando sacamos cinco hay un 20% de que el primero sea el que este enmedio (y un 20% de que sea el mayor, y un 20% de que sea el menor, etc).

Lo que estamos haciendo aqui, me explicaba @ruescasd, es usar una “beta binomial con prior uniforme“. Las beta binomial son una forma especialmente comoda, porque suele tener solucion analitica, de considerar a la vez la suma de muchas posibles distribuciones binomiales.

Por supuesto, una vez hemos abierto el coto de la simulacion con distintos escenarios para la distribucion subyacente podemos plantearnos distintos experimentos. Por ejemplo podriamos conjeturar que pvoto no es ni uniforme en [0,1] ni exactamente cara o cruz, sino que esta -uniformemente- en algun lado entre 0.4 y 0.6:

pvoto = 0.4 + 0.2*npr.random()
a =[ 1 if k > pvoto else 0 for k in npr.random(size=SIZE)]

En este caso la probabilidad de empate seria de tan solo el 0.16%… podriamos mantener una banda uniforme centrada en el “cara o cruz” e ir ensanchandola. Si la banda va de p=0.45 a p=0.55 la probabilidad de empate ya baja al 0.3%. Si va como p=0.4 a p=0.6 se reduce el 0.17%… asi hasta que la banda de indeterminacion cubre todo p=0 a p=1 y entonces tenemos la probabilidad de 0.03% dichosa.

Tabla: Caso de p alrededor de 0.5, variando la anchura

Para que veais que pronto se lia la cosa, vamos a interpolar entre las dos soluciones en disputa simplemente ampliando la incertidumbre acerca de la proximidad a 50:50 de la distribucion subyacente. Os doy la probabilidad de empate segun vamos ampliando

0.001:0.01447
0.002:0.01446 
0.01: 0.01373
0.02: 0.01203
0.03: 0.00991
0.04: 0.00802
0.05: 0.00653
0.06: 0.00550
0.07: 0.00472
0.08: 0.00412
0.09: 0.00366
0.1:  0.00329
0.2:  0.00164
0.3:  0.00109
0.4:  0.00082
0.5:  0.00066
0.6:  0.00054
0.7:  0.00047
0.8:  0.00041
0.9:  0.00036
1/3031=.0003299241...

Ya veis que funciona como hemos dicho mas arriba al comentar el algoritmo de simulacion: cuando la banda es solo de 0.499 a 0.501 la probabilidad es 0.01446, casi la misma que calculabamos con la binomial; si la incertidumbre va de 0.49 a 0.51 la probabilidad ya ha bajado a  0.01203; si va de 0.4 a 0.6 ya es de tan solo 0.00164. Por esto a no ser que se tenga certeza de que el resultado es estrecho -en este caso lo sabiamos por las votaciones anteriores- no es mala aproximacion suponer que la incertidumbre es total.

Pregunta: ¿Caso de p en banda [a,b]?

He intentado resolverlo analiticamente y me meto en un pantano de factoriales. En este caso estamos haciendo 3030 tiradas uniformes en (0,1), de las cuales daran SI las que salgan mayor que p, daran NO las que salgan  menor que p. Para que pueda haber empate es imprescindible que el numero n e tiradas cayendo en (0,a) y el numero m de tiradas cayendo en (b,1) puedan compensarse mediante un p en (a,b) que divida exactamente para contrapesar. Dentro del segmento (a,b) esto ocurre con probabilidad 1/(3031-m-n) dado que p en esa banda tiene la misma distribucion que el resto de los numeros que hayan caido ahi; es el mismo argumento de “equiprobabilidad” que con p uniforme en [0,1] en el caso de maxima ignorancia, y de hecho es la unica equiprobabilidad que hay en juego.

El problema esta en estimar la “trinomial” de caer en (0,a),(a,b) o (b,1) y luego sumarlas todas las probabilidades parciales con la condicion n < 1515, m<1515. Es un lio, pero es interesante pensarlo un ratito porque entiendes como al ir ensanchandose la banda va bajando la probabilidad de empate, y como tambien cambia si, sin ensancharse, se desliza hacia el p=0 o el p=1. Intuitivamente si la zona incertidumbre en la estimacion de la distribucion no pilla la zona del empate real, y dado que 3000 es una muestra ya bastante grande, sera dificil que se de el empate. Con p en el intervalo (0.4,0.5) estariamos en un 0.16%, con p en un intervalo mas grande, digamos (0.3,0.6) estariamos en 0.11%; y si lo suponemos en un intervalo (0.1,0.6) seria tan solo un  0.06%.

Obviamente se pueden dar probabilidades por debajo de la cota de “incertidumbre total”. Si estamos seguros de que p esta en el intervalo (0.1,0.48), por ejemplo, la probabilidad de empate es de solo 0.00001. Y con intervalos estrechos apoyados en los extremos la probabilidad de empate se ira acercando a cero, como corresponde al hecho de que ahi estarian todos en un solo bando.

¿Ignorancia total? ¿Principio de indiferencia?

Un argumento que se invoca para preferir la solucion prob(empate)=1/(n+1) es el “principio de indiferencia”, que ignoramos todo acerca de la distribucion subyacente y eso nos permite escogerla al azar.

Esto es, usamos la informacion de que hay una sola distribucion subyacente, con un unico parametro p que define su proporcion entre las dos opciones que se votan. Esto es intrigante, porque en el otro extremo si supusieramos que cada votante ha sido extraido de una distribucion diferente, ¡recuperariamos la binomial!. Porque para decidir su voto, el votante realizaria una tirara respecto de su parametro p, y sobre todos los votantes la probabilidad de que esas tiradas saquen la opcion A o la B es la misma. Podria arguirse pues que maximizar la indiferencia nos devuelve la binomial.

Esto se ve muy claro en el codigo. Para obtener 1/(n+1) usabamos en el bucle:

pvoto = npr.random()
a =[ 1 if k > pvoto else 0 for k in npr.random(size=SIZE)]

Si en vez de esto generamos un array con los p de cada distribucion de la que proviene cada votante

pvotante = npr.random(size=SIZE)
a =[ 1 if npr.random() > p else 0 for p in pvotante]

vemos que en realidad estamos generando de nuevo la binomial: la probabilidad de que  npr.random() sea mayor que otro npr.random() es de 1/2.

Un centenar de asambleas indiferentes

Por ultimo, sabemos que el caso real es intermedio: que los 3030 representantes lo eran de aproximadamente un centenar de asambleas.  ¡Podemos simular pues que no hay una unica p ni tres mil, sino un centenar! Para cada una de ellas desconocemos su proporcion p de votos entre las dos opciones, pero podemos aplicar la regla esa de indiferencia para simlarla. Y como podriamos esperar, saldra una probabilidad de empate intermedia:

• Asumiendo ignorancia de las distribuciones, de 101 asambleas enviando cada una 30 miembros, la probabilidad de empate seria el 0.45%
• Asumiendo ignorancia de las distribuciones, de 101 asambleas enviando cada una un numero aleatorio de miembros hasta sumar 3030,  la probabilidad de empate seria el 0.31%

El codigo para simular esto, basado en el gist de Galli, seria:

for i in xrange(1, LOOPS):
  l=np.empty([SIZE])
  for j in range(0,101):
    p=npr.random()
    l[j*30:j*30+30].fill(p)
  a =[ 1 if npr.random()> p else 0 for p in l ]
  if sum(a) == TIE:
    ties += 1
  if i % 1000 == 0:
  print("Total: {} ties: {} prob: {}".format(i, ties, ties/float(i)))

Y si queremos variar el numero de asistentes por cada asamblea

for i in xrange(1, LOOPS):
  l=np.empty([SIZE])
  div=npr.randint(SIZE,size=ASAMBLEAS+1)
  div.sort()
  div[0]=0
  div[ASAMBLEAS]=SIZE-1
  for j in range(0,ASAMBLEAS):
    p=npr.random()
    l[div[j]:div[j+1]].fill(p)
  a =[ 1 if npr.random()> p else 0 for p in l ]

Como hemos dicho, a medida que el numero de asambleas crece, el resultado vuelve a estar cerca del binomial. Para 606 asambleas enviando cada una 5 representantes, la probabilidad de empate es del 0.95%.

Hay aqui un poco de paradoja, que seguramente es la causa del debate. Revisemosla: si no sabemos nada de un asistente concreto, podemos pensar que la asamblea que proviene tiene una distribucion de probabilidad con un valor p que desconocemos aleatorio entre 0 y 1, y que el propio asistente puede ser de uno de los bandos con probabilidad p, del otro con probabilidad (1-p), lo que tenemos que asignar tirando un segundo aleatorio r, entre 0 y 1, y comprobando si es mayor o menor que p.  Y obviamente la probabilidad de que r>p, siendo los dos numeros aleatorios, es la misma que intercambiandolos, luego es 1/2.  Este es el mejor estimado que tenemos para el caso de considerar lo que va a votar un solo asistente proviniente de una asamblea dada cuya distribucion de preferencias desconocemos.  Pero cuando consideramos varios asistentes provinientes todos de esa misma asamblea la tirada “r” de cada uno cambia y todos tienen en comun la misma “p”, de forma que a mas asistentes, mas se acerca el resultado a la original de valor “p”, aunque sigamos desconociendola, y hay que incorporar ese hecho en las hipotesis, con la consecuencia de que la “binomialidad” se diluye en la aleatoriedad de p. Afortunadamente, como han discutido otros posts, suele haber mas datos para no tener que escoger entre estos dos casos extremos.

Una forma rápida de ver esta interpolación entre los dos casos es fijarse -como me han recordado Ruescas y Vilches- en qué variables aleatorias estan operando. Partimos del caso donde la ignorancia sobre la distribucion la representamos con una sola variable aleatoria que toma valores uniformemente entre 0 y 1. Al ir añadiendo asambleas, tenemos multiples variables aleatorias tomando valor uniforme pero su suma, pesada por la proporcion de asistentes, no es ya una variable aleatoria distribuida uniformente sino que se ira centrando -promediando- alrededor de 1/2.

Otras referencias

Parece que media internet ha entrado al trapo del debate, basta con buscar 3030 empate en google y salen decenas de blogs 0_0, y lo mismo en twitter.  Aparte de las aportaciones ya citadas de Galli y Ruescas en blogs,y gists, y de los comentarios de twitter, puede interesarte ver el articulo de prensa de Llaneras et al y comparar con alguno de los primeros, como el de Baraza.  Pueden valer para recordar que en todo caso la regla de “casos favorables dividido entre casos posibles” es una justificacion erronea de la estimacion 1/3031, y que la justificacion valida es mucho mas complicada y implica usar un concepto de ignorancia muy razonado, y su matematica asociada.

Mas jocosamente, pero con su toque divulgativo, ha tratado este asunto Federico Ardila (EN, CAT), usando el caso p=1/2 para terminar con un par de calculos probabilisticos del proceso de recuento que producen los numeros de Catalan.