20. Consider the following procedure for randomly choosing a subset of size k from the numbers 1, 2, . . . , n: Fix p and generate the first n time units of a renewal process whose interarrival distribution is geometric with mean 1/p—that is, P{interarrival time=k}=p(1 − p)k−1, k=1, 2, . . .. Suppose events occur at times i1 < i2 < · · · < im  n. If m = k, stop; i1, . . . , im is the desired set. If m > k, then randomly choose (by some method) a subset of size k from i1, . . . , im and then stop. If m < k, take i1, . . . , im as part of the subset of size k and then select (by some method) a random subset of size k−m from the set {1, 2, . . . , n}−{i1, . . . , im}.

Explain why this algorithm works. As E[N(n)] = np a reasonable choice of p is to take p ≈ k/n. (This approach is due to Dieter.)