logo标签列表

一道面试题目：关于概率论

algorithmrandomprobability
38

一道面试题：

给出一个函数 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)
            }       
    }
}

我对吗？你的解决方案是什么？（可以使用任何语言）

1
它返回0/1还是打印0/1？ - Sam Dufel
请将以下与编程有关的内容从英语翻译为中文。只返回已翻译的文本。抱歉造成困扰。 - Sawyer
你的函数可能会陷入无限循环。 - Dave O.
1
@Dave，它可能行，但不太可能。;p - Steven Jeuris
@ Dave O. - 同意。这可能适用于所有解决方案，但没有看到实际情况很难确定。 - dbasnett
显示剩余2条评论
10个回答
61
如果你连续两次调用 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）。
1
嗯，这里贝叶斯定理的使用很有意思，一些循环引入了归一化...... - Ludovico Fischer
谢谢，这与“如何从一个有偏差的硬币中制作一个公平的硬币”经典问题的答案相同。https://dev59.com/XW035IYBdhLWcg3wbPY5 - alex
8

你的解决方案是正确的，但效率不高且存在重复的逻辑。以下是同样算法在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）中。四分之三的数字位于区间的底部四分之三，四分之一位于区间的顶部四分之一。我们根据对f(x)的调用来决定选择哪一个。这意味着我们现在处于较小的区间中。
如果我们重复足够多次，就可以尽可能准确地确定我们的有限数字，并且将具有任何原始区间中的任何区域结束的完全相等的概率。特别地，我们有一个相同的概率大于或小于0.5的结果。
如果你想要，你可以重复这个想法，一次一个比特地生成无限的数据流。实际上，这被证明是生成这种流最有效的方法，并且是信息论中“熵”思想的来源。
哎呀，你说得对。已经修复了。它的工作方式是，如果我们进入一个区间后没有停止，那么我们就会均匀地选择从0到1之间的任意数字。实际上，我们会在知道数字将位于0.5的哪一侧时立即停止。我会尝试添加一些解释。 - btilly
函数 f() 的熵为 lg(4)/4+lg(4/3)*3/4 ≈ 0.81。因此，期望中大约需要调用 f() 约 1.23 次？ - Thomas Ahle
8
你的算法问题在于它有很高的重复概率。我的代码:
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)的平均次数。对于您的算法，每计算一次g(x)，就会计算约5.3次f(x)。而使用我的算法，这个数字降至约3.5次。到目前为止，其他答案也是如此，因为它们实际上与您所说的算法相同。
P.S.：目前您的定义没有提到“随机”，但可能是默认的。请参见我的其他答案。
我点赞了这个帖子，但后来又取消了，因为我认为看到了一个错误，但现在无法再次点赞。 :-( 无论如何，+1！当您编辑时，我相信我可以再次投票。也许可以更详细地解释一下答案？ :) - Steven Jeuris
1
@Steven，我看到你在玩弄我的声誉 :) - Snowbear
你可以通过区分 0、0、1 和 1、0、0 等不同的方式来处理另外 6 个未处理的情况。 - Tony Delroy
3
Given a function f(x) that 1/4 times returns 0, 3/4 times returns 1

严格按照这个声明的字面意思，如果调用f(x)四次，它将始终返回零一次和1三次。这与说f(x)是一个概率函数并且0到1的比率将在许多迭代中趋近于1到3（1/4 vs 3/4）是不同的。如果第一种解释是有效的，则无论您从序列的哪个位置开始，满足条件的唯一有效函数为重复0111的序列（或1011或1101或1110，这些是从不同起点开始的相同序列）。鉴于这个限制，
  g()= (f() == f())

应该足够了。
我已经看到那个问题的变化很多次了，甚至不用计算概率，我就知道答案。因此，在面试问题的背景下，我认为“独立同分布试验”是正确的假设。当然，有些面试官只是刁钻，所以准备另一个“坑人的问题”变种也是很好的。 - Jim Lewis
3

如前所述，您对概率的定义并不太好。通常这意味着不仅概率好，而且分布也好。否则，您可以简单地编写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)一次。但结果不会非常随机。

我不认为这是作弊——你正好给了面试官他们要求的东西。话虽如此，你的函数最终可能会返回(0)反转为(1)，(1) => (1)，(1)反转为(0)，(1) => (1)，3个1和1个0。为什么不只计算一次f()（以证明你已经使用过它），然后在每次调用g()时翻转结果呢？ - Jimmy
3
该方法是对btilly答案中使用的方法进行了细化，实现了每个“g（）”结果平均约1.85次“f（）”调用（下面进一步改进的方法实现了约1.75次，“tbilly”的实现方式为约2.6次，Jim Lewis的最佳答案为约5.33次）。代码在答案下方。
基本上，我使用均匀概率在0到3范围内生成随机整数：然后用户可以测试第一个50/50值的位0，并测试第二个50/50值的位1。原因是：“f（）”的1/4和3/4概率比半数更容易映射到四分之一。
算法描述：
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）。

1

这里是一个基于中心极限定理的解决方案，最初由我的一个朋友提出：

/*
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;
}
0

由于f()的每次返回都代表着3/4的TRUE几率，我们可以通过一些代数运算来正确平衡这些几率。我们需要的是另一个函数x()，它返回一个平衡的TRUE概率，以便

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

有50%的概率返回true。

因此，假设我们已知p(f)和期望的总概率（1/2），让我们来计算x的概率(p(x))：

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);
}
我认为这意味着你只能使用 f(x) 作为随机生成器，而不能使用其他任何 rand()。 - Eelvex
0

假设

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}
我认为这行代码不可行。它假设f(x)+f(x)的四个可能值是等概率的。然而在现实中，{0,0}出现的概率比{1,1}要小得多。 - bdk
看起来你有些困惑 :-)。这些函数并不是真正的f(x)和g(x)...它们没有输入，只是f()和g()。因此，不存在f(x+1)。至于f()+f()...有1/16的概率为0，6/16的概率为1，9/16的概率为2。你的g()函数在测试1时会“切换”，因此两个结果的概率分别为6/16和10/16（需要等可能地出现）。 - Tony Delroy
0

这很像蒙提霍尔悖论。

一般来说。

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
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接