Generate 0 and 1 with 25% and 75% probability

Given a function that generates 0, 1 50% of the time (like most of the random function in modern programming languages do), how can we design a function that return 0, 1 25%, 75% of the time?

Let's lay out a rule: random functions that return floating points are not allowed to be used. One can only use the said function that returns 0, 1 in equal probability since one can easily set a floating point as a threshold and return 0, 1 according to the exceedance threshold values.

📚Content

1. Maths and Concept
2. Code implementation
3. Complexity
4. Result
5. Challenge

📐Maths and Concept

Let's revisit some basic Maths for probability.
We are given a function tha returns a 0, 1 with probability equal to 50%, we name it as *P(0=50% & 1=50%), P(0) = 0.5 and . How can we design an algorithm which uses P(0=50% & 1=50%) to achieve the said title?

To design P(0=25% & 1=75%), we propose two different methods.

OR operator

In short, we can perform one OR operator to achieve our goal:
P(0=25% & 1=75%) = P(0=50% & 1=50%) || P(0=50% & 1=50%)

The "||" operator performs OR operation. Here are all the result for such operation:

• 0 || 0 = 0
• 0 || 1 = 1
• 1 || 0 = 1
• 1 || 1 = 1
  Since P(0=50% & 1=50%) splits out 0, 1 with equal probability, each row at the above list has 25% of happening (Multiplication of the probability of two independent events). We can thus see that it hs only 1 out of 4 chance of getting a 0, thus 25%. At the same time, it has a 75% obtaining a 1.

Bitwise exclusive OR operator

There is another way to perform calculation for P(0=25% & 1=75%), by bit shifting and bitwise exclusive OR operation. It has the following pseudocode:

function bitwiserand75():
    # either {0, 1}
    set x to rand50()

    # either {00, 10}
    x = x << 1

    # either {00, 01, 10, 11}
    # XOR operator, set each bit to 1 if only
    # one of two bits is 1
    x = x ^ rand50()

    if x > 0:
        return 1
    return 0

The above pseudocode is quite straight foward, but readers may not be very familiar with XOR operation. In short, it sets each bit to 1 if only one of the two bits is 1. Here are some examples:

• 00 ^ 00 = 00
• 00 ^ 01 = 01
• 10 ^ 00 = 10
• 10 ^ 01 = 11

This, we get all the permutation of 0, 1 in a two digit binary setting. Looking at the above list, we know that 0, or 00 happens at 1 out of 4 times, if we set the threshold of returning 1 to be larger than 0, we have a 3 out of 4 chance to obtain a 1, thus 75%.

🖥️ Code implementation

Here is the code for implementing the two algorithms described in above section:

import random

class baisedGenerator:
    # Generator with 50% of 0 and 1
    def rand50(self):
        return random.randint(0, 1)
    
    # Associated with OR operator
    # Generator with 75% of 0 and 1
    def rand75(self):
        return self.rand50() or self.rand50()

    # Associated with bitwise shifting operator
    # Generator with 75% of 0 and 1 by bitwise shifting
    def bitwiserand75(self):
        x = self.rand50()
        x = x << 1
        x = x ^ self.rand50()
        if x > 0:
            return 1
        return 0

⏳Complexities

Time complexity

The above two methods has constant runtime complexity since the random module from python gives a random (0, 1) in constant time, and all multiplications, bitshifting and XOR operation takes O(1) to run.

Space complexity

The above two methods for baised generator do not require additional memory, thus constant auxiliary space.

✍🏻Result

One can simply aggregate the result by declaring a simple for loop and but printing out the result:

g = baisedGenerator()

for i in range(1, 101):
    print(g.rand75(), end=" ")
    if i%10 == 0:
        print()    
print()

for i in range(1, 101):
    print(g.bitwiserand75(), end=" ")
    if i%10 == 0:
        print()

Here is the result, with around 75% out of 100 that it prints 1 for both methods:

1 1 1 1 1 1 1 0 1 0 
1 0 1 0 1 1 1 1 1 1 
0 1 0 1 1 1 0 1 0 1 
1 1 1 1 0 1 1 1 1 0 
1 1 1 0 0 0 0 1 1 1 
1 1 1 1 1 0 1 0 0 1 
1 1 1 1 1 1 0 1 1 1 
0 0 1 1 1 1 1 1 1 0 
0 1 1 1 1 1 1 1 1 1 
0 1 1 1 1 0 1 1 0 1 

1 1 0 0 0 0 1 1 1 1 
0 1 1 1 0 1 1 1 0 1 
1 0 1 1 1 0 1 1 1 1 
1 1 1 1 1 1 0 1 1 0 
0 0 1 1 0 0 1 1 1 1 
1 1 1 1 1 1 1 1 1 0 
1 0 1 0 1 1 0 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 0 0 0 1 1 1 1 1 
0 1 1 1 1 1 1 0 1 1 

With this article at OpenGenus, you must have the complete idea of how to generate 0 and 1 with 25% and 75% probability.

🧠Challenge

Here you go, an easy non-floating point-based baised generator that gives 0 and 1 in 25% and 75%, but can you use the AND operator instead of OR operator to generate the same distribution of 0 and 1, assuming other rules unchanged?