Computer Science

Uniform distribution of a fair die over n integers has the the probability space of ;

Ω={0,1}n where in this case n=6

P(w) =(1/2)n for all w€Ω

The distribution unit can be called {0,1}6 . To sample from this distribution, simply fli a fair coin for each of the 6-bits

For i=1 to n

Draw X1 from M(1/2)

Output X1 X2.....X6

Suppose we have distribution over {1,2,3,4,5}

Ω={1,2,3,4,5}

P(w)= 1/5 for all w€ Ω the sampling algorithm is

Let n=

Repeat Generate a sample X from Unif ({1,2, . . . ,5}), as described above

If

X≤5

: output

X and halt

Using this algorithm it is possible to generate the outcomes as many times as possible.

Question 2

bool FairCoinFromBiasedCoin() {

bool coin1, coin2;

do {

coin1 = function_P();

coin2 = function_P();

} while (coin1 == coin2);

return coin1;

}

To simulate this there is need to try

sum(fairCoin(biasedCoin) for i in range(10000))

for 10000 range by depending on P can perform ;

where t is the running time that is independent on P

Question 3

Distribution Ω={w1,….,w5}

P(w5)=P5

With fenite precission,

Generate X from Unif [0,1]

For all i=1 to 5

If p1+…+pi-1<X≤p1+…+pi : output wi

Dividing the interval [0,1] into 5 bins, the 5th bin stretches from p1+…+pi to p1+…+pi with length pi.

We generate X uniformly from [0,1] and then output correct . The chance of resulting to 5th output with no fail (that is, of outputting p1) is therefore exactly pi.

As before, we can run this process by generating X one bit at a time and stopping as soon as it is clear which X will be still correct. It is possible to show that the expected number of bits (coin flips) needed is

Question 4 a

if we take the result of the toss to be a and b, then if b-a is not a power of 2 the generated output will not fall in the subset of X. regenerating X is achieved by b-a=2n +1 for integer n the outcome of the subset of X will then have to always >50% chances of falling in this range.

Question 4 b

P(X ⊆Y ) = 25+1 = 36

P(X ∪ Y = [n])= P(X ⊆Y )- n = 31

Question 5

LinearMax (z, p)

n=|z|

while |z|>max {}do

j = 1

select I such that n.

else output “No item found”