Вопрос интервью: о вероятности

Question

Вопрос для интервью:

Учитывая функцию f (x), которая 1/4 раза возвращает 0, 3/4 раза возвращает 1. Напишите функцию g (x), используя f (x), которая 1/2 раза возвращает 0, 1/2 раза возвращает 1.

Моя реализация:

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)
            }       
    }
}

Я прав? Каково ваше решение? (Вы можете использовать любой язык)

Answer 1

Если вы вызываете f (x) дважды подряд, возможны следующие результаты (при условии, что последовательные вызовы f (x) являются независимыми, идентично распределенными испытаниями):

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 и 10 происходят с равной вероятностью. Так итерируйте, пока не получите один из тех случаи, затем верните 0 или 1 соответственно:

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

return a;

Может быть заманчиво вызывать f (x) только один раз за итерацию и отслеживать два самые последние значения, но это не сработает. Предположим, самый первый бросок равен 1, с вероятностью 3/4. Вы зациклились бы до первого 0, а затем вернули 1 (с вероятностью 3/4).

Answer 2

Проблема вашего алгоритма в том, что он повторяется с высокой вероятностью. Мой код:

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
}

Я измерял среднее число раз, f(x) было рассчитано для вашего алгоритма и для моего. Для вас f(x) было рассчитано примерно в 5,3 раза за один g(x) расчет. С моим алгоритмом это число уменьшилось до 3,5. То же самое относится и к другим ответам до сих пор, так как они на самом деле тот же алгоритм, как вы сказали.

P.S .: Ваше определение не упоминает «случайное» в данный момент, но, вероятно, оно предполагается. Смотрите мой другой ответ.

Answer 3

Ваше решение правильное, если несколько неэффективное и с более продублированной логикой. Вот реализация Python того же алгоритма в более чистой форме.

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

Если f () дорого, вы захотите получить более изощренную информацию об использовании совпадений / несоответствий, чтобы попытаться вернуться с меньшим количеством вызовов. Вот наиболее эффективное из возможных решений.

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

В среднем требуется около 2,6 звонков на g().

Вот как это работает. Мы пытаемся выбрать случайное число от 0 до 1, но мы останавливаемся, как только мы узнаем, является ли число 0 или 1. Мы начинаем знать, что число находится в интервале (0, 1). 3/4 чисел находятся в нижней части 3/4 интервала, а 1/4 - в верхней 1/4 интервала. Мы решаем, на основании какого звонка f(x). Это означает, что мы сейчас находимся в меньшем интервале.

Если мы будем мыть, полоскать и повторять достаточное количество раз, мы сможем определить наше конечное число как можно точнее, и у нас будет абсолютно равная вероятность попадания в любую область исходного интервала. В частности, мы имеем равную вероятность того, что она будет больше или меньше 0,5.

Если бы вы хотели, вы могли бы повторить идею генерировать бесконечный поток битов один за другим. Фактически, это, несомненно, самый эффективный способ генерации такого потока и источник идеи энтропии в теории информации.

Answer 4

Уточнение того же подхода, который использовался в ответе btilly, с достижением в среднем ~ 1,85 вызовов для f() на g() результата (дальнейшее уточнение, документированное ниже, достигает ~ 1,75, тбилли ~ 2,6, принятый ответ Джима Льюиса ~ 5.33).Код отображается ниже в ответе.

По сути, я генерирую случайные целые числа в диапазоне от 0 до 3 с четной вероятностью: вызывающий может затем проверить бит 0 для первого значения 50/50 и бит 1 для второго,Причина: f() вероятности 1/4 и 3/4 отображаются на четверти гораздо более чётко, чем на половинки.

---

Описание алгоритма

btilly объяснил алгоритм, но я 'Я тоже сделаю это по-своему ...

Алгоритм в основном генерирует случайное действительное число x между 0 и 1, а затем возвращает результат в зависимости от того, какой "контейнер результатов"это число попадает в число:

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

Но генерировать случайное действительное число, заданное только f(), сложно.Мы должны начать с знания, что наше значение x должно быть в диапазоне 0..1 - которое мы назовем нашим начальным «возможным x» пространством.Затем мы оттачиваем фактическое значение для x:

