面试问题：关于概率

Question

一道面试题：

给定一个函数 f(x)，1/4 次返回 0，3/4 次返回 1。 用f(x)写一个函数g(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)，每次 g(x) 计算大约会计算 5.3 次。根据我的算法，这个数字减少到 3.5 左右。到目前为止，其他答案也是如此，因为它们实际上与您所说的算法相同。

PS：您的定义目前没有提到“随机”，但可能是假设的。请参阅我的另一个答案。

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

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

从字面意思来看，f(x) 如果调用四次，将始终返回 0 一次和 1 3 次。这与 f(x) 是概率函数不同，并且在多次迭代中 0 比 1 的比率将接近 1 比 3（1/4 与 3/4）。如果第一个解释有效，那么无论您从序列中的哪个位置开始，满足条件的 f(x) 唯一有效函数就是序列 0111 重复。 （或者1011或1101或1110，它们是来自不同起点的相同序列）。考虑到这个限制，

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

应该足够了。

Answer 5

正如已经提到的，你的定义对于概率来说并不是那么好。通常，这不仅意味着概率好，而且分布也好。否则，您可以简单地编写 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

对 btilly 的答案中使用的相同方法进行了改进，每个 g() 结果平均实现了约 1.85 次对 f() 的调用（下面记录的进一步改进实现了约 1.75，tbilly 的~2.6，吉姆刘易斯接受的答案~5.33）。代码出现在答案的下方。

基本上，我以偶数概率生成 0 到 3 范围内的随机整数：然后调用者可以测试第 0 位的第一个 50/50 值，并测试第二位的位 1。原因：1/4 和 3/4 的 f() 概率映射到四分之一比一半更清晰。

---

算法描述

btilly 解释了该算法，但我也会以自己的方式这样做...

该算法基本上生成一个介于 0 和 1 之间的随机实数数字x，然后根据该数字所属的“结果桶”返回一个结果：

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（4中概率为1），我们认为x位于“可能x”空间的下四分之一，并消除该空间的上四分之三
  • 如果f()返回1（4中的概率为3），我们认为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 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

由于 f() 的每次返回代表 TRUE 的概率为 3/4，因此通过一些代数我们可以适当地平衡概率。我们想要的是另一个函数 x()，它返回 TRUE 的平衡概率，因此

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

50% 的时间返回 true。

因此，让我们计算 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() 应该以 2/3 的概率返回 TRUE，因为 2/3 * 3/4 = 6/12 = 1/2；

因此，以下应该适用于 g()：

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

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将结果相加，任何其他总和构成另外的 1/2。

编辑。
正如 bdk 所说 - {0,0} 的可能性小于 {1,1} 因为

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

定义

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

但是，我自己也很困惑，因为给出了 f[x] （Mathematica）或 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

这很像蒙蒂·霍尔悖论。

一般来说。

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