概率生成問題

有一枚不均勻的硬幣，要求產(chǎn)生均勻的概率分布
有一枚均勻的硬幣，要求產(chǎn)生不均勻的概率分布，如 0.25 和 0.75
利用 Rand7() 實(shí)現(xiàn) Rand10()

不均勻硬幣 產(chǎn)生等概率

現(xiàn)有一枚不均勻的硬幣 coin()，能夠返回 0、1 兩個(gè)值，其概率分別為 0.6、0.4。要求使用這枚硬幣，產(chǎn)生均勻的概率分布。即編寫一個(gè)函數(shù) coin_new() 使得它返回 0、1 的概率均為 0.5。

# 不均勻硬幣，返回 0、1 的概率分別為 0.6、0.4
def coin():
    return 0 if random.randint(1,10) > 4 else 1

統(tǒng)計(jì)拋兩次硬幣的結(jié)果的概率分布：

結(jié)果 0 1
0 0.60.6=0.36 0.60.4=0.24
1 0.40.6=0.24 0.40.4=0.16

連續(xù)拋兩枚硬幣得到 0 1 和 1 0 的概率分布是相同的。因此這道題的解法就是連續(xù)拋兩次硬幣，如果得到 0 1，返回 0；如果得到 1 0，返回 1；如果兩次結(jié)果相同，則重新拋。

以此類推，無論這枚不均勻硬幣的概率是多少，都可以用這種方法得到等概率的結(jié)果。

ddef coin_new():
    while True:
        a = coin()
        if coin() != a:  
            return a

完整測試代碼：

def coin():
    return 0 if random.randint(1,10) > 4 else 1

def coin_new():
    while True:
        a = coin()
        if coin() != a:  
            return a
if __name__ == '__main__':
    a = 0
    b = 0
    n = 100000
    for _ in range(n):
        if coin_new():a += 1
        if coin():b += 1

    print(f"1:{a/n},1:{b/n}")

均勻硬幣 產(chǎn)生不等概率

現(xiàn)有一枚均勻的硬幣 coin()，能夠返回 0、1 兩個(gè)值，其概率均為 0.5。要求編寫一個(gè)函數(shù) coin_new()，使得它返回指定的 0、1 概率分布。

# 均勻硬幣 
def coin():
    return random.randint(0,1)  

P(0) = 1/4，P(1) = 3/4

對于均勻硬幣而言，連續(xù)拋兩次，得到 0 0、0 1、1 0、1 1 的概率均為 1/4。顯然，只需要連續(xù)拋兩次硬幣，如果得到 0 0，返回 0，其他情況返回 1。

def coin_new():
    return coin() or coin()

P(0) = 1/3，P(1) = 2/3

連續(xù)拋兩次硬幣。如果得到 1 1，返回 0；如果得到 1 0 或 0 1，返回 1；如果得到 0 0，繼續(xù)拋硬幣。

def coin_new():
    while True:
        a, b = coin(), coin()
        if a & b: return 0
        if a | b: return 1

P(0) = 0.3，P(1) = 0.7

每拋一次硬幣，會(huì)得到二進(jìn)制數(shù)的一位，連續(xù)拋 4 次硬幣，可以等概率生成 [0, 15] 的每個(gè)數(shù)，記為 x。去掉 [10, 15]，剩下 [0, 9] 的每個(gè)數(shù)依然是等概率的。如果 x ∈ [ 0 , 2 ] x \in [0, 2] x∈[0,2]，返回 0； x ∈ [ 4 , 9 ] x \in [4, 9] x∈[4,9]，返回 1； x ≥ 10 x ≥ 10 x≥10，重復(fù)上述過程。

def coin_new():
    while True:
        x = 0
        for _ in range(4):
            x = (x << 1) + coin()
        if x <= 2: return 0
        if x <= 9: return 1

總結(jié)

每拋一次硬幣，會(huì)得到二進(jìn)制數(shù)的一位，連續(xù)拋 k 次硬幣，可以等概率生成 [ 0 , 2 k − 1 ] [0, 2^k-1] [0,2k−1] 的每個(gè)數(shù)在 [ 0 , 2 k − 1 ] [0, 2^k-1] [0,2k−1][ 中，選取 m 個(gè)數(shù)返回 0，n 個(gè)數(shù)返回 1，則 0、1 的概率分別為 m m + n \frac{m}{m+n} m+nm​ 、 n m + n \frac{n}{m+n} m+nn​。

關(guān)于 k 的選擇，最少需要滿足 N < = 2 k − 1 N <= 2^k-1 N<=2k−1，N 是生成對應(yīng)概率分布至少需要多少個(gè)不同數(shù)字。比如要生成 1/3、2/3 的分布，至少需要 3 個(gè)不同數(shù)字，則 N = 3, k = 2；要生成 3/10、7/10 的分布，至少需要 10 個(gè)數(shù)字，則 N = 10, k = 4。

k 最多則沒有限制，我們總可以通過拋更多次硬幣來解決問題，只需要把無用的數(shù)字舍棄即可。但我們的目的是盡可能減少無用數(shù)字的比例，因?yàn)槊看斡龅綗o用數(shù)字時(shí)，都需要重新生成新的數(shù)字。