• каждый раз, когда мы вызываем f():
  
  • , если f() возвращает 0 (вероятность 1 в 4), мы считаем x находящимся в нижней четверти пространства «возможного x», и исключаем три верхних четверти из этого пространства
  • , если f() возвращает 1 (вероятность 3 в 4), мысчитать, что x находится в верхних трех четвертях пространства «возможного x», и исключить нижнюю четверть из этого пространства
  • , когда пространство «возможного x» полностью содержится в одном контейнере результатов,это означает, что мы сузили x до точки, где мы знаем, к какому результату результата он должен соответствовать, и нам не нужно получать более конкретное значение для x.

Это может или не может помочь рассмотреть эту диаграмму: -):

    "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

---

Код

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;                               
    }                                                                           
}

Если полезно, посредник выдает 50/50результаты по одному:

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;
    }
}

ПРИМЕЧАНИЕ. Это можно дополнительно настроить, включив алгоритм.от рассмотрения результата f () == 0, который нужно отточить в нижней четверти, до того, чтобы вместо этого отразить его в верхней четверти, на основе которого в среднем происходит быстрое преобразование в корзину результатов.Внешне это казалось полезным при третьем вызове f (), когда результат в верхней четверти будет указывать на немедленный результат 3, в то время как результат в нижней четверти все еще охватывает точку вероятности 0,5 и, следовательно, результаты 1 и 2. Когда я попробовал это,результаты были на самом деле хуже.Чтобы увидеть реальные преимущества, потребовалась более сложная настройка, и я закончил тем, что написал грубое сравнение нижнего и верхнего предельных значений для второго-одиннадцатого вызовов функции g ().Наилучший результат, который я нашел, был в среднем ~ 1,75 в результате 1-го, 2-го, 5-го и 8-го вызовов функции g (), стремящихся к низкому значению (т. Е. Установив low = cutoff).

Answer 5

Как уже упоминалось, ваше определение не так уж хорошо в отношении вероятности. Обычно это означает, что хороша не только вероятность, но и distribution. В противном случае вы можете просто написать g (x), который вернет 1,0,1,0,1,0,1,0 - он вернет их 50/50, но числа не будут случайными.

Другой способ обмана может быть:

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

Это решение будет лучше всех остальных, так как оно вызывает f(x) только один раз. Но результаты не будут очень случайными.

Answer 6

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

Если принять это утверждение буквально, то f (x) при вызове четыре раза всегда будет возвращать ноль один раз и 1 3 раза.Это отличается от того, что f (x) является вероятностной функцией, и отношение 0: 1 будет приближаться к 1 к 3 (1/4 против 3/4) на многих итерациях.Если первая интерпретация верна, то единственной действительной функцией для f (x), которая будет соответствовать критериям, независимо от того, откуда в последовательности вы начинаете, является последовательность 0111, повторяющаяся.(или 1011, или 1101, или 1110, которые представляют собой одну и ту же последовательность из другой начальной точки).Учитывая это ограничение,

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

должно быть достаточно.

Answer 7

Вот решение, основанное на центральной предельной теореме, изначально принадлежащее моему другу:

/*
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 8

Это очень похоже на парадокс Монти Холла.

В общем.

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 9

Предполагая

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

и требует функции g[x] со следующими допущениями

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

Я считаю, что достаточно следующего определения g[x] (Mathematica)

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

или, альтернативно, в C

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

Это основано на идее, что вызовы {f[x], f[x+1]} приведут к следующим результатам

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

Суммируя каждый из полученных нами результатов

{
  0,
  1,
  1,
  2
}

, где сумма 1 представляет половину возможных итоговых сумм, а любая другая сумма составляет 1/2.

Edit. Как говорит БДК - {0,0} менее вероятно, чем {1,1}, потому что

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

Однако я запутался, потому что получил следующее определение для f[x] (Mathematica)

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

или в качестве альтернативы в C

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

тогда результаты, полученные при выполнении f[x] и g[x], похоже, имеют ожидаемое распределение.

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 10

Поскольку каждое возвращение f () представляет 3/4 шанса TRUE, с некоторой алгеброй мы можем просто правильно сбалансировать шансы.Нам нужна еще одна функция x (), которая возвращает балансирующую вероятность TRUE, так что

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

возвращает true в 50% случаев.

Итак, давайте найдем вероятность x (p (x)), учитывая p (f) и нашу желаемую общую вероятность (1/2):

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

Таким образом, x () должен возвращать TRUE с вероятностью 2/3, так как 2/3* 3/4 ​​= 6/12 = 1/2;

Таким образом, для g () должно работать следующее:

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