Let $A = (a_1, a_2, \dots, a_n)$ denote an array of distinct values with an order defined. Consider the following randomized sorting algorithm.

  1. Let $m := 0$.
  2. Select a pair $(i, j)$ with $1 \le i < j \le n$ uniformly at random.
  3. If $a_i > a_j$, swap $a_i$ and $a_j$.
  4. If $m < m_{max}$, let $m := m + 1$ and go to step 2.

It can obviously happen that the algorithm does not completely sort the array. But if $m_{max}$ is chosen large enough, it sorts the array with high probability.

How to estimate this probability depending on $n, m_{max}$ and the number of inversions?

I have the following approach which yields only a recurrence, but no closed-form. It would be great to know at least a good bound.

Let $P(m, k)$ be the probability that the array $A$ is sorted correctly if there are $m$ iterations and $k$ inversions left. Thus, $P(m, 0) = 1$ for all $m$ and $P(0, k) = 0$ for $k > 0$. If $m, k \ge 1$, it holds

$\displaystyle P(m, k) \ge \frac{k}{\binom{n}{2}} P(m - 1, k - 1) + \left( 1 - \frac{k}{\binom{n}{2}}\right) P(m - 1, k)$,

because $k$ of $\displaystyle \binom{n}{2}$ pairs $(i, j)$ are inversions and executing step 3 of the above algorithm reduces the inversion count by at least 1. This recurrence allows us to estimate $P(m_{max}, k)$ by dynamic programming. Does anyone have a good idea to express this in closed-form or suggest another estimate?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.