Aparentemente, para barajar un mazo de cartas de modo que todas las permutaciones se puedan realizar de forma equitativa, pase por el mazo en orden e intercambie la tarjeta actual por tarjetas que no aparecen antes que la tarjeta actual.
También, aparentemente, si uno simplemente intercambia tarjetas de forma aleatoria, no todas las permutaciones de las tarjetas tienen la misma probabilidad de resultar de la mezcla. ¿Por qué es este el caso?
Si cambiamos la parte superior de la tarjeta con una tarjeta elegida de forma aleatoria con una distribución uniforme (incluyendo la propia tarjeta, en cuyo caso el "swap" no cambia nada), entonces la nueva tapa de la tarjeta es cualquiera de las tarjetas con la misma probabilidad. Así, cada tarjeta también tiene la misma probabilidad de no ser de la tarjeta, es decir, de estar en el subdeck debajo de la parte superior de la tarjeta. Así, la cubierta será debidamente barajan, si el resto del procedimiento correctamente baraja que subdeck. Pero el resto del procedimiento es, precisamente, todo el procedimiento aplicado para que subdeck, por lo que el resultado de la siguiente manera por inducción, el caso base de ser un mazo de $1$ tarjeta, que es siempre bien mezclado.
Para la segunda parte de la pregunta, como Lopsy escribió, usted tendría que decir más acerca de lo que significa "al azar intercambio de tarjetas".
He aquí un argumento que el otro método - donde usted puede escoger el intercambiado de la tarjeta desde cualquier parte de la cubierta que tiene un sesgo.
Digamos que el original de la última carta de la baraja es el As de Espadas. Echemos un vistazo a la probabilidad de que, utilizando el método revisada donde elegimos la intercambiado tarjeta de toda la cubierta, de que el As de Espadas termina en la parte superior de la cubierta.
Para que esto suceda, tenemos que elegir el As de Espadas como el intercambiado de la tarjeta de primero y, a continuación, nunca otra vez, O nunca hasta el final y, a continuación, swap con la primera tarjeta. La probabilidad de que este es
$2 \times \large \frac{1}{52} \times \frac{51}{52}^{51}$.
El poder en que la expresión es acerca de $1/e$, por lo que la posibilidad de que el As de Espadas, terminando en la parte superior de la cubierta es $2/e$ o $.736$, los tiempos de lo que debería ser. Esto no es sólo una minúscula fracción lejos de la igualdad de la distribución de este método de revolver tiene una cantidad estadísticamente significativa de sesgo. En otras palabras, usted no me coge jugando al poker con alguien arrastrando los pies como este.
Supongamos que usted tiene una baraja de cartas y una tabla con 52 ranuras para el barajado las cartas.
Cuando usted hace el Fischer Yates, que son, básicamente, hacer esto:
Seleccione una carta al azar, lo puso en la ranura $1$.
Del resto de las $5$1, seleccione otra carta al azar, lo puso en la ranura $2$ y continuar.
La gente generalmente se confunden con Fischer Yates, debido a que las implementaciones suelen utilizar la baraja de cartas (la matriz de entrada) como el conjunto de ranuras de sí mismo, y el acto de poner una tarjeta en una ranura se realiza mediante el intercambio de cartas (los elementos de la matriz de entrada). Esto es hecho para hacer que el algoritmo de $\mathcal{O}(n)$ en la matriz de entrada de caso (básicamente, el 'get carta al azar", se convierte en $\mathcal{O}(1)$).
La probabilidad de que la tarjeta de $j$ va en la ranura $k$ está dada por (donde $n=52$)
$$\frac{n-1}{n}\cdot \frac{n-2}{n-1} \cdots \frac{n-k+1}{n-k+2} \cdot \frac{1}{n-k+1} = \frac{1}{n}$$
(lo anterior se calcula: no entra en las ranuras $1$ a $k-1$ y va en la ranura $k$).
Cada tarjeta es igualmente probable como cualquier otra tarjeta de terminar en una casilla determinada.
Así, dados dos permutaciones $A$ e $B$, ambas tienen la misma probabilidad de ocurrir.
Nota: Usted podría pensar que la probabilidad de obtener un determinado permutación es $\frac{1}{n^n}$ (o $\frac{1}{n^{n-1}}$) basadas en la probabilidad de $\frac{1}{n}$, pero no lo es. Se puede decir por qué?
Otro rápido heurística explicación de por qué el 'en cada etapa, de intercambio de la tarjeta de $i$, con una carta al azar de $1..n$' mecanismo no funciona: en cada paso (de $n$ pasos) de que estás eligiendo una de las $n$ opciones, independientemente de cualquier otra opción que se ha realizado; en otras palabras, hay $n^n$ diferentes rutas de ejecución para el algoritmo a seguir, cada uno de los cuales tiene la misma probabilidad. Pero no son exactamente $n!$ diferentes maneras en que su cubierta se puede barajan, y cada uno de ellos tiene que ser producido con igual probabilidad por su algoritmo; desde $n!$ no divide $n^n$, esto es imposible - el algoritmo tendrá que generar algunas permutaciones con una mayor probabilidad que otros.
Esto también explica (aproximadamente) de por qué la aleatorización de Fisher-Yates obras; en el primer paso hay un uno-de-$n$ elección que se hizo, en el segundo paso (independiente), uno-de-$(n-1)$, etc, así que al final hay $n\cdot(n-1)\cdot\ldots\cdot 1 = n!$ diferentes rutas de ejecución, cada uno de los cuales corresponde de forma exclusiva a uno de los posibles permutaciones.
Edificio en Lopsy comentario
Si no $n$ random swaps, entonces hay $\frac{52 \times 51}{2}=1326$ igualmente posibles acciones en cada turno, por lo que la probabilidad de cada posible resultado final se expresa como una fracción racional en términos mínimos debe tener un denominador que divide $1326^n$. Desde $1326=2 \times 3 \times 13 \times 17$, sólo estos números primos se puede dividir el denominador.
Pero desea que la fracción a se $\frac{1}{52!}$ porque desea que todas las permutaciones son igualmente probables, y este denominador también incluye los números primos $5,7,11,19,23,29,31,37,41,43,47$. Así que para finito $n$ usted no puede conseguir esta fracción exacta.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
