¿Qué distribución obtienes de esta mezcla aleatoria rota?

El "error común" que mencionas es barajar por transposiciones aleatorias. Este problema fue estudiado en detalle por Diaconis y Shahshahani en Generando una permutación aleatoria aleatoria transposiciones (1981). Hacen un análisis completo de los tiempos de parada y la convergencia a la uniformidad. Si no puede obtener un enlace al documento, por favor envíeme un correo electrónico y puedo enviarle una copia. En realidad es una lectura divertida (al igual que la mayoría de los artículos de Persi Diaconis).

Si el array tiene entradas repetidas, entonces el problema es ligeramente diferente. Como un plug desvergonzado, este problema más general es abordado por mí, Diaconis y Soundararajan en el Apéndice B de A Rule of Thumb for Riffle Shuffling (2011).

Digamos

• a = 1/N
• b = 1-a
• B _i (k) es la matriz de probabilidad después de iswaps para el k o elemento. es decir, la respuesta a la pregunta "¿dónde está k después de i swaps?". Por ejemplo B₀(3) = (0 0 1 0 ... 0) y B₁(3) = (a 0 b 0 ... 0). Lo que quieres es B_N (k) por cada k
• K_i es una matriz NxN con 1s en la i-ésima columna y i-ésima fila, ceros en todas partes, por ejemplo:

• I _i es la matriz de identidad pero con el elemento x=y=i puesto a cero. Por ejemplo, para i = 2:

• A _i es

Entonces

Sino porque B _N (k=1..N) forma la matriz de identidad, la probabilidad de que cualquier elemento dado i al final esté en la posición j es dada por el elemento de matriz (i,j) de la matriz:

Por ejemplo, para N = 4:

Como diagrama para N = 500 (los niveles de color son 100 * probabilidad):

El patrón es el mismo para todos N > 2:

• La posición final más probable para el k-ésimo elemento es k-1.
• La menos probable posición final es k para k , posición 1 de lo contrario

Sabía que había visto esta pregunta antes...

" ¿por qué este simple algoritmo aleatorio produce resultados sesgados? ¿cuál es una razón simple? " tiene muchas cosas buenas en las respuestas, especialmente un enlace a un blog de de Jeff Atwood sobre Coding Horror.

Como ya habrás adivinado, basado en la respuesta de @belisarius, la distribución exacta depende en gran medida del número de elementos a barajar. Aquí está la trama de Atwood para un 6-elemento baraja:

¡Qué hermosa pregunta! Ojalá tuviera una respuesta completa.

Fisher-Yates es agradable de analizar porque una vez que decide sobre el primer elemento, lo deja solo. El sesgado puede intercambiar repetidamente un elemento dentro y fuera de cualquier lugar.

Podemos analizar esto de la misma manera que lo haríamos con una cadena de Markov, describiendo las acciones como matrices de transición estocásticas que actúan linealmente sobre distribuciones de probabilidad. La mayoría de los elementos se dejan solos, la diagonal es generalmente (n-1) / n. En el paso k, cuando no se quedan solos, se intercambian con el elemento k (o un elemento aleatorio si son el elemento k). Esto es 1/(n-1) en fila o columna k. El elemento tanto en fila como en columna k es también 1/(n-1). Es bastante fácil multiplicar estas matrices juntas para que k vaya de 1 a n.

Sabemos que el elemento en el último lugar tendrá la misma probabilidad de haber estado originalmente en cualquier lugar porque el último pase intercambia el último lugar con cualquier otro. Del mismo modo, el primer elemento será igualmente probable que se coloca en cualquier lugar. Esta simetría se debe a que la transpuesta invierte el orden de la multiplicación de matrices. De hecho, la matriz es simétrica en el sentido de que la fila i es la misma que la columna (n + 1-i). Más allá de eso, los números no muestran mucho patrón aparente. Estas soluciones exactas muestran un acuerdo con las simulaciones ejecutadas por belisarius: En la ranura i, La probabilidad de obtener j disminuye a medida que j aumenta a i, alcanzando su valor más bajo en i-1, y luego saltando hasta su valor más alto valor en i, y disminuyendo hasta que j alcanza n.

En Mathematica generé cada paso con

 step[k_, n_] := Normal[SparseArray[{{k, i_} -> 1/n, 
                      {j_, k} -> 1/n, {i_, i_} -> (n - 1)/n} , {n, n}]]

(No lo he encontrado documentado en ninguna parte, pero se usa la primera regla coincidente.) La matriz de transición final se puede calcular con:

Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]]

ListDensityPlot es una herramienta de visualización útil.

Editar (por belisario)

Solo una confirmación. El siguiente código da la misma matriz que en la respuesta de @Eelvex:

step[k_, n_] := Normal[SparseArray[{{k, i_} -> (1/n), 
                      {j_, k} -> (1/n), {i_, i_} -> ((n - 1)/n)}, {n, n}]];
