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")?
sumber
Jawaban:
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 =k k≥2 1/k pn n 2/(k(k-1))1/(k2) 2/(k(k−1)) . (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+1 n n n+1st (k-2)/k1/ ( k(k−12)/(k2) (k−2)/k 2/(k(k-1))1/(k2) 2/(k(k−1))
Solusinya adalah
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(k−3k−1)nk−1k k n n/kk−1kexp(−2nk−1) 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
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/k n k ϵ 0.01 1/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=2 k
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/k n k−1kN<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 .(k−1)/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=3 k=3 2n (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.k≥4
sumber
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:
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:
Ini memberi 0,407.
Menggunakan ide yang sama, kita dapat membentuk hubungan berulang, yaitu:
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
sumber
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! t A/n2t A 1/n!=A/n2t n2t/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 /n≥3 n n2t/n! n! n=52 1/52! 3,5,7,...,47 tidak, sehingga A / 52 2 t tidak dapat mengurangi ke 1 / 52 ! .1/522t A/522t 1/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+ϵ)12nlogn L2 7
sumber
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):Ini akan menghasilkan matriks
swaps
dengannumTrials+1
baris (satu per percobaan + asli) dannumElements
kolom (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
Kita mendapatkan:
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
Yang memberi kita p = 0,9926
Jika kami memeriksa semua kolom:
Dan kita lari
kita mendapatkan:
Jadi, untuk sebagian besar elemen array, metode swap Anda telah memberikan hasil yang baik, karena Anda juga dapat melihat kuartil.
Perhatikan bahwa, jelas, dengan jumlah percobaan yang lebih sedikit situasinya tidak sebaik:
50 uji coba
100 uji coba
500 uji coba
sumber
Inilah cara saya menginterpretasikan algoritme Anda, dalam kode pseudo:
sumber