algorithm - significa - preguntas estadisticas ejemplos

Una pregunta de la entrevista: acerca de la probabilidad

Question

Una pregunta de entrevista:

Dada una función f (x) que 1/4 veces devuelve 0, 3/4 veces devuelve 1. Escribe una función g (x) usando f (x) que 1/2 veces devuelve 0, 1/2 veces devuelve 1.

Mi implementación es:

function g(x) = {
if (f(x) == 0){ // 1/4
var s = f(x)
if( s == 1) {// 3/4 * 1/4
return s // 3/16
} else {
g(x)
}
} else { // 3/4
var k = f(x)
if( k == 0) {// 1/4 * 3/4
return k // 3/16
} else {
g(x)
}
}
}

¿Estoy en lo cierto? ¿Cuál es su solución? (Puede usar cualquier idioma)

Answer 1

Aquí hay una solución basada en el teorema del límite central, originalmente debido a un amigo mío:

/*
Given a function f(x) that 1/4 times returns 0, 3/4 times returns 1. Write a function g(x) using f(x) that 1/2 times returns 0, 1/2 times returns 1.
*/
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstdio>
using namespace std;
int f() {
if (rand() % 4 == 0) return 0;
return 1;
}
int main() {
srand(time(0));
int cc = 0;
for (int k = 0; k < 1000; k++) { //number of different runs
int c = 0;
int limit = 10000; //the bigger the limit, the more we will approach %50 percent
for (int i=0; i<limit; ++i) c+= f();
cc += c < limit*0.75 ? 0 : 1; // c will be 0, with probability %50
}
printf("%d/n",cc); //cc is gonna be around 500
return 0;
}

Answer 2

Asumiendo

P(f[x] == 0) = 1/4
P(f[x] == 1) = 3/4

y que requiere una función g[x] con las siguientes suposiciones

P(g[x] == 0) = 1/2
P(g[x] == 1) = 1/2

Creo que la siguiente definición de g[x] es suficiente (Mathematica)

g[x_] := If[f[x] + f[x + 1] == 1, 1, 0]

o, alternativamente, en C

int g(int x)
{
return f(x) + f(x+1) == 1
? 1
: 0;
}

Esto se basa en la idea de que las invocaciones de {f[x], f[x+1]} producirían los siguientes resultados

{
{0, 0},
{0, 1},
{1, 0},
{1, 1}
}

Sumando cada uno de los resultados que tenemos

{
0,
1,
1,
2
}

donde una suma de 1 representa 1/2 de los posibles resultados de suma, con cualquier otra suma que compone el otro 1/2.

Editar. Como dice bdk, {0,0} es menos probable que {1,1} porque

1/4 * 1/4 < 3/4 * 3/4

Sin embargo, estoy confundido porque dada la siguiente definición para f[x] (Mathematica)

f[x_] := Mod[x, 4] > 0 /. {False -> 0, True -> 1}

o alternativamente en C

int f(int x)
{
return (x % 4) > 0
? 1
: 0;
}

entonces los resultados obtenidos al ejecutar f[x] g[x] parecen tener la distribución esperada.

Table[f[x], {x, 0, 20}]
{0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0}
Table[g[x], {x, 0, 20}]
{1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1}

Answer 3

Como cada devolución de f () representa una probabilidad de 3/4 de VERDADERO, con algo de álgebra podemos equilibrar las probabilidades. Lo que queremos es otra función x () que devuelva una probabilidad de equilibrio de TRUE, de modo que

function g() {
return f() && x();
}

devuelve verdadero el 50% del tiempo.

Entonces, busquemos la probabilidad de x (p (x)), dado p (f) y nuestra probabilidad total deseada (1/2):

p(f) * p(x) = 1/2
3/4 * p(x) = 1/2
p(x) = (1/2) / 3/4
p(x) = 2/3