r[n_, s_] := Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]];
Last@Table[r[4, i], {i, 1, 4}] // MatrixForm

La página de Wikipedia en el Fisher-Yates shuffle tiene una descripción y un ejemplo de exactamente lo que sucederá en ese caso.

Puede calcular la distribución usando matrices estocásticas. Deje que la matriz A(i,j) describa la probabilidad de que la carta originalmente en la posición i termine en la posición j. Entonces el intercambio kth tiene una matriz Ak dada por Ak(i,j) = 1/N si i == k o j == k, (la carta en la posición k puede terminar en cualquier lugar y cualquier carta puede terminar en la posición k con igual probabilidad), Ak(i,i) = (N - 1)/N para todos i != k (cada otra carta permanecerá en el mismo lugar con probabilidad (N-1)/N) y todos los demás elementos cero.

El el resultado de la mezcla completa viene dado por el producto de las matrices AN ... A1.

Espero que esté buscando una descripción algebraica de las probabilidades; puede obtener una expandiendo el producto de matriz anterior, pero me imagino que será bastante complejo!

ACTUALIZACIÓN: Acabo de ver la respuesta equivalente de wnoise arriba! oops...

He investigado esto más a fondo, y resulta que esta distribución ha sido estudiada en profundidad. La razón por la que es de interés es porque este algoritmo "roto" es (o fue) utilizado en el sistema de chip RSA.

En Barajando por transposiciones semi-aleatorias, Elchanan Mossel, Yuval Peres, y Alistair Sinclair estudian esto y una clase más general de barajar. El resultado de ese papel parece ser que se necesitan log(n) barajadas rotas para lograr casi al azar distribución.

En El sesgo de tres mezclas pseudoaleatorias (Aequationes Mathematicae, 22, 1981, 268-292), Ethan Bolker y David Robbins analizan esta mezcla y determinan que la distancia de variación total a la uniformidad después de una sola pasada es 1, lo que indica que no es muy aleatoria en absoluto. También dan análisis asímpóticos.

Finalmente, Laurent Saloff-Coste y Jessica Zúñiga encontraron un buen límite superior en su estudio de las cadenas de Markov no homogéneas.

Esta pregunta está pidiendo un diagrama de matriz visual interactiva análisis de la mezcla rota mencionada. Tal herramienta está en la página ¿Se Barajará? - Por qué los comparadores aleatorios son malos por Mike Bostock.

Bostock ha creado una excelente herramienta que analiza comparadores aleatorios. En el menú desplegable de esa página, elija naïve swap (random random random) para ver el algoritmo roto y el patrón que produce.

Su página es informativa ya que permite uno para ver los efectos inmediatos que un cambio en la lógica tiene en los datos barajados. Por ejemplo:

Este diagrama de matriz usando un shuffle no uniforme y muy sesgado se produce usando un intercambio ingenuo (elegimos de "1 a N") con código como este:

function shuffle(array) {
    var n = array.length, i = -1, j;
    while (++i < n) {
        j = Math.floor(Math.random() * n);
        t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

Pero si implementamos un barajamiento no sesgado, donde elegimos de "k a N" deberíamos ver un diagrama como este:

Donde la distribución es uniforme y se produce a partir de código tales como:

function FisherYatesDurstenfeldKnuthshuffle( array ) {
    var pickIndex, arrayPosition = array.length;
    while( --arrayPosition ) {
        pickIndex = Math.floor( Math.random() * ( arrayPosition + 1 ) );
        array[ pickIndex ] = [ array[ arrayPosition ], array[ arrayPosition ] = array[ pickIndex ] ][ 0 ];
    }
}

Las excelentes respuestas dadas hasta ahora se concentran en la distribución, pero también has preguntado "¿Qué sucede si cometes este error?" - que es lo que no he visto contestado todavía, así que voy a dar una explicación sobre esto:

El algoritmo de shuffle de Knuth-Fisher-Yates elige 1 de n elementos, luego 1 de n-1 elementos restantes y así sucesivamente.

Se puede implementar con dos matrices a1 y a2 donde se elimina un elemento de a1 e insertarlo en a2, pero el algoritmo lo hace en su lugar (lo que significa, que solo necesita una matriz), como se explica aquí (Google: "Barajar Algoritmos Fisher-Yates DataGenetics") muy bien.

Si no elimina los elementos, se pueden elegir aleatoriamente de nuevo, lo que produce la aleatoriedad sesgada. Esto es exactamente lo que hace el 2do ejemplo que estás describiendo. El primer ejemplo, el algoritmo Knuth-Fisher-Yates, utiliza una variable de cursor que se ejecuta de k a N, que recuerda qué elementos ya han sido tomado, por lo tanto, evitando recoger elementos más de una vez.