面试问题:关于概率

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

您的解决方案是正确的,如果效率低下并且逻辑更复杂.这是一个更简洁的同一算法的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

这g()平均需要大约2.6次呼叫.

它的工作方式是这样的.我们试图从0到1选择一个随机数,但是一旦我们知道数字是0还是1,我们就会立即停止.我们开始知道数字是在区间(0,1)中.3/4的数字位于间隔的底部3/4,而1/4位于间隔的顶部1/4.我们根据电话决定哪个f(x).这意味着我们现在处于较小的间隔.

如果我们洗涤,冲洗并重复足够的次数,我们可以尽可能精确地确定我们的有限数,并且在原始间隔的任何区域中具有绝对相等的卷绕概率.特别是我们甚至有可能卷起大于或小于0.5.

如果你想要,你可以重复这个想法,逐一产生无穷无尽的比特流.事实上,这可以证明是产生这种流的最有效方式,并且是信息理论中熵思想的源泉.

Answer 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左右.到目前为止,其他答案也是如此,因为它们实际上与您所说的算法相同.

PS:你的定义目前没有提及'随机',但可能是假设.看到我的其他答案.