# Python 概率生成问题案例详解

## 概率生成问题

有一枚不均匀的硬币，要求产生均匀的概率分布

### 不均匀硬币 产生等概率

# 不均匀硬币，返回 0、1 的概率分别为 0.6、0.4
def coin():
return 0 if random.randint(1,10) > 4 else 1


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

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


### 均匀硬币 产生不等概率

# 均匀硬币
def coin():
return random.randint(0,1)


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

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


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

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

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 最多则没有限制，我们总可以通过抛更多次硬币来解决问题，只需要把无用的数字舍弃即可。但我们的目的是尽可能减少无用数字的比例，因为每次遇到无用数字时，都需要重新生成新的数字。

### Rand7 生成 Rand10

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

if 1 <= x <= 10: return x


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


### 进一步优化

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


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


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


### RandM 生成 RandN

RandN 至少需要 N 个均匀随机整数，因此只需要取 k，使得 M k − 1 > = N M^k-1 >= N Mk−1>=N 即可，此时有多种方式得到 RandN：