7.4-6

Consider modifying the PARTITION procedure by randomly picking three elements from array A and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst an $\alpha-to(1 -\alpha)$ split, as a function of ˛ in the range $0 < \alpha < 1.$

Let A (resp, B, C) denote the subset of elements in the positions range $[0, \alpha n)$ (resp. $[ \alpha n, n- \alpha n]$,$(n - \alpha n, n])$,
We analyze the possible cases in which the median gives a valid (i.e. $ \alpha -to-(1 - \alpha )$) partition and calculate their respective probabilities.
Pr[One element from each of A,B and C] = $3! . \alpha^ 2(1 - 2 \alpha )$
Pr[One element from A, and two elements from B] = $(3/2) \alpha (1 - 2 \alpha)^2$
Pr[One element from C and two elements from B] = $(3/2) \alpha (1 - 2 \alpha)^2$
Pr[All three elements from B] = $(1 - 2 \alpha )^3$
The probability of a valid partition is just the sum of the above terms.