Randomized algorithm

1. How to generate 0,1 with 50% probability?? Ans:- we can think of natural number . We know that every two consecutive number is always odd and even or even and odd.

   • Ex. 1(odd) 2(even) 3(odd) 4(even) 5(odd) 6(even) 7(odd) 8(even) 9(odd) 10(even). At each iteration we try to generate a number it could be either even number or odd.If we do AND operation with 1 then if number is odd then it will give you 1 else 0.

2. Given a function rand2() that returns 0 or 1 with equal probability, write a function that returns 1 with 75% probability and 0 with 25% probability using rand2() only.

   • Ans:-The idea is to use Bitwise OR. A bitwise OR takes two bits and returns 0 if both bits are 0, while otherwise the result is 1. So it has 75% probability that it will return 1.

There are various kind of problem like generate rand6() from rand2() and many more. I will explain some of them here.

1. Given a function rand6() that returns random numbers from 1 to 6 with equal probability, implement one-liner function rand12() using rand6() that returns random numbers from 1 to 12 with equal probability.

   • Ans:-rand6() can generate 1,2,3,4,5,6 but what about 7,8,9,10,11,12.
   • So we can think of like this rand6()&1 which will always generate number 1,0 and if multiply with 6 then

2. Given a function rand2() that returns 0 or 1 with equal probability, implement rand3() using rand2() that returns 0, 1 or 2 with equal probability.

   • Ans:-The idea is to use expression 2 * rand2() + rand2(). It returns 0, 1, 2, 3 with equal probability. To make it return 0, 1, 2 with equal probability, we eliminate the undesired event 3.

Generalization:- Implement randM() using randN() when M > N: Use randX() to generate randM().

Note: N^b * (randN() - 1) + N^(b - 1) * (randN() - 1) + N^(b - 2) * (randN() - 1) + ... + N^0 * (randN() - 1) generates randX() - 1, where X = N^(b + 1).

• More Examples**(1) I**