Detailed Explanation of Python Probability Generation Problem Case

Probability generation problem

 Have 1 Uneven coins require uniform probability distribution 
 Have 1 A uniform coin requires an uneven probability distribution, such as  0.25  And  0.75
 Utilization  Rand7()  Realization  Rand10()

Equal probability of uneven coins

There is an uneven coin coin (), which can return two values of 0 and 1 with probabilities of 0.6 and 0.4 respectively. It is required to use this coin to produce a uniform probability distribution. That is, write a function coin_new () so that it returns 0, and the probability of 1 is 0.5.

#  Uneven coins, return  0 , 1  The probabilities of are respectively  0.6 , 0.4
def coin():
    return 0 if random.randint(1,10) > 4 else 1

Statistics the probability distribution of the result of tossing a coin twice:

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

The probability distribution of 0 1 and 1 0 obtained by throwing two coins in succession is the same. Therefore, the solution to this problem is to toss coins twice in a row. If you get 0 1, return 0; If you get 1 0, return 1; If the two results are the same, throw it again.

By analogy, no matter what the probability of this uneven coin is, the result of equal probability can be obtained by this method.

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

Complete test code:

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

Uniform coins produce unequal probabilities

There is a uniform coin coin (), which can return two values of 0 and 1 with a probability of 0.5. It is required to write a function coin_new () so that it returns the specified 0, 1 probability distribution.

#  Uniform coin  
def coin():
    return random.randint(0,1)  

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

For uniform coins, the probability of getting 0 0, 0 1, 1 0 and 1 1 by throwing them twice in succession is 1/4. Obviously, you only need to toss the coin twice in a row. If you get 0 0, you will return 0, and otherwise you will return 1.

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

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

Flip coins twice in a row. If 1 1 is obtained, 0 is returned; If you get 1 0 or 0 1, return 1; If you get 0 0, continue tossing coins.

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

Every time a coin is tossed, one digit of binary number will be obtained. If a coin is tossed four times in a row, every number of [0, 15] can be generated with equal probability, which is recorded as x. Remove [10, 15], and every number remaining [0, 9] is still equal probability. Returns 0 if x is [0, 2] x\ in [0, 2] x is [0, 2]; x peril [4, 9] x\ in [4, 9] x peril [4, 9], returns 1; x ≥ 10 x ≥ 10 x ≥ 10, repeat the above process.

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

Summarize

Every time a coin is tossed, one bit of binary number will be obtained. If k coins are tossed continuously, each number of [0, 2 k-1] [0, 2 k-1] [0, 2 k-1] [0, 2 k-1] [0, 2 k-1] [0, 2 k-1] [0, 2k-1] [0, 2k-1] [0, 2k-1] [EN + n\ frac {n} {m+n} m+nn.

With regard to the selection of k, it is necessary to meet N at least < = 2 k − 1 N < = 2^k-1 N < = 2k-1, where N is the minimum number of different numbers required to generate the corresponding probability distribution. For example, to generate 1/3 and 2/3 distributions, at least 3 different numbers are needed, then N = 3 and k = 2; To generate a 3/10, 7/10 distribution that requires at least 10 numbers, N = 10, k = 4.

k has no limit at most. We can always solve the problem by tossing more coins, just discard useless numbers. But our goal is to minimize the proportion of useless numbers, because every time we encounter useless numbers, we need to regenerate new numbers.

Rand7 Generates Rand10

The existing method Rand7 () can generate uniform random integers in the range of 1 to 7. Try to write a method Rand10 () to generate uniform random integers in the range of 1 to 10.

Coin toss can be regarded as Rand2 (), which uniformly generates two integers, 0 and 1. How do I generate Rand10 () from Rand2 ()? Taking the result of each coin toss as every bit of binary, we can get a uniform random integer in the range of [0, 2 k-1] [0, 2 k-1] [0, 2k-1]. You only need to toss coins four times to get integers in the range of [0, 15]. Returns an integer in the range of [1, 10], otherwise the coin is flipped again.

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

Take Rand7 ()-1 as the corresponding binary bit. Every time k Rand7 () is executed, a septal integer of k bits is obtained, which is evenly distributed in the range of [0, 7 k-1] [0, 7 ^ k-1] [0, 7k-1].

Simply execute k = Rand7 () twice to get a uniform integer in the range [0, 48]:

Returns x when x peril [1, 10] x\ in [1, 10] x peril [1, 10], otherwise recalculates:

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

Take one step to optimize

Select the number in the range [1, 40] and obtain the number in the range [1, 10] by remainder operation:

#  Uneven coins, return  0 , 1  The probabilities of are respectively  0.6 , 0.4
def coin():
    return 0 if random.randint(1,10) > 4 else 1

0

For the above nine useless numbers, calculating x% 40 yields a uniform random integer in the range [0, 8]. At this time, call Rand7 () again and calculate (x% 40) * 7 + Rand7 (), which is equivalent to Rand9 () * 7 + Rand7 (). Obviously, uniform random integers in the range of [1,63] can be obtained. At this time, all the numbers in the range of [1, 60] can be used for remainder operation, only 61, 62 and 63 are useless numbers:

#  Uneven coins, return  0 , 1  The probabilities of are respectively  0.6 , 0.4
def coin():
    return 0 if random.randint(1,10) > 4 else 1

1

For 61, 62, 63, call Rand7 () again, calculate (x-61) * 7 + Rand7 (), which is equivalent to Rand3 () * 7 + Rand7 (), and you can get a uniform random integer in the range of [1, 21]. At this time, the remainder operation is performed again, and there is only one useless number (21):

#  Uneven coins, return  0 , 1  The probabilities of are respectively  0.6 , 0.4
def coin():
    return 0 if random.randint(1,10) > 4 else 1

2

Every time while is executed, only one useless number (21) will be discarded, and the probability of re-execution is very low.

RandM Generates RandN

It is known that RandM () can generate random integers in the range of [0, M-1] with equal probability, then k times are executed, each time one bit of M is obtained, and random integers in the range of [0, M k-1] [0, M ^ k-1] [0, Mk-1] can be generated with equal probability, which is denoted as x.

RandN requires at least N uniform random integers, so only k needs to be taken so that M k-1 > = N M^k-1 > = N Mk−1 > = N. There are many ways to get RandN:
One is to return x only when x is [0, N-1] x\ in [0, N-1] x is [0, N-1], and the other is to use remainder operation to use as many generated numbers as possible on the premise of ensuring equal probability, thus reducing the proportion of discarded numbers and reducing the probability of repeated execution of while.