Entonces x () debería devolver VERDADERO con una probabilidad de 2/3, ya que 2/3 * 3/4 ​​= 6/12 = 1/2;

Por lo tanto, lo siguiente debería funcionar para g ():

function g() {
return f() && (rand() < 2/3);
}

Answer 4

Como ya mencioné, su definición no es tan buena con respecto a la probabilidad. Por lo general, significa que no solo la probabilidad es buena sino también la distribution . De lo contrario, simplemente puede escribir g (x) que devolverá 1,0,1,0,1,0,1,0 - los devolverá 50/50, pero los números no serán aleatorios.

Otro enfoque de engaño podría ser:

var invert = false;
function g(x) {
invert = !invert;
if (invert) return 1-f(x);
return f(x);
}

Esta solución será mejor que todas las demás ya que llama a f(x) solo una vez. Pero los resultados no serán muy aleatorios.

Answer 5

El problema con su algoritmo es que se repite con alta probabilidad. Mi código:

function g(x) = {
var s = f(x) + f(x) + f(x);
// s = 0, probability: 1/64
// s = 1, probability: 9/64
// s = 2, probability: 27/64
// s = 3, probability: 27/64
if (s == 2) return 0;
if (s == 3) return 1;
return g(x); // probability to go into recursion = 10/64, with only 1 additional f(x) calculation
}

He medido el número promedio de veces que f(x) se calculó para su algoritmo y para el mío. Para el tuyo, f(x) se calculó alrededor de 5,3 veces por un cálculo de g(x) . Con mi algoritmo, este número se reduce a alrededor de 3.5. Lo mismo es cierto para otras respuestas hasta ahora ya que en realidad son el mismo algoritmo que usted dijo.

PD: su definición no menciona ''aleatorio'' en este momento, pero probablemente se asume. Ver mi otra respuesta.

Answer 6

Esto es muy parecido a la paradoja de Monty Hall.

En general.

