Rompecabezas C: hacer una moneda justa de una moneda sesgada

algorithm math

Question

¿Cómo puedo determinar la probabilidad de que una función devuelva 0 o 1 en el siguiente caso:

Deje que la function_A devuelva 0 con probabilidad 40% y 1 con probabilidad 60%. Genere una function_B con probabilidades 50-50 usando solo function_A solamente.

Pensé en lo siguiente:

 function_B()
 {
     int result1=function_A();
     int result2=function_A();
     //two times 40% would result in 16% and 40%+60% would be 24%... two times 60%                        would be 36%
 }

¿Qué combinación podría dar 50-50?

Answer 1

Aquí hay un enfoque que funcionará, pero requiere una prueba repetida.

1. la posibilidad de que function_A devuelva 1: P (1) = p (por ejemplo, p = 60%)
2. la posibilidad de que function_A devuelva 0: P (0) = 1 - p
3. la posibilidad de una secuencia específica de valores de retorno a, b, ... en llamadas sucesivas a function_A es P (a) P (b) ...

4. Observar ciertas combinaciones surgirán con probabilidades iguales, por ejemplo:

         P(a)*P(b) === P(b)*P(a)
    P(a)*P(b)*P(c) === P(b)*P(c)*P(a)
   
    etc.

5. Podemos usar ese hecho cuando seleccionamos solo secuencias de (1,0) o (0,1), luego sabemos que la posibilidad de cualquiera de ellas es

       P(1)*P(0)/(P(1)*P(0) + P(0)*P(1)) 
    => x / (x + x)
    => 1 / 2

Esto, entonces, se convierte en la receta para implementar una function_B:

• call function_A repetidamente hasta que recibamos una secuencia de (0,1) o (1,0)
• siempre devolvemos el primer o el último elemento de la secuencia (ambos tendrán la misma probabilidad de ser 0 o 1)

function_B()
{
    do
    {
        int a = function_A();
        int b = function_A();
    } while( (a ^ b) == 0 ); // until a != b

    return a;
}

Answer 2

Este es un rompecabezas de probabilidad clásico y, según mi conocimiento, no puede hacerlo con solo dos llamadas a la función. Sin embargo, puede hacer esto con un bajo número esperado de llamadas a la función.

La observación es que si tienes una moneda sesgada que aparece cara a cara con probabilidad p, y si la giras dos veces, entonces:

• La probabilidad de que salga cara dos veces es p ^2.
• La probabilidad de que salga cara primero y segundo es p (1-p)
• La probabilidad de que salga de las colas primero y de que salga la segunda es (1-p) p
• La probabilidad de que salga colas dos veces es (1-p) ²

Ahora, supongamos que volteas repetidamente dos monedas hasta que encuentren valores diferentes. Si esto sucede, ¿cuál es la probabilidad de que la primera moneda salga cara? Bueno, si aplicamos la ley de Bayes, tenemos que

P (la primera moneda es cara | ambas monedas son diferentes) = P (ambas monedas son diferentes | la primera moneda es cara) P (la primera moneda es cara) / P (ambas monedas son diferentes)

La probabilidad de que la primera moneda sea cara es p, ya que cualquier lanzamiento de moneda aparece cara a cara con probabilidad p. La probabilidad de que ambas monedas sean diferentes dado que la primera moneda es cara es la probabilidad de que la segunda moneda saliera de la cola, que es (1 - p). Finalmente, la probabilidad de que ambas monedas sean diferentes es 2p (1-p), ya que si observa la tabla de probabilidad de arriba, esto puede suceder de dos maneras, cada una de las cuales tiene una probabilidad p (1-p). Simplificando, tenemos que

P (la primera moneda es cara | ambas monedas son diferentes) = p (1-p) / (2p (1-p)) = 1/2.

¿Pero esa es la probabilidad de que la primera moneda salga de cola si las monedas son diferentes? Bueno, es lo mismo que la probabilidad de que la primera moneda no salga cara cuando ambas monedas son diferentes, que es 1 - 1/2 = 1/2.

