¿Cómo probar la corrección de un algoritmo aleatorio?

24

Tengo dos formas de producir una lista de artículos en un orden aleatorio y me gustaría determinar si son igualmente justos (imparciales).

El primer método que utilizo es construir la lista completa de elementos y luego barajarla (digamos barajar Fisher-Yates). El segundo método es más un método iterativo que mantiene la lista barajada en cada inserción. En pseudocódigo, la función de inserción es:

insert( list, item )
    list.append( item )
    swap( list.random_item, list.last_item )

Estoy interesado en cómo se muestra la imparcialidad de este barajado particular. Las ventajas de este algoritmo, donde se usa, son suficientes para que, aunque sea un poco injusto, esté bien. Para decidir necesito una forma de evaluar su equidad.

Mi primera idea es que necesito calcular las permutaciones totales posibles de esta manera versus las permutaciones totales posibles para un conjunto de la longitud final. Sin embargo, estoy un poco perdido en cómo calcular las permutaciones resultantes de este algoritmo. Tampoco puedo estar seguro de que este sea el mejor enfoque o el más fácil.

edA-qa mort-ora-y
fuente
Podría hacer una muestra estadística en una gran cantidad de ejecuciones de su algoritmo y compararlo con el valor esperado, o realizar algún tipo de prueba de aleatoriedad en él.
Dave Clarke
Quieres probar la distribución. ¿Está distribuido uniformemente o sesgado? Sin embargo, sospecho que tendrías que ejecutarlo muchas, muchas veces.
Dave Clarke
No tengo claro cómo haría eso. No es la aleatoriedad de los contenidos lo que busco, sino la aleatoriedad del orden. ¿Qué enfoque puede medir la distribución del pedido?
edA-qa mort-ora-y
Ah, tonto, podría usar un conjunto de entrada fijo y usar la posición final de cada elemento para obtener una distribución. Aún así, preferiría más una prueba lógica que una simulación.
edA-qa mort-ora-y
@ edA-qamort-ora-y: Tu deseo es mi comando. ;)
Raphael

Respuestas:

22

Primero, hagamos dos suposiciones quizás obvias, pero importantes:

  1. _.random_item Puede elegir la última posición.
  2. _.random_itemelige cada posición con probabilidad 1n+1 .

Para probar la exactitud de su algoritmo, necesita un argumento inductivo similar al que se usa aquí :

  • Para la lista singleton solo hay una posibilidad, por lo que se elige de manera uniforme.
  • Suponiendo que la lista con elementos fue elegida uniformemente (de todas las permutaciones), demuestre que el que tiene n + 1 elementos obtenidos por su técnica es elegido uniformemente.nn+1

De aquí en adelante, la prueba está equivocada. Consulte a continuación para obtener una prueba correcta; Dejo esto aquí porque tanto el error como los siguientes pasos (que son sólidos) pueden ser educativos.

Es útil derivar una propiedad local (es decir, en cuanto a elementos) que debe mantenerse, porque discutir sobre toda la permutación es doloroso. Observe que una permutación se elige uniformemente si cada elemento tiene la misma probabilidad de estar en cada posición, es decir

πPermnPr(L=π)=1n!i=1n j=1nPr(Li=j)=1n(1)

donde y asumimos, en aras de la simplicidad de notación, que insertamos { 1 , ... , n }n=|L|{1,,n} en la lista.

Ahora, veamos qué hace tu técnica al insertar el elemento . Tenemos que considerar tres casos (después del intercambio):n+1

  1. Uno de los elementos de la lista, no intercambiado, es decir, y j { 1 , ... , n }i{1,,n}j{1,,n}
  2. Uno de los elementos en la lista, intercambiado, es decir, y j { 1 , ... , n }i=n+1j{1,,n}
  3. El nuevo elemento, es decir, y j = n + 1i{1,,n+1}j=n+1

