Expected number of iterations for bozo sort opt algorithm
The bounds in that paper can be tightened. The tighter bounds in lemma 14 are &quot;...&quot; at most $O(n\log n)$ (resp. $O(n^2\log n))$.

As in the question and the papers, we will fix a set of $n$ elements that are totally ordered. The array $a=(a_1, a_2, \cdots, a_n)$ will be a permutation of the $n$ elements. A pair of element $\{a_i, a_j\}$ is a good pair if $i\lt j$ and $a[i]\lt a[j]$. It is a bad pair if $i\lt j$ and $a[i]\gt a[j]$. A bad pair is also call an inversion.
Fact on inversion. Swapping a bad pair strictly decreases the number of all inversions. An array is sorted if and only if the number of all inversions is 0. The maximum number of all inversions is the same as the numbers of all pairs, $\binom n2$.
Now we will use the fact above to show the tightened version of lemma 14 for one case.
The expected number of comparisons carried out by bozo-sort$_{\text{opt}}$ on a worst-case input $x$ of length $n$ is at most $4n^2\log n + (n-1)$, where $\log$ is the natural logarithm.

Proof: Suppose there are $m$ bad pairs in the array. A run of procedure rand. transpose hit one with probability $p = m/n^2$, so the expected number of runs of that procedure until we hit a bad pair is $1/p=n^2/m$. Since the number of bad pairs decreases each time we swap a bad pair, the expected number of runs of  that procedure until the array is sorted is bounded by
$$\sum_{m=1}^{\binom n2}\frac{n^2}m=n^2\sum_{m=1}^{\binom n2}\frac1m\le 2n^2\log n$$
Note that each procedure rand. transpose makes one comparison. The effect of running procedure sorted before every $n-1$ procedure rand. transpose will at most double number of comparisons besides the initial $n-1$ comparisons. Q.E.D.
The above proof is adapted from Fun sort or the chaos of unordered binary search by T. Biedl, T. Chan, E. D. Demaine, R. Fleischer, M. Golin, J.A. King, and J. I. Munro. Discrete Applied Mathematics, 144(3):231–236, 2004. 
Exercises
Exercise 1. Show that $\sum_{m=1}^{\binom n2}\frac1m\le 2\log n.$ (Hint, here is the rate of divergence of harmonic series).
Exercise 2. (One minute or less.) Show that ${m}/\binom n2$ is the probability of procedure rand. transpose in bozo-sort$^+_{\text{opt}}$ hitting one bad pair when there are $m$ bad pairs.
Exercise 3. Show that the expected number of bad pairs found (and, swapped) by a call to procedure randomly permute in bogo-sort$_{\text{opt}}$ when there are $m$ bad pairs is $\Theta(m(n-1)/n^2)$. Show the expected number of total comparisons until the array is sorted is at most by $\Theta(n^2\log n)$.