三、假設(shè)你希望以1/2的概率輸出0與 1。你可以自由使用一個(gè)輸出0或1的過(guò)程 BIASED-RANDOM。它以某概率 p 輸出1，概率 1-p 輸出0，其中 0<p<1 ，但是 p 的值未知。請(qǐng)給出一個(gè)利用 BIASED-RANDOM 作為子程序的算法，返回一個(gè)無(wú)偏的結(jié)果，能以概率1/2返回0，以概率 1/2 返回1。作為 p 的函數(shù)，你的算法的期望運(yùn)行時(shí)間是多少?

文心一言：

可以使用貝葉斯公式來(lái)計(jì)算無(wú)偏的結(jié)果。假設(shè)我們進(jìn)行了n次試驗(yàn)，其中BIASED-RANDOM以概率p輸出1，以概率1-p輸出0。設(shè)N0為輸出0的次數(shù)，N1為輸出1的次數(shù)，則有N0+N1=n。根據(jù)貝葉斯公式，可以得到：

p(N0, N1|p) = p(N0, N1, p) / p(p)

其中，p(N0, N1, p)表示在n次試驗(yàn)中，N0次試驗(yàn)輸出0，N1次試驗(yàn)輸出1，且BIASED-RANDOM以概率p輸出1的概率。p(p)表示概率p的概率密度函數(shù)，可以在已知p的范圍的情況下計(jì)算得到。

由于要求無(wú)偏的結(jié)果，因此N0和N1的概率分布應(yīng)該是相等的。因此，可以取p(N0, N1|p) = 1 / (n+1)，并將此值作為算法的輸出結(jié)果。

該算法的期望運(yùn)行時(shí)間取決于n的大小。在最壞情況下，即n非常大時(shí)，每次試驗(yàn)都需要很長(zhǎng)時(shí)間才能得到結(jié)果。因此，該算法的期望運(yùn)行時(shí)間可能會(huì)非常大。但是，當(dāng)n比較小的時(shí)候，該算法的運(yùn)行時(shí)間是O(1)的。

訊飛星火：

我們可以使用 BIASED-RANDOM 作為子過(guò)程，來(lái)生成一個(gè)無(wú)偏的隨機(jī)數(shù)。具體來(lái)說(shuō)，我們可以利用 BIASED-RANDOM 生成兩個(gè)獨(dú)立的隨機(jī)數(shù) x 和 y,然后根據(jù)以下條件計(jì)算出一個(gè)新的隨機(jī)數(shù) z:

• ??如果 x 輸出了 1,y 輸出了 0,則 z 輸出 0;

• ??如果 x 輸出了 0,y 輸出了 1,則 z 輸出 1;

• ??否則，z 輸出 x*y。

這個(gè)新的隨機(jī)數(shù) z 就是我們需要的結(jié)果。由于 BIASED-RANDOM 是無(wú)偏的，因此這個(gè)新隨機(jī)數(shù) z 也是無(wú)偏的。同時(shí)，由于 BIASED-RANDOM 只依賴于 p 和 x、y 兩個(gè)獨(dú)立的過(guò)程，因此它的期望運(yùn)行時(shí)間是 O(p)。

現(xiàn)在我們來(lái)計(jì)算一下這個(gè)新隨機(jī)數(shù) z 的期望值。由于 BIASED-RANDOM 是一個(gè)二元過(guò)程，因此它的期望值為 pp+(1-p)(1-p)=2p^2-2p+1。而根據(jù)上面的條件，z 的期望值為：

E(z) = p*(xy) + (1-p)(x*(1-y)) + (1-p)(y(1-x)) = pxy + (1-p)x + (1-p)y = pxy + px + py = p*(xy + x + y) = pz

因此，我們得到了一個(gè)新的期望運(yùn)行時(shí)間為 O(p),并且能夠以概率 1/2 返回 0、以概率 1/2 返回 1 的無(wú)偏隨機(jī)數(shù)生成函數(shù)。

華為盤(pán)古：

360智腦：

