5.3 Randomized algorithms

5.3-1

Professor Marceau objects to the loop invariant used in the proof of Lemma 5.4. He questions whether it holds prior to the first iteration. He reasons that we could just as easily declare that an empty subarray contains no 0-permutations. Therefore, the probability that an empty subarray contains a 0-permutation should be 0, thus invalidating the loop invariant prior to the first iteration. Rewrite the procedure RANDOMLY-PERMUTE so that its associated loop invariant applies to a nonempty subarray prior to the first iteration, and modify the proof of Lemma 5.4 for your procedure.

RANDOMLY-PERMUTE-MODIFIED(A,n)
    swap(A[1], A[RANDOM(1, n)])
    for i = 2 to n
        swap(A[i], A[RANDOM(i, n)])

Modify the proof of Lemma by starting with $i=2$ instead of $i=1$. This resolves the the issue of 0-permutations.

5.3-2

Professor Kelp decides to write a procedure that produces at random any permutation except the identity permutation, in which every element ends up where it started. He proposes the procedure PERMUTE-WITHOUT-IDENTITY. Does this procedure do what Professor Kelp intends?

PERMUTE-WITHOUT-IDENTITY(A,n)
  for i D 1 to n - 1
      swap A[i] with A[RANDOM(i+1,n)]

No, some non-identity permutation like $$ can not be produced.

5.3-3

Consider the PERMUTE-WITH-ALL procedure on the facing page, which instead of swapping element $A[i]$ with a random element from the subarray $A[i:n]$, swaps it with a random element from anywhere in the array. Does PERMUTE-WITH-ALL produce a uniform random permutation? Why or why not?

PERMUTE-WITH-ALL(A,n)
  for i = 1 to n
      swap A[i] with A[RAMDOM(1,n)]

There are $n^{n}$ possible results produced by this procedure with same probability, but there are $n!$ distinct permutation. if $n^{n}\equiv n!$ (mod 3) does not hold, n! permutation can not have equal probability. For instance, if $n=3$, there are 27 results, but there are 6 permutation, they can not have eqaul probability.

5.3-4

Professor Knievel suggests the procedure PERMUTE-BY-CYCLE to generate a uniform random permutation. Show that each element $A[i]$ has a $1/n$ probability of winding up in any particular position in $B$. Then show that Professor Knievel is mistaken by showing that the resulting permutation is not uniformly random.

PERMUTE-BY-CYCLE(A,n)
let B[1:n] ne a new array
offset = RAMDOM(1,n)
for i = 1 to n
  dest = i + offset
  if dest > n
      dest = dest - n
  B[dest] = A[i]
return B

$A[i]$ winds up in $B[dest]$, $dest=(i+offset)\% n$. For a position $j$, the probability that $j=dest$ is the probability that $j=(i+RAMDOM(1,n))\% n$, which is 1/n.

The resulting permutation is not uniformly since the procedure can not produce peimutation like $$.

5.3-5

Professor Gallup wants to create a random sample of the set {1,2,3,...,n}, that is, an $m$-element subset S, where $0 \leq m \leq n$, such that each $m$-subset is equally likely to be created. One way is to set $A[i] = i$, for $i = 1,2,3...,n$, call RANDOMLY-PERMUTE(A), and then take just the first m array elements. This method makes n calls to the RANDOM procedure. In Professor Gallup’s application, n is much larger than m, and so the professor wants to create a random sample with fewer calls to RANDOM.

RANDOM-SAMPLE(m,n)
S = Ø
for k = n - m + 1 to n
  i = RANDOM(1,k)
  if i ∈ S
      S = S ∪ {k}
  else
      S = S ∪ {i}
return S

Show that the procedure RANDOM-SAMPLE on the previous page returns a random $m$-subset S of {1,2,3,...,n}, in which each $m$-subset is equally likely, while making only $m$ calls to RANDOM.

Loop invariant: At the start of $i$th $(k=n-m+i)$ iteration, each $(i-1)$-subset of the set ${1,2,...,n-m+i-1}$ is equally likely.

Initialization: $0$-subset, that is, $\emptyset$, is equally likely.

Maintenance: Since each $(i-1)$-subset is eqaully likely, that is, each one's probability is $1/ {{n-m+i-a}\choose{i-1}}$. After the $i$th iteration the probability of each $i$-subset with $n-m+i(k)$ is $\frac{1}{{n-m+i-1}\choose{i-1}}\cdot \frac{i}{n-m+i}=1/{{n-m+i}\choose{i}}$. Since each of others must have same probability, the sum of the probability of all subset is 1, and there are $n-m+i\choose i$ subset, the probability of each of others must be $n-m+i\choose i$.

Termination: when $k = n(i=m)$, the loop terminates. The probability of each subset is $n\choose m$, equally likely.

Obviouly, all $m$-subset is possible, and according to the loop invariant, we can prove the procedure returns a random $m$-subset S.