Seberapa buruk asimtotis pengocokan naif?

Sudah diketahui umum bahwa algoritma 'naif' ini untuk mengocok array dengan menukar setiap item dengan item yang dipilih secara acak tidak berfungsi dengan benar:

for (i=0..n-1)
  swap(A[i], A[random(n)]);

Secara khusus, karena pada masing-masing $n$ iterasi, salah satu dari $n$ pilihan dibuat (dengan probabilitas seragam), ada $n^n$ mungkin 'jalur' melalui perhitungan; karena banyaknya permutasi yang mungkin $n!$ tidak membagi secara merata ke dalam jumlah jalur $n^n$ , tidak mungkin bagi algoritma ini untuk menghasilkan masing-masing $n!$ permutasi dengan probabilitas yang sama. (Sebagai gantinya, seseorang harus menggunakan apa yang disebut pengocok Fischer-Yates , yang pada dasarnya mengubah panggilan untuk memilih nomor acak dari [0..n) dengan panggilan untuk memilih nomor acak dari [i..n); itu bisa diperdebatkan untuk pertanyaan saya.)

Yang saya pikirkan adalah, seberapa 'buruk' shuffle naif itu? Lebih khusus lagi, membiarkan $P(n)$ menjadi himpunan semua permutasi dan $C(\rho)$ menjadi jumlah lintasan melalui algoritma naif yang menghasilkan permutasi yang dihasilkan $\rho\in P(n)$ , apa perilaku asimptotik dari fungsi tersebut

$\qquad \displaystyle M(n) = \frac{n!}{n^n}\max_{\rho\in P(n)} C(\rho)$

dan

$\qquad \displaystyle m(n) = \frac{n!}{n^n}\min_{\rho\in P(n)} C(\rho)$ ?

Faktor utama adalah 'menormalkan' nilai-nilai ini: jika shuffle naif adalah 'asimptotik baik' maka

$\qquad \displaystyle \lim_{n\to\infty}M(n) = \lim_{n\to\infty}m(n) = 1$ .

Saya menduga (berdasarkan beberapa simulasi komputer yang pernah saya lihat) bahwa nilai aktual dibatasi dari 1, tetapi apakah itu bahkan diketahui jika $\lim M(n)$ adalah terbatas, atau jika $\lim m(n)$ dibatasi dari 0? Apa yang diketahui tentang perilaku kuantitas ini?

algorithms algorithm-analysis asymptotics probability-theory randomness Steven Stadnicki
sumber

Pertanyaan yang bagus Saya tidak tahu di mana tempat terbaik untuk pertanyaan ini. Kecuali jelas bahwa forum lain lebih baik untuk itu, saya pikir Anda harus meninggalkannya di sini selama seminggu atau lebih, dan jika Anda tidak mendapatkan jawaban yang memuaskan, tanyakan di salah satu forum lain (dan letakkan tautan di kedua pertanyaan ).

Peter Shor

@ vzn "Mengapa analisis keras pada algoritma cacat dikenal?" Karena matematika itu menarik, dan Anda tidak pernah tahu di mana aplikasi lain mungkin muncul - lihat analisis Knuth tentang Bubble Sort, misalnya. Grafik Atwood memberikan analisis kualitatif kasar tentang ketidakhomogenan, tetapi itu jauh dari analisis kuantitatif matematis. (Dan ada beberapa formulasi setara yang berbeda dari pengocokan Fischer-Yates - yang saya sebutkan berfungsi dengan baik.)

Steven Stadnicki

Sebagai catatan, urutan OEIS A192053 adalah maks dan tidak mencantumkan formulir tertutup. Juga, catatan untuk entri itu menunjukkan bahwa min mungkin , menyiratkan bahwa .

C (ρ)

$C(\rho)$

C (ρ)

$C(\rho)$

2^{n - 1}

$2^{n-1}$

m (n) \to 0

$m(n) \rightarrow 0$

mhum

@ vzn Ada apa dengan pertanyaan terbuka?

Yuval Filmus