Rand7 生成 Rand10

已有方法 Rand7() 可生成 1 到 7 范圍內(nèi)的均勻隨機(jī)整數(shù)，試寫一個(gè)方法 Rand10() 生成 1 到 10 范圍內(nèi)的均勻隨機(jī)整數(shù)。

拋硬幣可以看作是 Rand2()，均勻生成 0、1 兩個(gè)整數(shù)。如何根據(jù) Rand2() 生成 Rand10()？將每次拋硬幣的結(jié)果，看作二進(jìn)制的每一位，就可以得到 [ 0 , 2 k − 1 ] [0, 2^k-1] [0,2k−1] 范圍內(nèi)的均勻隨機(jī)整數(shù)。只需要拋 4 次硬幣，就能得到 [0, 15] 范圍的整數(shù)。返回 [1, 10] 范圍的整數(shù)，其他情況則重新拋硬幣。

def rand10():
    while True:
        x = 0
        for _ in range(4):
            x = x << 1 + rand2()
            
        if 1 <= x <= 10: return x

取 Rand7() - 1 作為對應(yīng)的 7 進(jìn)制位。每執(zhí)行 k 次 Rand7()，將得到一個(gè) k 位的 7 進(jìn)制整數(shù)，在 [ 0 , 7 k − 1 ] [0, 7^k-1] [0,7k−1] 范圍內(nèi)均勻分布。

只需執(zhí)行 k = 2 次 Rand7()，就可以得到范圍為 [0, 48] 的均勻整數(shù)：

當(dāng) x ∈ [ 1 , 10 ] x \in [1, 10] x∈[1,10] 時(shí)返回 x，否則重新計(jì)算：

def rand10():
    while True:
        x = (rand7() - 1) * 7 + (rand7() - 1);
        if 1 <= x <= 10: return x

進(jìn)一步優(yōu)化

選擇 [1, 40] 范圍里的數(shù)，通過取余運(yùn)算來得到 [1, 10] 范圍的數(shù)：

def rand10():
    while True:
        x = (rand7() - 1) * 7 + (rand7() - 1)
        if 1 <= x <= 40:
            return x % 10 + 1

對于上面這 9 個(gè)無用數(shù)字，計(jì)算 x % 40 可以得到 [0, 8] 范圍的均勻隨機(jī)整數(shù)。此時(shí)再調(diào)用一次 Rand7()，計(jì)算 (x % 40) * 7 + Rand7()，這相當(dāng)于 Rand9() * 7 + Rand7()。顯然，可以得到 [1, 63] 范圍的均勻隨機(jī)整數(shù)。這時(shí) [1, 60] 范圍里的數(shù)都可以用來作取余運(yùn)算，只有 61、62、63 共 3 個(gè)無用數(shù)字：

def rand10():
    while True:
        x = (rand7() - 1) * 7 + (rand7() - 1)
        if 1 <= x <= 40:
            return x % 10 + 1   
            
    	x = (x % 40) * 7 + rand7() # 1~63
    	if x <= 60: return x % 10 + 1

對于 61、62、63，再調(diào)用一次 Rand7()，計(jì)算 (x - 61) * 7 + Rand7()，相當(dāng)于 Rand3() * 7 + Rand7()，可以得到 [1, 21] 范圍的均勻隨機(jī)整數(shù)，這時(shí)再作取余運(yùn)算，只有 1 個(gè)無用數(shù)字（21）：

def rand10():
    while True:
        x = (rand7() - 1) * 7 + (rand7() - 1)
        if 1 <= x <= 40:
            return x % 10 + 1   
            
    	x = (x % 40) * 7 + rand7() # 1~63
    	if x <= 60: return x % 10 + 1

        x = (x - 61) * 7 + 7 # 1~21
        if x <= 20: return x % 10 + 1

每次 while 執(zhí)行的時(shí)候，只有 1 個(gè)無用數(shù)字（21）會(huì)被舍棄，重新執(zhí)行的概率很低。

RandM 生成 RandN

已知 RandM() 可以等概率的生成 [0, M-1] 范圍的隨機(jī)整數(shù)，那么執(zhí)行 k 次，每次都得到 M 進(jìn)制的一位，可以等概率生成 [ 0 , M k − 1 ] [0, M^k-1] [0,Mk−1] 范圍的隨機(jī)整數(shù)，記為 x。

RandN 至少需要 N 個(gè)均勻隨機(jī)整數(shù)，因此只需要取 k，使得 M k − 1 > = N M^k-1 >= N Mk−1>=N 即可，此時(shí)有多種方式得到 RandN：
一種是只在 x ∈ [ 0 , N − 1 ] x \in [0, N-1] x∈[0,N−1] 時(shí)返回 x，另一種是利用取余運(yùn)算，在保證等概率的前提下，盡可能多的利用生成的數(shù)字，從而減少舍棄的數(shù)字比例，降低 while 重復(fù)執(zhí)行的概率。

到此這篇關(guān)于Python 概率生成問題案例詳解的文章就介紹到這了,更多相關(guān)Python 概率生成問題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論