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

Ответ 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).

Ответ 2

Ваше решение правильное, если оно несколько неэффективно и с более продуманной логикой. Вот реализация 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.

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

Ответ 3

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

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.: ваше определение на данный момент не упоминает "случайный", но, вероятно, предполагается. См. Мой другой ответ.

Ответ 4

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

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

Ответ 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) только один раз. Но результаты не будут очень случайными.

Ответ 6

Уточнение того же подхода, что и в btilly-ответе, достижение среднего значения 1.85 на f() за g() результат (дальнейшее уточнение, приведенное ниже, достигает ~ 1.75, tbilly ~ 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).

Ответ 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;
}

Ответ 8

Так как каждое возвращение 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);
}

Ответ 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 возможных результатов суммы, причем любая другая сумма составляет вторую 1/2.

Изменить. Как говорит bdk - {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}

Ответ 10

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

В общем.

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