Consider modifying the Partition procedure of Quicksort by randomly picking three elements from array $A$ and use the median of the three elements as the pivot. What is the exact probability (not asymptotic form) of getting a split with the sizes of both subarrays are at least $|A|/4$?
Assumption:$|A|$ is divisible by $4$ and the pivot element does not count as an element in any one of the two subarrays after the partition
I somehow can find the solution by using summation and product notation. However, is there any method that can find the solution without using summation and product notation?
Let $|A|=4k$.
The subarray of everything smaller than the pivot will have fewer than $k$ elements exactly when the pivot is one of the $k$ smallest elements of the array. This, in turn, happens, when at least $2$ of the $3$ elements we picked are among the $k$ smallest elements.
This happens with probability $$\frac{\binom k3}{\binom{4k}{3}} + \frac{\binom k2 \binom{3k}{1}}{\binom{4k}{3}}.$$ The first fraction is the probability of choosing $3$ elements from the $k$ smallest, and the second fraction is the probability of choosing exactly $2$ elements from the $k$ smallest, and one from the other $3k$.
The expression doesn't really simplify as such, but we can write it as $\frac{5}{32} - \frac{3}{16(2k-1)} + \frac{3}{32(4k-1)}$ to make it clear what its limit is.
Finally, if the above probability is $p$, we want $1-2p$ as our final answer: we want to exclude the event above, as well as the symmetric event that the other subarray will be small. This gives us a final answer of $$ \frac{11}{16} + \frac{3}{8(2k-1)} - \frac{3}{16(4k-1)}. $$