Bagaimana cara membuktikan kebenaran algoritma shuffle?

Saya memiliki dua cara untuk menghasilkan daftar item dalam urutan acak dan ingin menentukan apakah mereka sama adil (tidak bias).

Metode pertama yang saya gunakan adalah untuk membangun seluruh daftar elemen dan kemudian melakukan pengocokan (katakanlah Fisher-Yates shuffle). Metode kedua lebih merupakan metode berulang yang membuat daftar terseret di setiap penyisipan. Dalam pseudo-code, fungsi penyisipan adalah:

insert( list, item )
    list.append( item )
    swap( list.random_item, list.last_item )

Saya tertarik pada bagaimana seseorang menunjukkan keadilan dari pengocokan khusus ini. Kelebihan dari algoritma ini, di mana digunakan, cukup bahwa meskipun sedikit tidak adil itu akan baik-baik saja. Untuk memutuskan saya perlu cara untuk mengevaluasi keadilannya.

Gagasan pertama saya adalah bahwa saya perlu menghitung permutasi total yang mungkin dengan cara ini versus total permutasi yang mungkin untuk satu set panjang akhir. Namun saya sedikit bingung bagaimana cara menghitung permutasi yang dihasilkan dari algoritma ini. Saya juga tidak dapat memastikan ini adalah pendekatan terbaik, atau termudah.

Pertama, mari kita buat dua asumsi yang jelas, tetapi penting:

1. _.random_item dapat memilih posisi terakhir.
2. _.random_itemmemilih setiap posisi dengan probabilitas .$\frac{1}{n+1}$

Untuk membuktikan kebenaran algoritme Anda, Anda memerlukan argumen induktif yang mirip dengan yang digunakan di sini :

• Untuk daftar tunggal hanya ada satu kemungkinan, jadi itu dipilih secara seragam.
• Dengan asumsi bahwa daftar dengan elemen dipilih secara seragam (dari semua permutasi), tunjukkan bahwa daftar dengan elemen yang diperoleh dengan teknik Anda dipilih secara seragam.n + $n$$n+1$

^{Dari sini, buktinya salah. Silakan lihat di bawah untuk bukti yang benar; Saya meninggalkan ini di sini karena kesalahan dan langkah-langkah berikut (yang masuk akal) mungkin mendidik.}

Berguna untuk mendapatkan properti lokal (yaitu elemen-bijaksana) yang harus dimiliki, karena memperdebatkan seluruh permutasi adalah menyakitkan. Perhatikan bahwa permutasi dipilih secara seragam jika setiap elemen memiliki probabilitas yang sama untuk berada di setiap posisi, yaitu

$\qquad \displaystyle \mathop{\forall}\limits_{\pi \in \mathrm{Perm}_n} \operatorname{Pr}(L = \pi) = \frac{1}{n!} \quad \Longleftrightarrow \quad \mathop{\forall}\limits_{i=1}^n\ \mathop{\forall}\limits_{j=1}^n \operatorname{Pr}(L_i = j) = \frac{1}{n} \qquad (1)$

dimana dan kami mengasumsikan demi kesederhanaan notasi yang kami masukkan { 1 , ... , n } ke dalam daftar.$n = |L|$$\{1,\dots,n\}$

Sekarang, mari kita lihat apa teknik Anda lakukan ketika memasukkan st elemen. Kami harus mempertimbangkan tiga kasus (setelah swap):$n+1$