Public Class Form1
''the general case
''
''twiceThis = 2 is 1 in four chance of 0
''twiceThis = 3 is 1 in six chance of 0
''
''twiceThis = x is 1 in 2x chance of 0
Const twiceThis As Integer = 7
Const numOf As Integer = twiceThis * 2
Private Sub Button1_Click(ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles Button1.Click
Const tries As Integer = 1000
y = New List(Of Integer)
Dim ct0 As Integer = 0
Dim ct1 As Integer = 0
Debug.WriteLine("")
''''show all possible values of fx
''For x As Integer = 1 To numOf
'' Debug.WriteLine(fx)
''Next
''test that gx returns 50% 0''s and 50% 1''s
Dim stpw As New Stopwatch
stpw.Start()
For x As Integer = 1 To tries
Dim g_x As Integer = gx()
''Debug.WriteLine(g_x.ToString) ''used to verify that gx returns 0 or 1 randomly
If g_x = 0 Then ct0 += 1 Else ct1 += 1
Next
stpw.Stop()
''the results
Debug.WriteLine((ct0 / tries).ToString("p1"))
Debug.WriteLine((ct1 / tries).ToString("p1"))
Debug.WriteLine((stpw.ElapsedTicks / tries).ToString("n0"))
End Sub
Dim prng As New Random
Dim y As New List(Of Integer)
Private Function fx() As Integer
''1 in numOf chance of zero being returned
If y.Count = 0 Then
''reload y
y.Add(0) ''fx has only one zero value
Do
y.Add(1) ''the rest are ones
Loop While y.Count < numOf
End If
''return a random value
Dim idx As Integer = prng.Next(y.Count)
Dim rv As Integer = y(idx)
y.RemoveAt(idx) ''remove the value selected
Return rv
End Function
Private Function gx() As Integer
''a function g(x) using f(x) that 50% of the time returns 0
'' that 50% of the time returns 1
Dim rv As Integer = 0
For x As Integer = 1 To twiceThis
fx()
Next
For x As Integer = 1 To twiceThis
rv += fx()
Next
If rv = twiceThis Then Return 1 Else Return 0
End Function
End Class

Answer 7

Si llama a f (x) dos veces seguidas, los siguientes resultados son posibles (suponiendo que las llamadas sucesivas a f (x) son ensayos independientes, distribuidos de forma idéntica):

00 (probability 1/4 * 1/4)
01 (probability 1/4 * 3/4)
10 (probability 3/4 * 1/4)
11 (probability 3/4 * 3/4)

01 y 10 ocurren con la misma probabilidad. Así que itere hasta que obtenga uno de esos casos, luego devuelva 0 o 1 apropiadamente:

do
a=f(x); b=f(x);
while (a == b);
return a;

Puede ser tentador llamar a f (x) solo una vez por iteración y hacer un seguimiento de los dos valores más recientes, pero eso no funcionará. Supongamos que la primera tirada es 1, con probabilidad 3/4. Harías un bucle hasta el primer 0, luego regresas 1 (con probabilidad 3/4).

Answer 8

Su solución es correcta, aunque algo ineficaz y con más lógica duplicada. Aquí hay una implementación de Python del mismo algoritmo en una forma más limpia.

def g ():
while True:
a = f()
if a != f():
return a

Si f () es costoso, querrá ser más sofisticado con el uso de la información de coincidencia / falta de coincidencia para intentar regresar con menos llamadas. Aquí está la solución más eficiente posible.

def g ():
lower = 0.0
upper = 1.0
while True:
if 0.5 < lower:
return 1
elif upper < 0.5:
return 0
else:
middle = 0.25 * lower + 0.75 * upper
if 0 == f():
lower = middle
else:
upper = middle

Esto requiere alrededor de 2.6 llamadas a g() en promedio.

La forma en que funciona es esto. Estamos tratando de elegir un número aleatorio de 0 a 1, pero nos detenemos tan pronto como sabemos si el número es 0 o 1. Comenzamos a saber que el número está en el intervalo (0, 1). 3/4 de los números están en la parte inferior 3/4 del intervalo, y 1/4 están en el 1/4 superior del intervalo. Decidimos cuál basado en una llamada a f(x) . Esto significa que ahora estamos en un intervalo más pequeño.

Si nos lavamos, enjuagamos y repetimos suficientes veces podemos determinar nuestro número finito de la manera más precisa posible, y tendremos la misma probabilidad de terminar en cualquier región del intervalo original. En particular, tenemos una probabilidad incluso de liquidación superior o inferior a 0,5.

Si quisieras, podrías repetir la idea para generar una secuencia interminable de bits uno por uno. Esta es, de hecho, probablemente la forma más eficiente de generar tal flujo, y es la fuente de la idea de entropía en la teoría de la información.

Answer 9

Un refinamiento del mismo enfoque usado en la respuesta de Btilly, logrando un promedio de ~ 1.85 llamadas a f() por g() resultado (refinamiento adicional documentado a continuación alcanza ~ 1.75, tbilly ~ 2.6, respuesta aceptada por Jim Lewis ~ 5.33). El código aparece más abajo en la respuesta.

Básicamente, genero enteros aleatorios en el rango de 0 a 3 con probabilidad par: la persona que llama puede probar el bit 0 para el primer valor 50/50 y el bit 1 para un segundo. Motivo: las probabilidades f() de 1/4 y 3/4 se asignan a los trimestres mucho más limpiamente que las mitades.

Descripción del algoritmo

Biltly explicó el algoritmo, pero lo haré a mi manera también ...

El algoritmo básicamente genera un número real aleatorio x entre 0 y 1, luego devuelve un resultado según el "cubo de resultados" en que se encuentra ese número:

result bucket result
x < 0.25 0
0.25 <= x < 0.5 1
0.5 <= x < 0.75 2
0.75 <= x 3

Pero, generar un número real aleatorio dado solo f() es difícil. Tenemos que comenzar con el conocimiento de que nuestro valor x debe estar en el rango 0..1 - que llamaremos nuestro espacio inicial "posible x". Luego nos enfocamos en un valor real para x :

• cada vez que llamamos f() :
  
  • si f() devuelve 0 (probabilidad 1 en 4), consideramos que x está en el cuarto inferior del espacio "x posible" y eliminamos los tres cuartos superiores de ese espacio
  • si f() devuelve 1 (probabilidad 3 en 4), consideramos que x está en los tres cuartos superiores del espacio de "x posible", y eliminamos el cuarto inferior de ese espacio
  • cuando el espacio de "posible x" está completamente contenido por un solo cubo de resultados, eso significa que hemos reducido x hasta el punto donde sabemos a qué valor de resultado debe asignarse y no es necesario obtener un valor más específico para x .

Puede o no ayudar a considerar este diagrama :-):

 "result bucket" cut-offs 0,.25,.5,.75,1
0=========0.25=========0.5==========0.75=========1 "possible x" 0..1
| | . . | f() chooses x < vs >= 0.25
| result 0 |------0.4375-------------+----------| "possible x" .25..1
| | result 1| . . | f() chooses x < vs >= 0.4375
| | | . ~0.58 . | "possible x" .4375..1
| | | . | . | f() chooses < vs >= ~.58
| | ||. | | . | 4 distinct "possible x" ranges

Código

int g() // return 0, 1, 2, or 3
{
if (f() == 0) return 0;
if (f() == 0) return 1;
double low = 0.25 + 0.25 * (1.0 - 0.25);
double high = 1.0;
while (true)
{
double cutoff = low + 0.25 * (high - low);
if (f() == 0)
high = cutoff;
else
low = cutoff;
if (high < 0.50) return 1;
if (low >= 0.75) return 3;
if (low >= 0.50 && high < 0.75) return 2;
}
}

Si es útil, un intermediario para enviar 50/50 resultados de uno en uno:

int h()
{
static int i;
if (!i)
{
int x = g();
i = x | 4;
return x & 1;
}
else
{
int x = i & 2;
i = 0;
return x ? 1 : 0;
}
}

NOTA: Esto puede modificarse aún más haciendo que el cambio de algoritmo no considere un resultado f () == 0 para afinar el cuarto inferior, sino que tenga un enfoque en el cuarto superior, en función del cual en promedio se resuelve en un resultado balde más rápido. Superficialmente, esto pareció útil en la tercera llamada a f () cuando un resultado en el cuarto superior indica un resultado inmediato de 3, mientras que un resultado en el cuarto inferior aún abarca el punto de probabilidad 0.5 y por lo tanto los resultados 1 y 2. Cuando lo intenté, los resultados fueron en realidad peores. Se necesitaba una sintonización más compleja para ver los beneficios reales, y terminé escribiendo una comparación de fuerza bruta de corte inferior versus superior para llamadas de segundo a undécimo a g (). El mejor resultado que encontré fue un promedio de ~ 1.75, como resultado de la primera, segunda, quinta y octava llamadas a g () buscando bajo (es decir, ajuste low = cutoff ).

Answer 10

Given a function f(x) that 1/4 times returns 0, 3/4 times returns 1

Tomando esta declaración literalmente, f (x) si se llama cuatro veces, siempre regresará a cero una vez y a 1 3 veces. Esto es diferente a decir que f (x) es una función probabalística y la relación de 0 a 1 se acercará a 1 a 3 (1/4 frente a 3/4) en muchas iteraciones. Si la primera interpretación es válida, entonces la única función válida para f (x) que cumplirá los criterios, independientemente de en qué parte de la secuencia empiece, es la secuencia 0111 que se repite. (o 1011 o 1101 u 1110 que son la misma secuencia desde un punto de partida diferente). Dada esa restricción,

 g()= (f() == f())

debería ser suficiente.