Youre given a fair coin and asked to sample uniformly a numb

You\'re given a fair coin and asked to sample uniformly a number from {0,1,2,3,4}. Give a randomized algorithm and analyze the expected running time of your algorithm.

Solution

n m r
3 1 0.25
8 3 0.15625
13 5 0.05078125
44 17 0.0378308072686
75 29 0.0247036782182
106 41 0.0113974522704
243 94 0.00933096248381
380 147 0.00726015308463
517 200 0.00518501504347
654 253 0.00310553931213
791 306 0.00102171682348
obtained with the formulas:

m=nlog32
r=13 powder m/2 powder n

Algorithm RandQuickSort(S = {a1, a2, · · · , an}
If |S| 1 then output S; else:
Choose a pivot element ai uniformly at random (u.a.r.) from S
Split the set S into two subsets S1 = {aj |aj < ai}
and S2 = {aj |aj > ai} by comparing each aj with the chosen ai
Recurse on sets S1 and S2
Output the sorted set S1 then ai and then sorted S2.
end Algorithm

A probability space consists of a universe , a collection
of subsets of known as events, and a function, P, over the events that satisfies the following
properties:
1. is an event.
2. If E is an event then E¯ is an event.
3. If E1, E2, . . . , Ek are events then iEi
is an event. (The union can be over a countable
set of events.)
4. For each event E, P(E) 0.
5. P () = 1.
6. If E1, E2, . . . , Ek are disjoint events then P (iEi) = P
i P (Ei).

The conditional probability of event E1 given that
event E2 has occurred, written P (E1|E2), is defined as
P (E1|E2) = P (E1 E2)
P (E2)
(1)
At times, we write P (E1 E2) as P (E1, E2). More generally, we write P (E1 E2 · · · En)
as P (E1, E2, · · · , En)

(Pairwise independence). Events E1, E2, . . . , En are pairwise independent if
(i, j, i 6= j)(Ei and Ej are independent ).
Definition 5 (k-wise independence). Events E1, E2, . . . , En are k-wise independent 2
k n, if for every 2 k1 k and distinct indices i1, . . . , ik1
P

Ei1 Ei2 . . . Eik1

= k1
j=1P

Eij

;
Or equivalently
P

Ei1
|Ei2 . . . Eik1

= P (Ei1
).

.