1. Salah satu elemen dalam daftar, tidak bertukar, yaitu dan j ∈ { 1 , ... , n $i \in \{1,\dots,n\}$$j \in \{1,\dots,n\}$
2. Salah satu elemen dalam daftar, bertukar, yaitu dan j ∈ { 1 , … , n $i = n+1$$j \in \{1,\dots,n\}$
3. Elemen baru, yaitu dan j = n + $i \in \{1,\dots,n+1\}$$j = n+1$

Untuk setiap kasus, kami menghitung probabilitas elemen berada pada posisi i ; semua harus berubah menjadi $j$$i$ (yang cukup karena(1)). Misalkanpn=$\frac{1}{n+1}$$(1)$ adalah probabilitas dari salah satu yang pertamanelemen berada di posisi dalam daftar tua (hipotesis induksi), danps=$p_n = \frac{1}{n}$$n$ kemungkinan posisi apapun yang dipilih oleh(asumsi 1, 2). Perhatikan bahwa kutipan daftar dengannelemen dan memilih posisi swap adalahperistiwa independen, sehingga probabilitas faktor peristiwa gabungan, misalnya$p_s = \frac{1}{n+1}$random_item$n$

$\qquad \displaystyle \operatorname{Pr}(L_i=j, i \text{ swapped}) = \operatorname{Pr}(L_i=j)\cdot \operatorname{Pr}(i \text{ swapped}) = p_np_s$

untuk . Sekarang untuk perhitungan.$i,j \in \{1,\dots,n\}$

1. Kami hanya mempertimbangkan elemen lama . Elemen j tersebut berada pada posisi i jika dan hanya jika ada sebelum penyisipan terakhir dan saya tidak dipilih sebagai posisi swap, yaitu $n$$j$$i$$i$

   .$\quad \displaystyle \operatorname{Pr}(L_i = j) = p_n(1-p_s) = \frac{1}{n}\cdot\frac{n}{n+1} = \frac{1}{n+1}$

2. Di sini kami menganggap bahwa salah satu elemen lama ditukar ke posisi terakhir. Elemen bisa berada di salah satu posisi lama, jadi kami menjumlahkan semua probabilitas bahwa j berada di posisi i dan saya dipilih sebagai posisi swap, yaitu$j$$j$$i$$i$

   .$\quad \displaystyle \operatorname{Pr}(L_{n+1} = j) = \sum_{i=1}^n p_np_s = \sum_{i=1}^n \frac{1}{n}\cdot\frac{1}{n+1} = \frac{1}{n+1}$

3. Elemen baru berakhir di posisi jika dan hanya jika saya dipilih sebagai posisi swap, yaitu$i$$i$

   .$\quad \displaystyle \operatorname{Pr}(L_i = j) = p_s = \frac{1}{n+1}$

Semua ternyata baik-baik saja, strategi penyisipan Anda memang mempertahankan keseragaman. Dengan kekuatan induksi, itu membuktikan bahwa algoritma Anda menciptakan permutasi yang terdistribusi secara merata.

^{Sebuah kata peringatan: bukti ini rusak jika elemen yang dimasukkan tidak berbeda secara berpasangan. dapat dibedakan, karena persamaan pertama tidak lagi valid. Tetapi algoritma Anda masih valid; setiap permutasi dengan duplikat dihasilkan oleh jumlah eksekusi acak yang sama. Anda dapat membuktikan ini dengan menandai duplikat (yaitu membuatnya dapat dibedakan), melakukan bukti di atas dan menghapus tanda (secara virtual); langkah terakhir runtuh set permutasi berukuran sama dengan yang sama.}

Seperti yang dikatakan Steven dengan benar dalam komentar, bukti di atas secara mendasar cacat karena tidak berlaku; Anda dapat membangun distribusi pada set permutasi yang memenuhi tangan kanan, tetapi tidak pada sisi kiri¹.$(1)$

random_item$L^{(k)}$$\{1,\dots,k\}$

$\pi' \in \mathrm{Perm}_{n+1}$$\{1,\dots,n+1\}$

$\qquad \displaystyle \pi' = (\pi(1), \pi(2), \dots, \pi(i-1), n+1, \pi(i+1), \dots, \pi(n), \pi(i))$

$\pi \in \mathrm{Perm}_n$$i \in \{1,\dots,n+1\}$$\operatorname{Pr}(L^{(n)} = \pi) = \frac{1}{n!}$random_item$i$$\frac{1}{n+1}$$\pi$$i$

$\qquad \displaystyle \operatorname{Pr}(L^{(n+1)} = \pi') = \operatorname{Pr}(L^{(n)} = \pi) \cdot \operatorname{Pr}(i \text{ swapped}) = \frac{1}{(n+1)!}$

yang harus kami tunjukkan. Dengan kekuatan induksi, itu membuktikan bahwa algoritma Anda menciptakan permutasi yang terdistribusi secara merata.

1. $\{(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3)\}$$\frac{1}{4}$$0$