Problem:
Let $ .5 < \alpha <1 $ be some constant. Suppose you are looking for the median element in an array using RANDOMIZED SELECT (as explained in lectures). What is the probability that after the first iteration the size of the subarray in which the element you are looking for lies is $ \le \alpha $ times the size of the original array?
Solution:
Let the size of the array be $ N $. The pivot is the xth number in the sorted array.
Then as long as $ (1-\alpha) N < x < \alpha N $, then the median will be in the array smaller than of equals to $ \alpha N $.
If this is a little abstract, see this, suppose $ \alpha = 0.7 $ and the array has 10 elements, then as long as the pivot is the 4th, 5th, 6th, 7th element (array index start with 1), we should be fine as the array containing the median has length at most 6.
Now the question becomes what is the probability of the pivot lying in that range, the answer is simply $ p = 1 - (1 - \alpha) - (1 - \alpha) $ (i.e. the whole range minus the forbidden ones), simplifying, we get $ p = 2 \alpha - 1 $, and that is the answer.
Let $ .5 < \alpha <1 $ be some constant. Suppose you are looking for the median element in an array using RANDOMIZED SELECT (as explained in lectures). What is the probability that after the first iteration the size of the subarray in which the element you are looking for lies is $ \le \alpha $ times the size of the original array?
Solution:
Let the size of the array be $ N $. The pivot is the xth number in the sorted array.
Then as long as $ (1-\alpha) N < x < \alpha N $, then the median will be in the array smaller than of equals to $ \alpha N $.
If this is a little abstract, see this, suppose $ \alpha = 0.7 $ and the array has 10 elements, then as long as the pivot is the 4th, 5th, 6th, 7th element (array index start with 1), we should be fine as the array containing the median has length at most 6.
Now the question becomes what is the probability of the pivot lying in that range, the answer is simply $ p = 1 - (1 - \alpha) - (1 - \alpha) $ (i.e. the whole range minus the forbidden ones), simplifying, we get $ p = 2 \alpha - 1 $, and that is the answer.
This comment has been removed by the author.
ReplyDeleteThanks a lot for this explanation. However I am still finding it hard to understand.. :(
ReplyDeleteWhy there are two forbidden ones (1−α) and (1−α)
I think I have got this..... if alpha is 0.75 the pivot element element choosen for an array of length 100 shouldn't be in the first 25 nor in the last 25
ReplyDelete