sábado, 1 de mayo de 2010

Respuesta al problema de las tres puertas

El jueves escribi una nota sobre un problema, que gracias a al comentario de David ahora se que se conoce como el problema de Monty Hall.

Hubieron unos cuantos comentarios interesantes. David también dejó dos links a videos de YouTube donde se explica el problema y la solución. Los pueden ver acá y acá.

La respuesta es bastante poco intuitiva, o por lo menos así me pareció a mi.

El planteo del problema lo vi de casualidad en el programa Alterados por Pi, donde se daba también una solución que no me convenció. A los pocos días, volví a verlo en la película 21: Black Jack, donde se daba la misma solución.

Como no estaba convencido, es más, creía que daba lo mismo cambiar o no, decidí probarlo... así que como buen informático, hice un programa que hace la simulación...

Acá dejo el fuente (en C para que sea más rápido...):
#include <stdio.h>
#include <stdlib.h>

#define ITERACIONES 1000000
#define CANT_PUERTAS 3

int generarNumeroAleatorio() {
    return (arc4random() % CANT_PUERTAS);
}

void cargaPremio(int *contenido) {
    for (int i = 0; i < CANT_PUERTAS; i++) {
        contenido[i]=0;
    }
    int premio = generarNumeroAleatorio();
    contenido[premio] = 1;
}

int eligePuerta() {
    return generarNumeroAleatorio();
}

int abreOtraPuerta(int puertaElegida, int *contenido) {
    int otraPuerta = 0;
    int seguir = 1;
    while (seguir) {
        otraPuerta = generarNumeroAleatorio();
        if ((otraPuerta != puertaElegida) && (!contenido[otraPuerta]))
            seguir = 0;
    }
    return otraPuerta;
}

int main (int argc, const char * argv[]) {
    printf("Puertas\n");
    int contenido[CANT_PUERTAS];
    int puertaElegida;
    int puertaAbierta;
    int cantPremios = 0;
   
    for (int i = 0; i < ITERACIONES; i++) {
        cargaPremio(contenido);
        puertaElegida = eligePuerta();
        puertaAbierta = abreOtraPuerta(puertaElegida, contenido);
        cantPremios += contenido[puertaElegida];
    }
   
    double resultado = cantPremios * 100.0 / ITERACIONES;
    printf("%f1.2 ", resultado);

    return 0;
}
Nótese que ni siquiera se necesita correrlo para ver la solución. En cada iteración de la simulación (líneas pintadas de rojo), se hace lo siguiente:
  1. se sortea en que puerta está el premio
  2. se elige una puerta al azar
  3. se abre una puerta que no es la elegida ni tiene premio
  4. se acumula la cantidad de veces que acertó
El tema es que la puerta abierta por el conductor del programa no entra en juego para nada. La cantidad de veces que acierto (si me quedo con la puerta original) es la cantidad de veces que hubiera acertado con las tres puertas cerradas...

Por lo tanto, si tenemos que al no cambiar gano 1/3 de las veces, entonces si cambio debo ganar 2/3 de las veces.

Efectivamente al correr la simulación el resultado que se obtiene es que si no se cambia de puerta se gana solo el 33% de las veces.

