No puedo responder con argumentos solidos y matematicos, pero para mi en la primera solución le estas dando mucha importancia a los primeros elementos en desmedro de los ultimos. Si en la primera vez la posibilidad de que el elemento se quede en donde mismo es 1/2 y la posibilidad de irse al final es tambien 1/2, lo malo que veo, es que en la 2da vuelta, el primer elemento puede volver a ser el primero con la misma probabilidad y por tanto, en el fondo vuelve a ser probable que se quede alli.
Si el elemento que está al ultimo tuviera voz, seguro reclamaría que el no tiene casi ninguna posiblidad de ser removido de su lugar, mientras que el primero siempre tiene varias alternativas de serlo. Lo que no sabe este ultimo es que el primero también esta sufriendo del mismo problema, vale decir, tiene mucha probabilidad de quedarse donde mismo.
No sé si es esto lo que ocurre finalmente, o sea, pocos movimientos, pero eso intuyo que pasa. ¿Pasa esto?
Finalmente, no es exactamente lo que haces, pero al menos tiene relación: randomizar "mal" es un clásico problema y Knuth presenta la manera adecuada de hacerlo: intercambiar el elemento i-esimo con el mismo o con cualquiera de los que les sigue.
Ver mas
en este link:
http://goo.gl/IXln1l.