Suppose we want to create a random sample of the set 1,2,3..n that is m-element
ID: 3630785 • Letter: S
Question
Suppose we want to create a random sample of the set 1,2,3..n that is m-element subset S where 0<=m<=n such that each m-subset is equally to be created.One way would be to set A{i}=i for 1,2,23...n call Randomize in place A and then just take m array elements.This method would n calls to RANDOM procedure.If n is much larger than m then we create a random sample with fewer calls to random.show that the following recursive procedure returns a random m subset S of 1,2,3..n in which each m subset is equally likely while making m calls to random.Random - sample (m,n)
if m==0
return null
else S = RANDOM -SAMPLE (m-1,n-1)
i = random(1,n)
if i belongs to S
s=s u (n)
else s = s u (i)
return s
Can i have the answer pls.
Explanation / Answer
Proof by induction on m. We'll prove the following statement holds for every m: For every n >= m, RANDOM-SAMPLE(m,n) produces a random subset of {1,...,n} of size m. Base case: If m=0 then there is only one possible subset of size m, namely the empty set, which the algorithm returns. Inductive case: Suppose for every n >= m-1, RANDOM-SAMPLE(m-1,n) produces a random subset of {1,...,n} of size m. Let p >= m be given. Let T be a random subset of {1,...,p}. We want to show that P(T) = 1/(p choose m) (where p choose m = p! / (m! (p-m)!) is the number of possible subsets of {1,...,p} of size m) (If this is true for every T then it means every T is equally likely.) Let i be the number that was chosen in the top-level call to RANDOM-SAMPLE. Let S = T - {i}. By the inductive hypothesis, P(S) = 1 / ((p-1)!/[(m-1)![(p-1)-(m-1)]!] = (m-1)!(p-m)! / (p-1)! Case 1: T contains p This means that either i was in S, or i = p. P(T) = P(i being in S) P(S) + P(i = p) P(S) = P(S)(P(i in S) + P(i = p)) = P(S)((m-1)/p) + 1/p) = P(S)(m/p) = [(m-1)!(p-m)! / (p-1)!] (m/p) = [m(m-1)!(p-m)!] / (p(p-1)!) = (m!(p-m)!] / (p!) = 1 / (p choose m) Case 2: T does not contain p Then i could have been any element of T. P(T) = sum over i in T of P(i)P(S) = sum over i in T of (1/p)((m-1)!(p-m)! / (p-1)!) = m[(1/p)((m-1)!(p-m)!/(p-1)!)] = (m(m-1)!(p-m)!) / (p (p-1)!) = (m!(p-m)!) / p! = 1 / (p choose m) This proves the inductive case.