10 comentarios:

  1. Muy interesante hacer un algoritmo para comprender un problema... yo suelo hacerlo seguido pero en RUBY!!!

    Tu observación es aguda y es la clave de todo, realmente no hace falta correr el programa al observar que si no cambia de decision los aciertos son muchos menos (en realidad no hacia falta ni escribir el programa, pero eso es otra historia).

    Para jugar un rato le dedique un par de minutos e implemente tu algoritmo en Ruby (por claridad).

    Trate de ser lo mas fiel posible, el único cambie es que elimine el vector porque no era necesario, lo usabas para guardar la posición del premio, es mas directo tenerlo explícito un variable.


    Repetir = 1_000_000
    Puertas = 3

    aciertos = 0
    for i in 1..Repetir
    premio = rand(Puertas)
    elegida = rand(Puertas)
    mostrar = rand(Puertas) while mostrar != elegida && mostrar != premio
    aciertos += 1 if elegida==premio
    end

    puts "#{Puertas} Puertas => #{100 * aciertos / Repetir}% aciertos"


    Hay varias cosas interesantes que podemos aprender de este pequeño juego.

    1) Somos un tipos muy extraños, en lugar de pensar un rato le dedicamos mucho mas tiempo en hacer algo mucho mas complicado.

    2) Ruby es mucho mas compacto y claro que C(al menos para mi).

    3) El rendimiento del lenguaje no importa para un proceso que se corre un sola vez. Aunque Ruby fuera 100 veces mas lento que C bastaba con correrlo tan solos 10.000 veces para que demoren lo mismo sin perder para nada significación estadística.

    4) Tenemos una compulsion por optimizar aun cuando no sea en absoluto necesario ya que el algoritmo corrió en menos de 2 segundos en mi MacBookPro. (vos lo has hecho en C, yo elimine el vector)

    5) La burocracia de C me resulta insoportable (y hace que casi no pueda leer el programa)

    ResponderEliminar
  2. Alejandro:

    >en realidad no hacia falta ni escribir el programa, pero eso es otra historia

    Es verdad... pero de la otra forma no me quedaba claro.

    >el único cambie es que elimine el vector porque no era necesario, lo usabas para guardar la posición del premio, es mas directo tenerlo explícito un variable

    Es verdad, ahora que lo decís, no era necesario. Era una representación más fiel al problema nomás.

    >1) Somos un tipos muy extraños

    Totalmente de acuerdo, pero eso ya lo sabía :)

    >2) Ruby es mucho mas compacto y claro que C

    En C se puede hacer más compacto, pero no siempre más compacto quiere decir mejor o más claro...
    Me gustó igual de Ruby eso que hacés de "mostrar = rand(Puertas) while mostrar != elegida && mostrar != premio"

    >3) El rendimiento del lenguaje no importa para un proceso que se corre un sola vez

    También es cierto...

    >5) La burocracia de C me resulta insoportable (y hace que casi no pueda leer el programa)

    Esa debe ser la ventaja entonces de no saber Ruby :) A mi no me molesta tener que definir las variables. Las funciones en realidad no eran necesarias, pero como primero escribí el loop, parecía lo más natural.
    Para un programa que corre una sola vez está claro que no precisa hacer todo eso.

    ResponderEliminar
  3. La verdad que son extraños, jejeje

    ResponderEliminar
  4. Jaja. Geek, sí, y a mucha honra.

    ResponderEliminar
  5. Hola amigo, estoy intentando correr el codigo en Turbo c++, y me ha dado una serie de errores, que compilador me recomiendas para correr el codigo???

    ResponderEliminar
  6. sourmijo:

    Yo lo compilé con GCC, pero pienso que cualquier compilador de C estándar debería servir... Es un programa muy sencillo para que de problemas de compilación.

    ResponderEliminar
  7. Gracias use el programa que me recomendo y funciono, pero el error que me mostraba con el Turb C++ 4.5 y el Dev-C++ era el siguiente

    'for' loop initial declaration used outside C99 mode

    lo cual solucione declarando la variable "i" fuera de los dos For que usas... pero igual muchas gracias por recomendarme el GCC

    ResponderEliminar
  8. hola disculpa el abuso, pero me podrias decir que cambios o agregados se le deberia hacer al codigo para que me muestre todas las interacciones es decir, el proseso tu lo pones a repetir 100.000, y como podria hacer para que me muestre en cada repeticion el nuemero de la puerta con el premio, la puerta seleccionada por el concursante y la puerta que se cambia si es que hay cambio...

    de antemano gracias y disculpa la molestia

    ResponderEliminar
  9. sourmijo:

    En el "for (int i = 0; i < ITERACIONES; i++)", deberías poner el printf correspondiente, mostrando las variables puertaElegida, puertaAbierta y contenido[puertaElegida]

    ResponderEliminar