可以使用Bernoulli-Monte Carlo方法來(lái)實(shí)現(xiàn)。具體來(lái)說(shuō),可以設(shè)置BIASED-RANDOM過(guò)程的初始值為0,并不斷迭代直到達(dá)到所需的輸出結(jié)果。在每個(gè)迭代步驟中,將BIASED-RANDOM過(guò)程的輸出乘以p并將結(jié)果加上 BIASED-RANDOM過(guò)程的當(dāng)前值。重復(fù)此操作直到最終結(jié)果滿足要求為止。這個(gè)算法的預(yù)期時(shí)間復(fù)雜度取決于BIASED-RANDOM過(guò)程的期望時(shí)間復(fù)雜度。在這種情況下,由于每次迭代都涉及到一次BIASED-RANDOM過(guò)程的輸出,因此期望時(shí)間復(fù)雜度為O(E[BIASED-RANDOM]) = O(log E[x]),其中E表示期望值。由于 BIASED-RANDOM 是一個(gè)二項(xiàng)分布,其期望值可以通過(guò)二項(xiàng)分布的性質(zhì)來(lái)計(jì)算。因此,我們可以計(jì)算出BIASED-RANDOM的期望時(shí)間復(fù)雜度為O(log E[x]),其中E[x]表示任意兩個(gè)連續(xù)時(shí)間點(diǎn)之間經(jīng)過(guò)的時(shí)間間隔。

chatglm：

算法如下：

1.調(diào)用 BIASED-RANDOM 過(guò)程，得到概率 p 的值。

2.如果 p > 0.5，則返回 0。

3.如果 p < 0.5，則返回 1。

這種算法是無(wú)偏的，因?yàn)樗豢紤] BIASED-RANDOM 過(guò)程的輸出，而是根據(jù) p 的值隨機(jī)選擇返回 0 或 1。 對(duì)于每個(gè) p 的值，算法都需要調(diào)用 BIASED-RANDOM 過(guò)程一次，因此時(shí)間復(fù)雜度為 O(1)。

由于 BIASED-RANDOM 過(guò)程的輸出是隨機(jī)的，因此算法的期望運(yùn)行時(shí)間與 p 的值有關(guān)。當(dāng) p 接近 0 或 1 時(shí)，算法的期望運(yùn)行時(shí)間會(huì)相應(yīng)縮短，因?yàn)樵谶@種情況下，BIASED-RANDOM 過(guò)程的輸出更可能接近 0 或 1。

chatgpt：

為了以 1/2 的概率輸出 0 和 1，我們可以利用 BIASED-RANDOM 過(guò)程來(lái)實(shí)現(xiàn)。具體算法如下：

1.調(diào)用 BIASED-RANDOM 過(guò)程兩次；

2.如果兩次結(jié)果都是相同的，則返回這個(gè)結(jié)果；

3.否則，重復(fù)步驟 1。

由于 BIASED-RANDOM 過(guò)程只輸出 0 和 1 兩種結(jié)果，因此該算法的期望運(yùn)行時(shí)間不會(huì)超過(guò) 3 次調(diào)用 BIASED-RANDOM 過(guò)程。接下來(lái)，我們分別考慮前兩次調(diào)用 BIASED-RANDOM 過(guò)程的情況：

1.如果第一次和第二次調(diào)用的結(jié)果都是 0 或者都是 1，則直接返回這個(gè)結(jié)果即可；

2.如果第一次和第二次調(diào)用的結(jié)果不同，則需要再次調(diào)用 BIASED-RANDOM 過(guò)程，重復(fù)上述步驟。

由于 BIASED-RANDOM 過(guò)程的輸出概率為 p 和 1-p，因此兩次調(diào)用結(jié)果相同的概率為 p^2 + (1-p)^2，結(jié)果不同的概率為 2p(1-p)。因此，需要多次調(diào)用 BIASED-RANDOM 過(guò)程的概率為 2p(1-p)，即：

P(需要多次調(diào)用) = 2p(1-p)

第一次和第二次調(diào)用結(jié)果相同的概率為 p^2 + (1-p)^2，即：

P(第一次和第二次結(jié)果相同) = p^2 + (1-p)^2

因此，算法的期望運(yùn)行時(shí)間為：

E(T) = P(需要多次調(diào)用) * [2 + E(T)] + P(第一次和第二次結(jié)果相同)

展開(kāi)得到：

E(T) = 2p(1-p)*[2+E(T)] + (p^2 + (1-p)^2)

整理可得：

E(T) = 2 + 2p - 4p^2

因此，該算法的期望運(yùn)行時(shí)間為 O(1)，只需要進(jìn)行常數(shù)次 BIASED-RANDOM 過(guò)程調(diào)用即可得到無(wú)偏結(jié)果。