Probabilidade de uma rede de classificação aleatória funcionar

14

Dado entradas , construímos uma rede de ordenação aleatória com portões por iterativamente colheita duas variáveis com e adicionando um portão comparador que eles se permutas .x 0 , , x n - 1 m x i , x j i < j x i > x jnx0,,xn1mxi,xji<jxi>xj

Pergunta 1 : Para fixo , qual deve ser o tamanho da rede para classificar corretamente com probabilidade ?m > 1nm>12

Temos pelo menos o limite inferior m=Ω(n2logn) pois uma entrada que é classificada corretamente, exceto que cada par consecutivo é trocado, levará tempo Θ(n2logn2) para cada par a ser escolhido como comparador. Esse também é o limite superior, possivelmente com mais logn fatores?

Pergunta 2 : Existe uma distribuição de portas do comparador que atinge m=O~(n) , talvez escolhendo comparadores próximos com maior probabilidade?

Geoffrey Irving
fonte
1
Eu acho que alguém pode obter um limite superior de O(n3logO(1)) olhando uma entrada de cada vez e depois delimitando a união, mas isso parece longe de ser apertado.
Daniello #
2
Idéia para a pergunta 2: escolha uma rede de classificação de profundidade O(log2n) . Em cada etapa, escolha aleatoriamente um dos portões da rede de classificação e faça essa comparação. Após O~(n) etapas, todos os portões na primeira camada serão aplicados. Após outras etapas O~(n) , todos os portões na segunda camada serão aplicados. Se você puder mostrar que isso é monotônico (inserir comparações extras no meio da rede de classificação não pode prejudicar), você obteve uma solução com comparadores O~(n) no total, em média. Não tenho certeza se a monoticidade realmente é válida.
DW
2
@ DW: A monotonicidade não é necessariamente válida. Considere as seqüências sequência funciona; s ' não (considere a entrada (1, 0, 0)). A idéia é que (x_0, x_2), (x_0, x_1) classifique qualquer entrada que receba, exceto (0, 1, 0) (veja aqui ). Em s , essa entrada não pode alcançar (x_0, x_2), (x_0, x_1) . Em ' pode. ss(x0,x2),(x0,x1)(0,1,0)
s=(x1,x2),(x0,x2),(x0,x1);s=(x1,x2),(x0,x1),(x0,x2),(x0,x1).
ss(x0,x2),(x0,x1)(0,1,0)( x 0 , x 2 ) , ( x 0 , x 1 ) s s(x0,x2),(x0,x1)s
Neal Young
3
Considere a variante em que a rede é escolhida escolhendo duas variáveis adjacentes aleatoriamente em cada etapa. Agora a monotonicidade se mantém (como swaps adjacentes não criam inversões). Aplique a idéia de @ DW a uma rede de classificação ímpar-par , que possui rodadas: em rodadas ímpares, ele compara todos os pares adjacentes onde é ímpar; nas rodadas pares, ele compara todos os pares adjacentes onde é par. Quando a rede aleatória está correta nas comparações , pois "inclui" esta rede. (Ou estou faltando alguma coisa?) n i i O ( n 2 log n )xi,xi+1niiO(n2logn)
Neal Young
2
Monotonicidade de redes adjacentes: Dado , para defina . Diga se ( ). Corrija qualquer comparação " ". Deixe- e vêm de e fazendo essa comparação. Reivindicação 1. e . Reivindicação 2: se , então . Então mostre indutivamente: se j { 0 , 1 , , n } s j ( a ) = j i = 1 a i a b s j ( a ) s j ( b ) j x i < x i + 1 a b a,b{0,1}nj{0,1,,n}sj(a)=i=1jaiabsj(a)sj(b)jxi<xi+1abb um 'um b 'b um b um 'b ' y s x y ' s ' s x y 'y y y 'ab aabb ababyé o resultado da sequência de comparação na entrada , e é o resultado da super-sequência de em , então . Portanto, se é classificado, o mesmo é . sxyssxyyyy
Neal Young

Respostas:

3

Aqui estão alguns dados empíricos para a pergunta 2, com base na ideia de DW aplicada à classificação bitônica. Para variáveis, escolha com probabilidade proporcional a , depois selecione uniformemente aleatoriamente para obter um comparador . Isso corresponde à distribuição dos comparadores em classificação bitônica se for uma potência de 2 e, caso contrário, será aproximada.j - i = 2 k lg n - k i ( i , j ) nnji=2klgnki(i,j)n

Para uma determinada sequência infinita de portas extraídas dessa distribuição, podemos aproximar o número de portas necessárias para obter uma rede de classificação, classificando muitas seqüências aleatórias de bits. Aqui está a estimativa para tendo a média de mais de sequências de gate com sequências de bits usadas para aproximar a contagem: parece corresponder a , a mesma complexidade que a classificação bitônica. Nesse caso, não comemos um fator extra devido ao problema do coletor de cupons de encontrar cada porta.100 6400 Θ ( n log 2 n ) log nn<2001006400Número aproximado de portõesΘ(nlog2n)logn

Para enfatizar: estou usando apenas seqüências de bits para aproximar o número esperado de portas, não . As portas médias necessárias aumentam com esse número: para se eu usar as seqüências , e , as estimativas são , e . Assim, é possível que as últimas seqüências aumentem a complexidade assintótica, embora, intuitivamente, pareça improvável.64002nn=19964006400064000014270±106914353±101314539±965

Edit : Aqui está um gráfico semelhante até , mas usando o número exato de portas (calculado através de uma combinação de amostragem e Z3). Eu mudei da potência de dois para arbitrário com probabilidade proporcional a . ainda parece plausível.n=80d=jid[1,n2]lognlogddΘ(nlog2n)

Número exato de portões

Geoffrey Irving
fonte
2
Boa experiência! Existe uma maneira diferente de o problema do coletor de cupons aparecer aqui: você está apenas amostrando uma pequena fração das seqüências de bits necessárias para verificar a correção em todas as entradas. Parece que podemos concluir (cientificamente, não matematicamente, é claro) a partir de seu experimento que uma rede aleatória desse tipo e tamanho classifica uma permutação aleatória whp. Eu também ficaria curioso para ver testes exaustivos de nessas redes aleatórias para todos os até os quais você está disposto a ir. ( não deve ser tão ruim, talvez até dependendo do idioma e hardware que você está usando). 2n2nnn=20n=30
Joshua Grochow
1
Parece o mesmo para exatos até , mas não vejo isso como conclusivo. n=27
Geoffrey Irving
1
@ JoshuaGrochow: Adicionei valores exatos até . n=80
Geoffrey Irving
1
Agradável! Parece haver uma propagação crescente para os dados exatos, o que talvez indica um limite superior com um fator extra de ? (Isto é, se o "spread" está crescendo a uma taxa de log n .)lognlogn
Joshua Grochow
1
Sim, não podemos descartar um fator extra. Eu ficaria surpreso se fosse , no entanto, uma vez que em 80 temos lg n 6 e a constante é suspeitamente próxima de caso contrário. Nesse ponto, acho que a teoria precisa assumir o controle. :)lognlgn61
Geoffrey Irving