Apa yang salah dengan algoritma pengocokan “naif” ini?

23

Ini adalah tindak lanjut dari pertanyaan Stackoverflow tentang mengacak array secara acak .

Ada algoritma yang sudah mapan (seperti Knuth-Fisher-Yates Shuffle ) yang harus digunakan untuk mengocok array, daripada mengandalkan implementasi ad-hoc "naif".

Saya sekarang tertarik untuk membuktikan (atau menyangkal) bahwa algoritma naif saya rusak (seperti pada: tidak menghasilkan semua permutasi yang mungkin dengan probabilitas yang sama).

Berikut algoritanya:

Ulangi beberapa kali (panjang array harus dilakukan), dan dalam setiap iterasi, dapatkan dua indeks array acak dan tukar dua elemen di sana.

Jelas, ini membutuhkan angka acak lebih banyak daripada KFY (dua kali lebih banyak), tetapi selain itu tidak berfungsi dengan baik? Dan berapa jumlah iterasi yang sesuai (cukup "panjang array")?

Thilo
sumber
4
Saya tidak bisa mengerti mengapa orang berpikir bahwa bertukar ini lebih 'sederhana' atau 'lebih naif' daripada TA ... Ketika saya memecahkan masalah ini untuk pertama kalinya saya baru saja mengimplementasikan TA (tidak tahu itu bahkan memiliki nama) , hanya karena sepertinya cara paling sederhana untuk melakukannya untuk saya.
1
@ MBb: secara pribadi, saya menemukan mereka sama mudahnya, meskipun saya setuju bahwa TA tampaknya lebih "alami" bagi saya.
nico
3
Ketika saya meneliti algoritma pengocokan setelah menulis sendiri (praktik yang sejak itu saya tinggalkan), saya semua "omong kosong, sudah dilakukan, dan memiliki nama !!"
JM bukan ahli statistik

Jawaban:

12

Itu rusak, meskipun jika Anda melakukan cukup mengocok itu bisa menjadi perkiraan yang sangat baik (seperti jawaban sebelumnya telah ditunjukkan).

Hanya untuk mengetahui apa yang terjadi, pertimbangkan seberapa sering algoritma Anda akan menghasilkan pengocokan array elemen di mana elemen pertama diperbaiki, k 2 . Ketika permutasi dihasilkan dengan probabilitas yang sama, ini harus terjadi 1 / k waktu. Biarkan p n menjadi frekuensi relatif dari kejadian ini setelah n mengocok dengan algoritma Anda. Mari kita bermurah hati, juga, dan anggaplah Anda benar-benar memilih yang berbeda pasang indeks seragam secara acak untuk mengocok Anda, sehingga setiap pasangan yang dipilih dengan probabilitas =kk21/kpnn 2/(k(k-1))1/(k2)2/(k(k1)). (Ini berarti tidak ada shuffles "sepele" terbuang. Di sisi lain, itu benar-benar merusak algoritma Anda untuk array dua elemen, karena Anda bergantian antara memperbaiki dua elemen dan menukar mereka, jadi jika Anda berhenti setelah jumlah yang telah ditentukan sebelumnya. langkah-langkah, tidak ada keacakan apapun hasilnya!)