En otras palabras, si sigues lanzando dos monedas hasta que tengan diferentes valores, luego tomas el valor de la primera moneda que lanzas, ¡terminas haciendo una moneda justa a partir de una moneda sesgada!

En C, esto podría verse así:

bool FairCoinFromBiasedCoin() {
    bool coin1, coin2;

    do {
        coin1 = function_A();
        coin2 = function_A();
    } while (coin1 == coin2);

    return coin1;
}

Esto puede parecer muy ineficiente, pero en realidad no es tan malo. La probabilidad de que termine en cada iteración es 2p (1 - p). En espera, esto significa que necesitamos 1 / (2p (1-p)) iteraciones antes de que termine este bucle. Para p = 40%, esto es 1 / (2 x 0.4 x 0.6) = 1 / 0.48 ~ = 2.083 iteraciones. Cada iteración lanza dos monedas, por lo que necesitamos, en la expectativa, alrededor de 4.16 tiradas de monedas para obtener una tirada justa.

¡Espero que esto ayude!

Answer 3

Me pregunté si algo recursivo debería funcionar, a medida que aumenta la profundidad, la probabilidad de 0 o 1 debería estar más cerca y más cerca de 0.5. En 1 nivel, la probabilidad modificada es p ''= p * p + (p-1) * (p-1)

depth = 10;
int coin(depth) {
    if (depth == 0) {
        return function_A();
    }
    p1 = coin(depth-1);
    p2 = coin(depth-1);
    if (p1 == p2) {
        return 1;
    } else {
        return 0;
    }
}

Answer 4

Realizable. Sin embargo, 2 llamadas a esas funciones no serán suficientes. Piense en llamar a la función una y otra vez y acercarse cada vez más a 50/50

Answer 5

Dado:

1. Eventos = {cabeza, cola}
2. la moneda es injusta => P (cabeza) = p y P (cola) = 1-p

Algoritmo:

1. Genera una muestra de eventos N1 (cabeza o cola) usando la moneda injusta
2. estimar su media muestral m1 = (#heads) / N1
3. Genera otra muestra de eventos N2 (caras o colas) usando las monedas injustas
4. estimar su media muestral m2 = (#heads) / N2
5. si (m1> m2) devuelve la cabeza o devuelve la cola

Notas:

1. Los eventos devueltos en el paso # 5 anterior son igualmente probables (P (cabeza) = P (cola) = 0.5)
2. Si el # 5 se repite muchas veces, entonces su media muestral -> 0.5 independientemente de p
3. Si N1 -> infinito, entonces m1 -> verdadera media p
4. Para generar una salida de moneda justa, necesita muchos muestreos independientes (aquí lanzamientos) de la moneda injusta. Mientras más, mejor.

Intuición: aunque la moneda es injusta, la desviación de la media estimada alrededor de la media verdadera es aleatoria y podría ser positiva o negativa con igual probabilidad. Como no se da la media verdadera, esto se estima a partir de otra muestra.

Answer 6

def fairCoin(biasedCoin):
coin1, coin2 = 0,0
while coin1 == coin2:
coin1, coin2 = biasedCoin(), biasedCoin()
return coin1

Esta fue originalmente la idea inteligente de von Neumann. Si tenemos una moneda sesgada (es decir, una moneda que sale cara con probabilidad diferente de 1/2), podemos simular una moneda justa lanzando pares de monedas hasta que los dos resultados sean diferentes. Dado que tenemos resultados diferentes, la probabilidad de que la primera sea "cabezas" y la segunda "colas" es la misma que la probabilidad de "colas" y luego "cabezas". Entonces, si simplemente devolvemos el valor de la primera moneda, obtendremos "caras" o "colas" con la misma probabilidad, es decir, 1 / 2.Esta respuesta es de - http://jeremykun.com/2014/02/08/simulating-a-fair-coin-with-a-biased-coin/ lea más sobre esto en http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin