随机算法 (Fall 2011)/Median Selection
The selection problem is the problem of finding the th smallest element in a set . A typical case of selection problem is finding the median.
- The median of a set is the th element in the sorted order of .
The median can be found in time by sorting. There is a linear-time deterministic algorithm, "median of medians" algorithm, which is quite sophisticated. Here we introduce a much simpler randomized algorithm which also runs in linear time.
Randomized median selection algorithm
The idea of this algorithm is random sampling. For a set , let denote the median. We observe that if we can find two elements satisfying the following properties:
- The median is between and in the sorted order, i.e. ;
- The total number of elements between and is small, specially for , .
Provided and with these two properties, within linear time, we can compute the ranks of in , construct , and sort . Therefore, the median of can be picked from in linear time.
So how can we select such elements and from ? Certainly sorting would give us the elements, but isn't that exactly what we want to avoid in the first place?
Observe that and are only asked to roughly satisfy some constraints. This hints us maybe we can construct a sketch of which is small enough to sort cheaply and roughly represents , and then pick and from this sketch. We construct the sketch by randomly sampling a relatively small number of elements from . Then the strategy of algorithm is outlined by:
- Sample a set of elements from .
- Sort and choose and somewhere around the median of .
- If and have the desirable properties, we can compute the median in linear time, or otherwise the algorithm fails.
The parameters to be fixed are: the size of (small enough to sort in linear time and large enough to contain sufficient information of ); and the order of and in (not too close to have between them, and not too far away to have sortable in linear time).
We choose the size of as , and and are within range around the median of .
Input: a set of elements over totally ordered domain.
- Pick a multi-set of elements in , chosen independently and uniformly at random with replacement, and sort .
- Let be the -th smallest element in , and let be the -th smallest element in .
- Construct and compute the ranks and .
- If or or then return FAIL.
- Sort and return the th element in the sorted order of .
"Sample with replacement" (有放回采样) means that after sampling an element, we put the element back to the set. In this way, each sampled element is independently and identically distributed (i.i.d) (独立同分布). In the above algorithm, this is for our convenience of analysis.
The algorithm always terminates in linear time because each line of the algorithm costs at most linear time. The last three line guarantees that the algorithm returns the correct median if it does not fail.
We then only need to bound the probability that the algorithm returns a FAIL. Let be the median of . By Line 4, we know that the algorithm returns a FAIL if and only if at least one of the following events occurs:
directly follows the third condition in Line 4. and are a bit tricky. The first condition in Line 4 is that , which looks not exactly the same as , but both and that are equivalent to the same event: the -th smallest element in is greater than , thus they are actually equivalent. Similarly, is equivalent to the second condition of Line 4.
We now bound the probabilities of these events one by one.
Proof. Let be the th sampled element in Line 1 of the algorithm. Let be a indicator random variable such that
It is obvious that , where is as defined in . For every , there are elements in that are less than or equal to the median. The probability that is
which is within the range of . Thus
The event is defined as that .
Note that 's are Bernoulli trials, and is the sum of Bernoulli trials, which follows binomial distribution with parameters and . Thus, the variance is
Applying Chebyshev's inequality,
By a similar analysis, we can obtain the following bound for the event .
We now bound the probability of the event .
Proof. The event is defined as that , which by the Pigeonhole Principle, implies that at leas one of the following must be true:
- : at least elements of is greater than ;
- : at least elements of is smaller than .
We bound the probability that occurs; the second will have the same bound by symmetry.
Recall that is the region in between and . If there are at least elements of greater than the median of , then the rank of in the sorted order of must be at least and thus has at least samples among the largest elements in .
Let indicate whether the th sample is among the largest elements in . Let be the number of samples in among the largest elements in . It holds that
is a binomial random variable with
Applying Chebyshev's inequality,
Symmetrically, we have that .
Applying the union bound
Combining the three bounds. Applying the union bound to them, the probability that the algorithm returns a FAIL is at most
Therefore the algorithm always terminates in linear time and returns the correct median with high probability.