Para cada caso, calculamos la probabilidad de que el elemento esté en la posición i ; todos tienen que resultar ser 1ji (que es suficiente debido a(1)). Dejepn=11n+1(1) sea ​​la probabilidad de que uno de los primerosnelementos esté en cualquier posición de la lista anterior (hipótesis de inducción), yps=1pn=1nn la probabilidad de que cualquier posición sea elegida por(supuestos 1, 2). Tenga en cuenta que la clave de la lista connelementos yla elección de laposición de intercambio soneventos independientes, por lo que las probabilidades de factor de eventos conjuntos, por ejemplops=1n+1random_itemn

Pr(Li=j,i swapped)=Pr(Li=j)Pr(i swapped)=pnps

para . Ahora para los cálculos.i,j{1,,n}

  1. Solo consideramos el viejo n elementos . Tal elemento está en la posición i si y sólo si estaba allí antes de la última inserción y i no se selecciona como posición de intercambio, es decir jii

    .Pr(Li=j)=pn(1ps)=1nnn+1=1n+1

  2. Aquí consideramos que uno de los elementos antiguos se cambia a la última posición. El elemento podría haber estado en cualquiera de las posiciones anteriores, por lo que sumamos todas las probabilidades quej estuviera en la posición i e i se elija como posición de intercambio, es decirjii

    .Pr(Ln+1=j)=i=1npnps=i=1n1n1n+1=1n+1

  3. El nuevo elemento termina en la posición si y sólo si i es elegido como la posición de intercambio, es decirii

    .Pr(Li=j)=ps=1n+1

Todo salió bien, su estrategia de inserción realmente preserva la uniformidad. Por el poder de la inducción, eso prueba que su algoritmo crea permutaciones distribuidas uniformemente.

Una palabra de advertencia: esta prueba se descompone si los elementos insertados no son diferentes en pares o resp. distinguible, porque entonces la primera ecuación ya no es válida. Pero su algoritmo sigue siendo válido; cada permutación con duplicados es generada por el mismo número de ejecuciones aleatorias. Puede probar esto marcando duplicados (es decir, haciéndolos distinguibles), realice la prueba anterior y elimine las marcas (virtualmente); el último paso colapsa conjuntos de permutaciones de igual tamaño al mismo.


Como Steven ha señalado correctamente en los comentarios, la prueba anterior es fundamentalmente defectuosa como (1) no se cumple; puede construir distribuciones en el conjunto de permutaciones que cumplen el lado derecho, pero no el lado izquierdo¹.

Por lo tanto, tendremos que trabajar con probabilidades de permutaciones, lo que resulta que no es tan malo después de todo. Las suposiciones random_itemy la estructura inductiva descrita al comienzo del post permanecen en su lugar, continuamos desde allí. Dejar denotar la lista después de { 1 ,L(k)haber insertado ... , k } .{1,,k}

Deje πPermn+1 una permutación arbitraria de . Se puede escribirúnicamentecomo{1,,n+1}

π=(π(1),π(2),,π(i1),n+1,π(i+1),,π(n),π(i))

πPermni{1,,n+1}Pr(L(n)=π)=1n!random_itemi1n+1πyo

Pr(L(norte+1)=π)=Pr(L(norte)=π)Pr(yo intercambiado)=1(norte+1)!

que tuvimos que mostrar Por el poder de la inducción, eso prueba que su algoritmo crea permutaciones distribuidas uniformemente.


  1. Por ejemplo, asigne cada permutación en {(1,2,3,4),(2,3,4,1),(3,4,1,2),(4,1,2,3)} probability 14 and all others 0. There are also examples that assign every permutation a non-zero probability.
Raphael
fuente
4
'Observe that a permutation is uniformly chosen if every element has equal probability of being at each position' - this isn't true. For instance, the set of four permutations on four elements {(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3)} satisfies your constraint, but obviously isn't the set of all permutations. Unfortunately you have to use global properties of your permutation because no local conditions are enough to determine uniformity.
Steven Stadnicki