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.
fuente
Respuestas:
Primero, hagamos dos suposiciones quizás obvias, pero importantes:
_.random_item
Puede elegir la última posición._.random_item
elige cada posición con probabilidadPara probar la exactitud de su algoritmo, necesita un argumento inductivo similar al que se usa aquí :
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
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
Para cada caso, calculamos la probabilidad de que el elemento esté en la posición i ; todos tienen que resultar ser 1j i (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=1n n 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+1 n
random_item
para . Ahora para los cálculos.i,j∈{1,…,n}
Solo consideramos el viejon 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 j i i
.Pr(Li=j)=pn(1−ps)=1n⋅nn+1=1n+1
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 decirj i i
.Pr(Ln+1=j)=∑i=1npnps=∑i=1n1n⋅1n+1=1n+1
El nuevo elemento termina en la posición si y sólo si i es elegido como la posición de intercambio, es deciri i
.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 suposicionesL(k) haber insertado ... , k } .{1,…,k}
random_item
y la estructura inductiva descrita al comienzo del post permanecen en su lugar, continuamos desde allí. Dejar denotar la lista después de { 1 ,Dejeπ′∈Permn+1 una permutación arbitraria de . Se puede escribirúnicamentecomo{1,…,n+1}
random_item
que tuvimos que mostrar Por el poder de la inducción, eso prueba que su algoritmo crea permutaciones distribuidas uniformemente.
fuente