@ vzn Tidak setuju dengan kalimat terakhir Anda, ada banyak analisis tentang shuffles "tidak sempurna". Sebagai contoh, jika kita membuat transposisi acak, diketahui bahwa ambang untuk keacakan kira-kira . Pertanyaan saat ini mungkin sulit, tetapi secara apriori sulit untuk mengatakan apakah itu "sangat sulit". Jawaban seperti mhum sudah sangat memuaskan, menunjukkan bahwa pertanyaan itu sesuai untuk forum dan tidak menghadirkan penghalang yang tidak dapat diatasi (bukti formal dikesampingkan).

(1 / 2) n \log n

$(1/2) n\log n$

Yuval Filmus

Jawaban:

Kami akan menunjukkan dengan induksi bahwa permutasi adalah contoh dengan . Jika ini adalah kasus terburuk, seperti untuk beberapa pertama (lihat catatan untuk urutan OEIS A192053 ), maka . Jadi min yang dinormalisasi, seperti max yang dinormalisasi, adalah 'buruk secara eksponensial'. $\rho_n = (2,3,4,\ldots, n,1)$ $C(\rho_n) = 2^{n-1}$ $n$ $m(n) \approx (2/e)^{n}$

Kasing dasar mudah. Untuk langkah induksi, kita membutuhkan lemma:

Lemma: Di jalur mana pun dari hingga , baik gerakan pertama bertukar posisi dan , atau gerakan terakhir bertukar posisi dan . $(2,3,4, \ldots, n, 1)$ $(1,2,3, \ldots, n)$ $1$ $n$ $1$ $n$

Sketsa Bukti: Misalkan tidak. Pertimbangkan langkah pertama yang melibatkan posisi ke - . Menganggap bahwa itu adalah 'bergerak th, dan . Langkah ini harus menempatkan item di posisi ke- . Sekarang perhatikan langkah selanjutnya yang menyentuh item . Asumsikan langkah ini adalah 'bergerak th. Langkah ini harus menukar dan , memindahkan item ke tempat ', dengan . Argumen serupa mengatakan bahwa item selanjutnya hanya dapat dipindahkan ke kanan. Tapi item $n$ $i$ $i\neq 1$ $i \neq n$ $1$ $i$ $1$ $j$ $i$ $j$ $1$ $j$ $i < j$ $1$ $1$ perlu berakhir di tempat pertama, sebuah kontradiksi. $\square$

Sekarang, jika gerakan pertama menukar posisi dan , gerakan yang tersisa harus mengambil permutasi ke . Jika gerakan yang tersisa tidak menyentuh posisi pertama, maka ini adalah permutasi di posisi , dan kami tahu dengan induksi bahwa ada jalur yang melakukan ini. Argumen yang mirip dengan bukti dari Lemma mengatakan bahwa tidak ada jalan yang menyentuh posisi pertama, karena item harus berakhir di posisi yang salah. $1$ $n$ $(1, 3,4,5, \ldots, n,2)$ $(1,2,3,4, \ldots, n)$ $\rho_{n-1}$ $2 \ldots n$ $C(\rho_{n-1})=2^{n-2}$ $1$

Jika gerakan terakhir menukar posisi dan , gerakan pertama harus mengambil permutasi ke permutasi . Sekali lagi, jika gerakan ini tidak menyentuh posisi terakhir, maka ini adalah permutasi , dan dengan induksi ada jalur yang melakukannya. Dan lagi, jika salah satu dari gerakan pertama di sini menyentuh posisi terakhir, item tidak akan pernah berakhir di tempat yang benar. $1$ $n$ $n-1$ $(2,3,4,\ldots, n,1)$ $(n,2, 3,4, \ldots, n-1, 1)$ $\rho_{n-1}$ $C(\rho_{n-1})=2^{n-2}$ $n-1$ $1$

Dengan demikian, . $C(\rho_n) = 2C(\rho_{n-1}) = 2^{n-1}$

Peter Shor
sumber

Sempurna - argumen di balik lemma terlihat sangat mirip dengan yang saya miliki untuk keterlibatan sebagai satu-satunya cara untuk mendapatkan permutasi identitas, tetapi saya telah melewatkan struktur rekursif dalam swap eksplisit. Terima kasih!

Steven Stadnicki

