Python 概率生成問題案例詳解

 更新時間:2021年09月10日 10:05:42   作者:Yake1965  
這篇文章主要介紹了Python 概率生成問題案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下

概率生成問題

有一枚不均勻的硬幣,要求產生均勻的概率分布
有一枚均勻的硬幣,要求產生不均勻的概率分布,如 0.25 和 0.75
利用 Rand7() 實現 Rand10()

不均勻硬幣 產生等概率

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

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

統計拋兩次硬幣的結果的概率分布:

結果 0 1
0 0.60.6=0.36 0.60.4=0.24
1 0.40.6=0.24 0.40.4=0.16

連續拋兩枚硬幣得到 0 1 和 1 0 的概率分布是相同的。因此這道題的解法就是連續拋兩次硬幣,如果得到 0 1,返回 0;如果得到 1 0,返回 1;如果兩次結果相同,則重新拋。

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

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}")

均勻硬幣 產生不等概率

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

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

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

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

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

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

連續拋兩次硬幣。如果得到 1 1,返回 0;如果得到 1 0 或 0 1,返回 1;如果得到 0 0,繼續拋硬幣。

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

每拋一次硬幣,會得到二進制數的一位,連續拋 4 次硬幣,可以等概率生成 [0, 15] 的每個數,記為 x。去掉 [10, 15],剩下 [0, 9] 的每個數依然是等概率的。如果 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,重復上述過程。

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

總結

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

關于 k 的選擇,最少需要滿足 N < = 2 k − 1 N <= 2^k-1 N<=2k−1,N 是生成對應概率分布至少需要多少個不同數字。比如要生成 1/3、2/3 的分布,至少需要 3 個不同數字,則 N = 3, k = 2;要生成 3/10、7/10 的分布,至少需要 10 個數字,則 N = 10, k = 4。

k 最多則沒有限制,我們總可以通過拋更多次硬幣來解決問題,只需要把無用的數字舍棄即可。但我們的目的是盡可能減少無用數字的比例,因為每次遇到無用數字時,都需要重新生成新的數字。

Rand7 生成 Rand10

已有方法 Rand7() 可生成 1 到 7 范圍內的均勻隨機整數,試寫一個方法 Rand10() 生成 1 到 10 范圍內的均勻隨機整數。

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

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

取 Rand7() - 1 作為對應的 7 進制位。每執行 k 次 Rand7(),將得到一個 k 位的 7 進制整數,在 [ 0 , 7 k − 1 ] [0, 7^k-1] [0,7k−1] 范圍內均勻分布。

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

當 x ∈ [ 1 , 10 ] x \in [1, 10] x∈[1,10] 時返回 x,否則重新計算:

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

進一步優化

選擇 [1, 40] 范圍里的數,通過取余運算來得到 [1, 10] 范圍的數:

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

對于上面這 9 個無用數字,計算 x % 40 可以得到 [0, 8] 范圍的均勻隨機整數。此時再調用一次 Rand7(),計算 (x % 40) * 7 + Rand7(),這相當于 Rand9() * 7 + Rand7()。顯然,可以得到 [1, 63] 范圍的均勻隨機整數。這時 [1, 60] 范圍里的數都可以用來作取余運算,只有 61、62、63 共 3 個無用數字:

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,再調用一次 Rand7(),計算 (x - 61) * 7 + Rand7(),相當于 Rand3() * 7 + Rand7(),可以得到 [1, 21] 范圍的均勻隨機整數,這時再作取余運算,只有 1 個無用數字(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 執行的時候,只有 1 個無用數字(21)會被舍棄,重新執行的概率很低。

RandM 生成 RandN

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

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

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

相關文章

  • python中的split()函數和os.path.split()函數使用詳解

    python中的split()函數和os.path.split()函數使用詳解

    今天小編就為大家分享一篇python中的split()函數和os.path.split()函數使用詳解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-12-12
  • Python多進程fork()函數詳解

    Python多進程fork()函數詳解

    今天小編就為大家分享一篇關于Python多進程fork()函數詳解,小編覺得內容挺不錯的,現在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2019-02-02
  • python實現簡單多人聊天室

    python實現簡單多人聊天室

    這篇文章主要為大家詳細介紹了python實現簡單多人聊天室功能,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-12-12
  • Python操作Sql Server 2008數據庫的方法詳解

    Python操作Sql Server 2008數據庫的方法詳解

    這篇文章主要介紹了Python操作Sql Server 2008數據庫的方法,結合實例形式分析了Python使用pyodbc庫操作Sql Server 2008數據庫的連接、執行sql語句、關閉連接等相關操作技巧與注意事項,需要的朋友可以參考下
    2018-05-05
  • Python入門開發教程  windows下搭建開發環境vscode的步驟詳解

    Python入門開發教程 windows下搭建開發環境vscode的步驟詳解

    大家都知道Python是跨平臺的,它可以運行在Windows、Mac和各種Linux/Unix系統上。在Windows上寫Python程序,放到Linux上也是能夠運行的,今天給大家分享Python開發環境搭建vscode的步驟,一起看看吧
    2021-07-07
  • python協程之動態添加任務的方法

    python協程之動態添加任務的方法

    今天小編就為大家分享一篇python協程之動態添加任務的方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-02-02
  • python selenium自動化測試框架搭建的方法步驟

    python selenium自動化測試框架搭建的方法步驟

    這篇文章主要介紹了python selenium自動化測試框架搭建的方法步驟,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-03-03
  • flask入門之表單的實現

    flask入門之表單的實現

    這篇文章主要介紹了flask入門之表單的實現,小編覺得挺不錯的,現在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2018-07-07
  • Python操作csv文件實例詳解

    Python操作csv文件實例詳解

    這篇文章主要為大家詳細介紹了Python操作csv文件的實例,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2017-07-07
  • 用實例分析Python中method的參數傳遞過程

    用實例分析Python中method的參數傳遞過程

    這篇文章主要介紹了用實例分析Python中method的參數傳遞過程,包括instancemethod和staticmethod等實例,需要的朋友可以參考下
    2015-04-04

最新評論

精品国内自产拍在线观看