Frekuensi ini memenuhi pengulangan sederhana, karena elemen pertama ditemukan di tempat asalnya setelah mengocok dalam dua cara terpisah. Salah satunya adalah bahwa hal itu tetap setelah mengocok dan shuffle berikutnya tidak bergerak elemen pertama. Yang lain adalah bahwa itu dipindahkan setelah mengocok tetapi shuffle memindahkannya kembali. Peluang untuk tidak memindahkan elemen pertama sama dengan = , sedangkan peluang untuk memindahkan elemen pertama sama dengan = . Dari manan n n + 1 s t ( k - 1n+1nnn+1st (k-2)/k1/ ( k(k12)/(k2)(k2)/k 2/(k(k-1))1/(k2)2/(k(k1))

p0=1
karena elemen pertama dimulai di tempat yang seharusnya;

pn+1=k2kpn+2k(k1)(1pn).

Solusinya adalah

pn=1/k+(k3k1)nk1k.

Mengurangkan , kita melihat bahwa frekuensinya salah oleh . Untuk dan , perkiraan yang baik adalah . Ini menunjukkan bahwa kesalahan dalam frekuensi khusus ini akan berkurang secara eksponensial dengan jumlah swap relatif terhadap ukuran array ( ), menunjukkan akan sulit untuk dideteksi dengan array besar jika Anda telah membuat sejumlah swap yang relatif besar --Tapi kesalahannya selalu ada.( k - 31/k knk-1(k3k1)nk1kknn/kk1kexp(2nk1)n/k

Sulit untuk memberikan analisis komprehensif tentang kesalahan di semua frekuensi. Kemungkinan mereka akan berperilaku seperti ini, yang menunjukkan bahwa setidaknya Anda perlu (jumlah swap) untuk menjadi cukup besar untuk membuat kesalahan menjadi kecil. Solusi perkiraan adalahn

n>12(1(k1)log(ϵ))

di mana harus sangat kecil dibandingkan dengan . Ini menyiratkan harus beberapa kali bahkan untuk perkiraan kasar ( yaitu , di mana berada di urutan kali atau lebih.)1 / k n k ϵ 0,01 1 / kϵ1/knkϵ0.011/k

Semua ini menimbulkan pertanyaan: mengapa Anda memilih untuk menggunakan algoritma yang tidak cukup (tetapi hanya kira-kira) benar, menggunakan teknik yang sama persis dengan algoritma lain yang terbukti benar, namun yang membutuhkan perhitungan lebih banyak?

Edit

Komentar Thilo tepat (dan saya berharap tidak ada yang akan menunjukkan hal ini, sehingga saya bisa terhindar dari pekerjaan ekstra ini!). Biarkan saya menjelaskan logikanya.

  • Jika Anda memastikan untuk menghasilkan swap yang sebenarnya setiap kali, Anda benar-benar kacau. Masalah yang saya tunjukkan untuk kasus meluas ke semua array. Hanya setengah dari semua permutasi yang mungkin dapat diperoleh dengan menerapkan bilangan swap yang genap; separuh lainnya diperoleh dengan menerapkan jumlah swap yang ganjil. Dengan demikian, dalam situasi ini, Anda tidak akan pernah bisa menghasilkan distribusi permutasi yang mendekati seragam (tetapi ada begitu banyak kemungkinan sehingga studi simulasi untuk cukup besar tidak akan dapat mendeteksi masalah). Itu sangat buruk.kk=2k

  • Oleh karena itu adalah bijaksana untuk menghasilkan swap secara acak dengan menghasilkan dua posisi secara independen secara acak. Ini berarti ada peluang setiap kali bertukar elemen dengan dirinya sendiri; yaitu, tidak melakukan apa-apa. Proses ini secara efektif sedikit memperlambat algoritme: setelah langkah, kami hanya berharap tentang benar swap telah terjadi.n k - 11/knk1kN<N

  • Perhatikan bahwa ukuran kesalahan berkurang secara monoton dengan jumlah swap yang berbeda. Oleh karena itu, melakukan lebih sedikit swap rata-rata juga meningkatkan kesalahan, rata-rata. Tapi ini adalah harga yang harus Anda bayarkan untuk mengatasi masalah yang dijelaskan dalam poin pertama. Akibatnya, perkiraan kesalahan saya konservatif rendah, kira-kira oleh faktor .(k1)/k

Saya juga ingin menunjukkan pengecualian nyata yang menarik: melihat dari dekat rumus kesalahan menunjukkan bahwa tidak ada kesalahan dalam kasus . Ini bukan kesalahan: itu benar. Namun, di sini saya telah memeriksa hanya satu statistik yang berkaitan dengan distribusi permutasi yang seragam. Fakta bahwa algoritma dapat mereproduksi statistik yang satu ini ketika (yaitu, mendapatkan frekuensi permutasi yang tepat yang memperbaiki posisi apa pun yang diberikan) tidak menjamin permutasi telah didistribusikan secara seragam. Memang, setelah swap aktual, satu-satunya permutasi yang mungkin dapat dihasilkan adalah ,k = 3 2 n ( 123 ) ( 321 ) 2 n + 1 ( 12 ) ( 23 ) ( 13 )k=3k=32n(123)(321), dan identitas. Hanya yang terakhir memperbaiki posisi apa pun yang diberikan, jadi memang sepertiga permutasi memperbaiki posisi. Tapi setengah permutasi hilang! Dalam kasus lain, setelah swap aktual, satu-satunya permutasi yang mungkin adalah , , dan . Sekali lagi, tepatnya salah satu dari ini akan memperbaiki posisi yang diberikan, jadi sekali lagi kami mendapatkan frekuensi permutasi yang benar untuk memperbaiki posisi itu, tetapi sekali lagi kami mendapatkan hanya setengah dari permutasi yang mungkin.2n+1(12)(23)(13)

Contoh kecil ini membantu mengungkap untaian utama argumen: dengan menjadi "murah hati" kami secara konservatif meremehkan tingkat kesalahan untuk satu statistik tertentu. Karena tingkat kesalahan itu bukan nol untuk semua , kita melihat bahwa algoritma rusak. Selanjutnya, dengan menganalisis peluruhan dalam tingkat kesalahan untuk statistik ini, kami menetapkan batas bawah pada jumlah iterasi dari algoritma yang diperlukan untuk memiliki harapan sama sekali tentang perkiraan distribusi permutasi yang seragam.k4

whuber
sumber
1
"Mari kita bermurah hati juga, dan anggaplah kamu benar-benar memilih pasangan indeks berbeda secara seragam secara acak untuk pengocokanmu". Saya tidak mengerti mengapa asumsi itu bisa dibuat, dan bagaimana itu murah hati. Tampaknya memang membuang permutasi yang mungkin, menghasilkan distribusi yang bahkan kurang acak.
Thilo
1
@Thilo: Terima kasih. Komentar Anda layak mendapatkan jawaban yang panjang, jadi saya menempatkannya di respons itu sendiri. Izinkan saya menunjukkan di sini bahwa menjadi "murah hati" tidak benar-benar membuang permutasi: itu hanya menghilangkan langkah-langkah dalam algoritma yang jika tidak akan melakukan apa-apa.
whuber
2
Masalah ini dapat dianalisis sepenuhnya sebagai rantai Markov pada grafik Cayley dari grup permutasi. Perhitungan numerik untuk k = 1 hingga 7 (matriks 5040 oleh 5040!) Mengkonfirmasi bahwa nilai eigen terbesar dalam ukuran (setelah 1 dan -1) persis . Ini menyiratkan bahwa sekali Anda telah mengatasi masalah bolak-balik tanda permutasi (sesuai dengan nilai eigen -1), kesalahan dalam semua probabilitas meluruh pada laju atau lebih cepat. Saya menduga ini terus berlaku untuk semua lebih besar . ( 1 - 2 / ( k - 1 ) ) n k(k3)/(k1)=12/(k1)(12/(k1))nk
whuber
1
Anda dapat melakukan jauh lebih baik daripada karena probabilitas invarian pada kelas konjugasi, dan hanya ada partisi dari sehingga Anda dapat menganalisis matriks . 5040×504015715×15
Douglas Zare
8

Saya pikir algoritme sederhana Anda akan mengocok kartu dengan benar karena pengocokan angka cenderung tak terbatas.

Misalkan Anda memiliki tiga kartu: {A, B, C}. Asumsikan bahwa kartu Anda dimulai dengan urutan sebagai berikut: A, B, C. Kemudian setelah satu pengocokan Anda memiliki kombinasi berikut:

{A,B,C}, {A,B,C}, {A,B,C} #You get this if choose the same RN twice.
{A,C,B}, {A,C,B}
{C,B,A}, {C,B,A}
{B,A,C}, {B,A,C}

Oleh karena itu, probabilitas kartu A berada di posisi {1,2,3} adalah {5/9, 2/9, 2/9}.

Jika kami mengocok kartu untuk kedua kalinya, maka:

Pr(A in position 1 after 2 shuffles) = 5/9*Pr(A in position 1 after 1 shuffle) 
                                     + 2/9*Pr(A in position 2 after 1 shuffle) 
                                     + 2/9*Pr(A in position 3 after 1 shuffle) 

Ini memberi 0,407.

Menggunakan ide yang sama, kita dapat membentuk hubungan berulang, yaitu:

Pr(A in position 1 after n shuffles) = 5/9*Pr(A in position 1 after (n-1) shuffles) 
                                     + 2/9*Pr(A in position 2 after (n-1) shuffles) 
                                     + 2/9*Pr(A in position 3 after (n-1) shuffles).

Pengodean ini dalam R (lihat kode di bawah), memberikan kemungkinan kartu A berada di posisi {1,2,3} sebagai {0,33334, 0,33333, 0,33333} setelah sepuluh mengocok.

Kode r

## m is the probability matrix of card position
## Row is position
## Col is card A, B, C
m = matrix(0, nrow=3, ncol=3)
m[1,1] = 1; m[2,2] = 1; m[3,3] = 1

## Transition matrix
m_trans = matrix(2/9, nrow=3, ncol=3)
m_trans[1,1] = 5/9; m_trans[2,2] = 5/9; m_trans[3,3] = 5/9

for(i in 1:10){
  old_m = m
  m[1,1] = sum(m_trans[,1]*old_m[,1])
  m[2,1] = sum(m_trans[,2]*old_m[,1])
  m[3,1] = sum(m_trans[,3]*old_m[,1])

  m[1,2] = sum(m_trans[,1]*old_m[,2])
  m[2,2] = sum(m_trans[,2]*old_m[,2])
  m[3,2] = sum(m_trans[,3]*old_m[,2])

  m[1,3] = sum(m_trans[,1]*old_m[,3])
  m[2,3] = sum(m_trans[,2]*old_m[,3])
  m[3,3] = sum(m_trans[,3]*old_m[,3])
}  
m
csgillespie
sumber
1
+1. Itu menunjukkan bahwa probabilitas untuk kartu yang diberikan berakhir di posisi yang diberikan mendekati rasio yang diharapkan karena jumlah pengocokan meningkat. Namun, hal yang sama juga berlaku pada algoritma yang hanya memutar array sekali dengan jumlah acak: Semua kartu memiliki probabilitas yang sama untuk berakhir di semua posisi, tetapi masih tidak ada keacakan sama sekali (array tetap diurutkan).
Thilo
@Thilo: Maaf saya tidak mengikuti komentar Anda. "Algoritma diputar dengan jumlah acak" tetapi masih "tidak ada keacakan"? Bisakah Anda menjelaskan lebih lanjut?
csgillespie
Jika Anda "mengocok" susunan elemen-N dengan memutarnya antara posisi 0 dan N-1 (secara acak), maka setiap kartu memiliki probabilitas yang persis sama untuk berakhir di posisi N mana pun, tetapi 2 masih selalu berada di antara 1 dan 3.
Thilo
1
@Thio: Ah, saya mengerti maksud Anda. Baik Anda dapat menghitung probabilitas (menggunakan ide yang persis sama seperti di atas), untuk Pr (A di posisi 2) dan Pr (A di posisi 3) - dito untuk kartu B dan C. Anda akan melihat bahwa semua probabilitas cenderung untuk 1/3. Catatan: jawaban saya hanya memberikan kasus tertentu, sedangkan @whuber jawaban yang bagus memberikan kasus umum.
csgillespie
4

Salah satu cara untuk memastikan bahwa Anda tidak akan mendapatkan distribusi seragam yang sempurna adalah dengan dapat dibagi. Dalam distribusi seragam, probabilitas setiap permutasi adalah . Ketika Anda menghasilkan urutan t transposisi acak, dan urutan kemudian mengumpulkan oleh produk mereka, probabilitas Anda dapatkan adalah dari bentuk A / n 2 t untuk beberapa bilangan bulat A . Jika 1 / n ! = A / n 2 t , lalu n 2 t / n ! = A1/n!tA/n2tA1/n!=A/n2tn2t/n!=A. Dengan Postulat Bertrand (teorema), untuk ada bilangan prima yang terjadi pada penyebut dan yang tidak membelah n , jadi n 2 t / n ! bukan bilangan bulat, dan tidak ada cara untuk membagi transposisi secara merata menjadi n ! permutasi. Sebagai contoh, jika n = 52 , maka penyebut dari 1 / 52 ! habis dibagi 3 , 5 , 7 , . . . , 47 sedangkan penyebut 1 /n3nn2t/n!n!n=521/52!3,5,7,...,47 tidak, sehingga A / 52 2 t tidak dapat mengurangi ke 1 / 52 ! .1/522tA/522t1/52!

Berapa banyak yang Anda butuhkan untuk memperkirakan permutasi acak dengan baik? Menghasilkan permutasi acak dengan transposisi acak dianalisis oleh Diaconis dan Shahshahani menggunakan teori representasi dari kelompok simetris di

Diaconis, P., Shahshahani, M. (1981): "Menghasilkan permutasi acak dengan transposisi acak." Z. Wahrsch. Verw. Geb. 57, 159–179.

Satu kesimpulan adalah bahwa dibutuhkan transposisi dalam arti bahwa setelah(1-ϵ)112nlogn(1ϵ)12nlogn(1+ϵ)12nlognL27

Douglas Zare
sumber
2

Ingatlah bahwa saya bukan ahli statistik, tetapi saya akan menaruh 2 sen saya.

Saya membuat sedikit tes di R (hati-hati, sangat lambat untuk tinggi numTrials, kode mungkin dapat dioptimalkan):

numElements <- 1000
numTrials <- 5000

swapVec <- function()
    {
    vec.swp <- vec

    for (i in 1:numElements)
        {
        i <- sample(1:numElements)
        j <- sample(1:numElements)

        tmp <- vec.swp[i]
        vec.swp[i] <- vec.swp[j]
        vec.swp[j] <- tmp
        }

    return (vec.swp)
    }

# Create a normally distributed array of numElements length
vec <- rnorm(numElements)

# Do several "swapping trials" so we can make some stats on them
swaps <- vec
prog <- txtProgressBar(0, numTrials, style=3)

for (t in 1:numTrials)
    {
    swaps <- rbind(swaps, swapVec())
    setTxtProgressBar(prog, t)
    }

Ini akan menghasilkan matriks swapsdengan numTrials+1baris (satu per percobaan + asli) dan numElementskolom (satu per setiap elemen vektor). Jika metode ini benar, distribusi setiap kolom (yaitu nilai untuk setiap elemen selama percobaan) tidak boleh berbeda dari distribusi data asli.

Karena data asli kami terdistribusi normal, kami berharap semua kolom tidak menyimpang dari itu.

Jika kita lari

par(mfrow= c(2,2))
# Our original data
hist(swaps[1,], 100, col="black", freq=FALSE, main="Original")
# Three "randomly" chosen columns
hist(swaps[,1], 100, col="black", freq=FALSE, main="Trial # 1") 
hist(swaps[,257], 100, col="black", freq=FALSE, main="Trial # 257")
hist(swaps[,844], 100, col="black", freq=FALSE, main="Trial # 844")

Kita mendapatkan:

Histogram uji coba acak

yang terlihat sangat menjanjikan. Sekarang, jika kita ingin mengkonfirmasi secara statistik distribusi tidak menyimpang dari aslinya Saya pikir kita bisa menggunakan tes Kolmogorov-Smirnov (tolong bisakah beberapa ahli statistik mengkonfirmasi ini benar?) Dan lakukan, misalnya

ks.test(swaps[1, ], swaps[, 234])

Yang memberi kita p = 0,9926

Jika kami memeriksa semua kolom:

ks.results <- apply(swaps, 2, function(col){ks.test(swaps[1,], col)})
p.values <- unlist(lapply(ks.results, function(x){x$p.value})

Dan kita lari

hist(p.values, 100, col="black")

kita mendapatkan:

Histogram dari nilai p tes Kolmogorov-Smirnov

Jadi, untuk sebagian besar elemen array, metode swap Anda telah memberikan hasil yang baik, karena Anda juga dapat melihat kuartil.

1> quantile(p.values)
       0%       25%       50%       75%      100% 
0.6819832 0.9963731 0.9999188 0.9999996 1.0000000

Perhatikan bahwa, jelas, dengan jumlah percobaan yang lebih sedikit situasinya tidak sebaik:

50 uji coba

1> quantile(p.values)
          0%          25%          50%          75%         100% 
0.0003399635 0.2920976389 0.5583204486 0.8103852744 0.9999165730

100 uji coba

          0%         25%         50%         75%        100% 
 0.001434198 0.327553996 0.596603804 0.828037097 0.999999591 

500 uji coba

         0%         25%         50%         75%        100% 
0.007834701 0.504698404 0.764231550 0.934223503 0.999995887 
nico
sumber
0

Inilah cara saya menginterpretasikan algoritme Anda, dalam kode pseudo:

void shuffle(array, length, num_passes)
  for (pass = 0; pass < num_passes; ++pass) 
    for (n = 0; n < length; ++)
      i = random_in(0, length-1)
      j = random_in(0, lenght-1)
      swap(array[i], array[j]

2×length×nkamum_halSebuahsses[0,length-1]length

length2×length×nkamum_halSebuahsses

length!length!<length2×length×nkamum_halSebuahsses

length!|length2×length×nkamum_halSebuahsses

halhal<lengthhallengthlength>2hal|length!length2×length×nkamum_halSebuahsseslength!length2×length×nkamum_halSebuahsseslength>2

lengthhal<lengthlength-1length-1length

lengthlength-1length!length!|length!. Tidak sulit untuk menunjukkan bahwa setiap jejak menghasilkan permutasi yang berbeda, dan dari sana mudah untuk melihat bahwa Fisher-Yates menghasilkan setiap permutasi dengan probabilitas yang sama.

tzs
sumber