Setelah beberapa penggalian sekitar berkat penunjuk mhum untuk OEIS, saya akhirnya menemukan analisis yang sangat baik dan argumen dasar (relatif) yang bagus (karena, sejauh yang saya tahu, untuk Goldstein dan Moews [1]) bahwa tumbuh sangat cepat di : $M(n)$ $n$

Setiap involusi dari sesuai dengan serangkaian algoritma pengocokan 'naif' yang menghasilkan permutasi identitas sebagai hasilnya, karena algoritma akan menukar dengan dan selanjutnya menukar dengan , meninggalkan keduanya tidak berubah. Ini berarti bahwa jumlah run dari algoritma yang menghasilkan permutasi identitas setidaknya jumlah involusi (pada kenyataannya, sedikit pemikiran menunjukkan bahwa korespondensi adalah 1-1 dan jadi tepat ) , dan maksimum dalam dibatasi dari bawah oleh . $\iota$ $\{1\ldots n\}$ $k$ $\iota(k)$ $\iota(k)$ $k$ $Q(n)$ $Q(n)$ $M(n)$ $Q(n)$

$Q(n)$ tampaknya menggunakan sejumlah nama, termasuk nomor telepon : lihat http://oeis.org/A000085 dan http://en.wikipedia.org/wiki/Telephone_number_%28mathematics%29 . Asimtotiknya terkenal, dan ternyata ; dari relasi rekurensi dapat secara induktif ditunjukkan bahwa rasio memenuhi dan dari sana analisis dasar mendapatkan istilah terdepan dalam asimptotik, meskipun yang lain istilah membutuhkan upaya yang lebih hati-hati. Karena 'faktor skala' $Q(n) \approx C\left(\frac{n}{e}\right)^{n/2}e^\sqrt{n}$ $Q(n) = Q(n-1)+(n-1)Q(n-2)$ $R(n) = \frac{Q(n)}{Q(n-1)}$ $\sqrt{n}\lt R(n)\lt\sqrt{n+1}$ $n^{n/2}$ $\frac{n!}{n^n}$ dalam definisi hanya tentang , istilah utama mendominasi dan menghasilkan (tanpa gejala) . $M(n)$ $C\sqrt{n}e^{-n}$ $Q(n)$ $M(n)\geq Cn^{(n+1)/2}e^{-3n/2+\sqrt{n}}$

Goldstein dan Moews sebenarnya pergi untuk menunjukkan di [1] bahwa permutasi identitas yang paling mungkin untuk besar , sehingga sebenarnya adalah dan perilaku sepenuhnya diselesaikan. Ini masih menyisakan pertanyaan tentang perilaku terbuka; Saya tidak akan terlalu terkejut jika itu juga menghasilkan analisis dalam makalah mereka, tetapi saya belum memiliki kesempatan untuk membacanya dengan cukup dekat, tetapi belum benar-benar memahami metode mereka, hanya cukup untuk memahami hasil dasarnya. $n$ $\geq$ $\approx$ $M(n)$ $m(n)$

[1] Goldstein, D. dan Moews, D .: "Identitas adalah pengocokan pertukaran yang paling mungkin untuk n besar", http://arxiv.org/abs/math/0010066

Steven Stadnicki
sumber

Tidak terlalu sulit untuk menunjukkan bahwa permutasi adalah contoh dengan . Jika ini adalah kasus terburuk, seperti untuk beberapa pertama , maka .

(2, 3, 4, \dots, n, 1)

$(2,3,4,\ldots,n,1)$

C (ρ) = 2^{n - 1}

$C(\rho) = 2^{n-1}$

n

$n$

m (n) \approx (2 / e)^{n}

$m(n) \approx (2/e)^n$

Peter Shor

@PeterShor Bisakah Anda memberikan argumen dasar? Saya merasa seperti saya kehilangan beberapa versi sederhana dari argumen involusi yang akan berhasil, tetapi saya tidak mengerti. Saya pikir bahkan jika itu tidak cukup minimal itu akan cukup baik; hitungan minimum tampaknya tidak sub-responsif dalam dan hanya mengetahui bahwa max dan min yang dinormalisasi keduanya 'secara eksponensial buruk' adalah jawaban yang cukup memuaskan.

n

$n$

Steven Stadnicki

Saya menambahkan jawaban dengan argumen ... terlalu lama untuk komentar.

Peter Shor