<p>I've looked into this further, and it turns out that this distribution has been studied at length. The reason it's of interest is because this "broken" algorithm is (or was) used in the RSA chip system.</p>

<p>In <a href="http://arxiv.org/abs/math.PR/0404438" rel="nofollow">Shuffling by semi-random transpositions</a>, Elchanan Mossel, Yuval Peres, and Alistair Sinclair study this and a more general class of shuffles. The upshot of that paper appears to be that it takes <code>log(n)</code> broken shuffles to achieve near random distribution.</p>

<p>In <em>The bias of three pseudorandom shuffles</em> (<em>Aequationes Mathematicae</em>,  22, 1981, 268-292), Ethan Bolker and David Robbins analyze this shuffle and determine that the total variation distance to uniformity after a single pass is 1, indicating that it is not very random at all. They give asympotic analyses as well.</p>

<p>Finally, Laurent Saloff-Coste and Jessica Zuniga found a nice upper bound in their study of inhomogeneous Markov chains. </p>
What distribution do you get from this broken random shuffle?
<p>The famous Fisher-Yates shuffle algorithm can be used to randomly permute an array A of length N:</p>

<pre><code>For k = 1 to N
    Pick a random integer j from k to N
    Swap A[k] and A[j]
</code></pre>

<p>A common mistake that I've been told over and over again not to make is this:</p>

<pre><code>For k = 1 to N
    Pick a random integer j from 1 to N
    Swap A[k] and A[j]
</code></pre>

<p>That is, instead of picking a random integer from k to N, you pick a random integer from 1 to N.</p>

<p>What happens if you make this mistake?  I know that the resulting permutation isn't uniformly distributed, but I don't know what guarantees there are on what the resulting distribution will be.  In particular, does anyone have an expression for the probability distributions over the final positions of the elements?</p>