家庭作业:每次调用返回两个值之一的函数

Question

我正在尝试编写一个函数,每次调用它都会返回true或false,但是具有已知频率,比如60%的时间它是真的,另外40%它将是错误的.使用该函数我将创建另一个函数,该函数在50%的时间内返回true.

我最初的方法是使用随机函数,如果低于0.6则返回true,如果超过则返回false.不知道如何使用它接近第二部分.

Answer 1

让我们来看一般情况:你建立了一个函数F1(),它以概率P返回True(在你的情况下,P = 60%).现在你用这种方式构建第二个函数:

F2():
   result1 = F1()
   result2 = F1()
   if result1 = True and result2 = False: return True
   elif result1 = False and result2 = True: return False
   else:  F2()

在这种情况下,运行F1两次并获得(True,False)的概率与获得(False,True)相同,并且它是P*(1-P).相反,如果你得到(True,True)或(False,False),你可以递归地调用F2.这意味着,在运行F2后,你总是以1/2的概率获得真或假,因为前两个分支具有相等的概率,而第三个总是给你1/2概率函数的结果.

我正在制作一个社区维基,以防有人想让我的答案更清楚.我意识到解释这个概念可能有点难.

平均通话次数

函数F2()在n次递归调用之后终止的概率是:

{(1-P)^ 2 + P ^ 2} ^ N*2P(1-P)

因此,所需的平均递归调用次数为:

\ Sum_ {i = 0} ^\infty i*{(1-P)^ 2 + P ^ 2} ^ i*2P(1-P)