5.4The Uniform Random Variable 165
each of the subsets of sizek−1 of the numbers 2,...,nis equally likely to be the other
elements of the subset). Hence, we have that
P{I 2 = 1 |I 1 = 1 }=
k− 1
n− 1
(5.4.2)
Similarly, if element 1 is not in the subgroup, then thekmembers of the subgroup would
have been chosen “at random” from the othern−1 elements, and thus
P{I 2 = 1 |I 1 = 0 }=
k
n− 1
(5.4.3)
From Equations 5.4.2 and 5.4.3, we see that
P{I 2 = 1 |I 1 }=
k−I 1
n− 1
In general, we have that
P{Ij= 1 |I 1 ,...,Ij− 1 }=
k−
j∑− 1
i= 1
Ii
n−j+ 1
, j=2,...,n (5.4.4)
The preceding formula follows since
∑j− 1
i= 1 Iirepresents the number of the firstj−^1
elements that are included in the subset, and so givenI 1 ,...,Ij− 1 there remaink−
∑j− 1
i= 1 Ii
elements to be selected from the remainingn−(j−1).
SinceP{U < a}=a,0≤a≤1, whenUis a uniform (0, 1) random variable,
Equations 5.4.1 and 5.4.4 lead to the following method for generating a random subset
of sizekfrom a set ofnelements: Namely, generate a sequence of (at mostn) random
numbersU 1 ,U 2 ,...and set
I 1 =
1ifU 1 <
k
n
0 otherwise
I 2 =
1ifU 2 <
k−I 1
n− 1
0 otherwise
..
.
Ij=
{
1ifUj<k−In^1 −···−−j+ 1 Ij−^1
0 otherwise