I am reading about usage of Chernoff bounds for bounding number of comparisons in a randomized Quicksort from here. What is proved is that ($n$ is number of elements in the array) $$\Pr[\text{Number of comparisons} \le 32\ln{n}] \ge 1-\frac{1}{n}$$
To prove this, the following is proved
For an arbitrary element $z$ in the array if we look at the first $32\ln{n}$ intervals containing it, then with high probability $4\ln{n}$ of those intervals were partitioned in a balanced way.
So the the first partition containing $z$ is the complete array, lets call it $S_1$. An interval $S_{i}$ (contains $z$) is said to be partitioned in a balanced way if $|S_{i+1}| \le \frac{3}{4}|S_{i}|$ and $|S_{i}\backslash S_{i+1}| \le \frac{3}{4}|S_{i}|$.
It is the argued that the events $Y_i$, where $Y_i=1$ if $S_i$ was partitioned in a balanced way and $0$ otherwise, have the following properties
- $\Pr[Y_i]=\frac{1}{2}$.
- $Y_i$ are independent.
I have the following doubts:
- Why is $\Pr[Y_i]=\frac{1}{2}$ ? If one takes $n=4$ then taking any element as pivot gives a balanced partition. I can see that if $n \to \infty$, then the result will hold. But wouldn't it be wrong to use that, as at one point we would be arguing that the interval containing $z$ with good probability will hit a singleton interval (so interval size becomes small and $1$ ultimately) and on the other hand we would be assuming $|S_i| \to \infty $ as $n \to \infty$. Or is there something else trivial I am missing ?
- I am also unable to see why they are independent events. If probabilities of $Y_i$ are dependent on $|S_i|$ then they might not be independent, as $Y_j=1$ might reveal some additional information about value of $Y_i$. Though I am unable to formally prove or disprove it.