Introduction to Probability and Statistics for Engineers and Scientists

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