Some of the students asked me again why the probability that a_i is compared with a_j is 2/(j-i+1) for any i<j.
Following is the key fact: the probability a_i is compared with a_j is equal to the probability that either a_i or a_j are the first to be chosen as the pivot among a_i, a_(i+1),..., a_(j-1), a_j.
Analyzing the probability can be also thought of a dart game: each time we throw a dart uniform randomly. If we hit i or j, we will win. If we hit any number k such that i<k<j, we will lose. If we hit a number outside the range of [i,j], then we will keep playing the game. Then the winning probability is exactly 2/(j-i+1).
I want to put an more formal specification: suppose we have an array containing a_i,a_{i+1},...a_j. We introduce an binary variable z indicating whether there is an element in [a_i, ...a_j] will be chosen in the algorithm. We denote x as whether a_i or a_j will be selected. According to definition of probability, P(x) = P(x,z=0) + P(x,z=1) = P(x|z=0)*P(z=0) + P(x|z=1)*P(z=1); Obviously, during the algorithm, there must be an element in [a_i,...a_j] be selected. Thus p(z=1) =1
ReplyDeleteP(x) = P(x|z=1). P(x=1|z=1) = 2/(j-i+1), so P(x=1)=2/(j-i+1)
by P(x) you mean P(x=1) and last line should be P(x=1) = Pr(x=1|z=1)P(z=1) ?
ReplyDeleteyes, i think so.
DeleteTo shandian, I don't think your proof is correct. The variable 'z' is trying to capture that the element you chosen is out of range [i,j]. In your argument, P(x,z=0) = 0. However, in the quick-sort procedure, you have more chance to choose element when z=0 and P(x,z=0)\neq 0. Dart game actually is an induction to proof the probability unchanged and exactly 2/(j-i+1)
ReplyDelete