A sequence of random variables $X_0 , X_1,....,X_n$ is called a martingale sequence if:
$E[X_i | X_0,X_1,....,X$i-1$]$ = $X$i-1
The text that I am reading from says the following:
Let us analyse quicksort on a fixed n input array and track the running time of quicksort algorithm Q as we go along. The expected running time varies with the choice of each pivot. Let $P_0,P_1,....,P_n$ be the choices of pivot. Let $T_0 = E[T_Q]$ be the expected running time of Q. and $T_1$ is the expected running time of Q conditioned on the first pivot choice, $T_2$ is the expected running time of Q conditioned on the first two pivot choices, and so on. In general
$T_i$ = $E [T_Q |P_0 , . . . , P$i-1$ ]$ , i ≥ 1
Also $T_n$ = $T_Q$ (I did not understand what this statement even means.)
Hence, $E[T_i |P_0 , P_1 , P_2 , . . . , Pi−1 ]$ = $T$i−1 , i > 0 Therefore the quicksort is a martingale.
Can you please explain this proof? Thanks.