2
$\begingroup$

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?

$\endgroup$

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.