Saya telah menulis sebuah program untuk mensimulasikan kartu shuffle overhand .
Setiap kartu diberi nomor, dengan setelan naik dari CLUBS, DIAMONDS, HEARTS, SPADES
dan peringkat dari Dua hingga Sepuluh kemudian Jack, Ratu, Raja dan Ace. Jadi Dua Klub memiliki Jumlah 1, Tiga Klub a 2. .... Ace of Clubs adalah 13 ... Ace of Spades adalah 52.
Salah satu metode untuk menentukan seberapa banyak kartu dikocok adalah membandingkannya dengan kartu yang tidak diacak dan melihat apakah urutan kartu berkorelasi.
Artinya, saya mungkin memiliki kartu-kartu ini, dengan kartu yang tidak diacak untuk perbandingan:
Unshuffled Shuffled Unshuffled number Shuffled number
Two of Clubs Three of Clubs 1 2
Three of Clubs Two of Clubs 2 1
Four of Clubs Five of Clubs 3 4
Five of Clubs Four of Clubs 4 3
Korelasi dengan metode Pearson adalah: 0,6
Dengan satu set kartu yang besar (semuanya 52) Anda mungkin melihat pola-pola muncul. Hipotesis saya adalah bahwa setelah lebih banyak mengocok Anda akan mendapatkan lebih sedikit korelasi.
Namun, ada banyak cara untuk mengukur korelasi.
Saya sudah mencoba tangan saya di korelasi Pearson tetapi saya tidak yakin apakah ini adalah korelasi yang tepat untuk digunakan dalam situasi ini.
Apakah ini ukuran korelasi yang cocok? Apakah ada ukuran yang lebih cocok?
Poin Bonus Saya terkadang melihat data seperti ini di hasil saya:
Jelas ada beberapa korelasi tetapi saya tidak tahu bagaimana Anda mengukur 'trendline' yang terpisah?
sumber
Jawaban:
Anda dapat mengukur tingkat korelasi relatif (atau lebih tepatnya, tingkat peningkatan keacakan) dengan menggunakan entropi Shannon dari perbedaan nilai nominal antara semua pasangan kartu yang berdekatan.
Berikut ini cara menghitungnya, untuk setumpuk kartu acak sebanyak 52 kartu. Anda mulai dengan mengulang sekali melalui seluruh dek, dan membangun semacam histogram. Untuk setiap posisi kartu , hitung selisih nilai nominal . Untuk membuat ini lebih konkret, katakanlah kartu di posisi adalah raja sekop, dan kartu di posisi ke- adalah empat klub. Kemudian kita memiliki dan dan . Ketika Anda sampai ke , itu adalah kasus khusus; Anda berputar kembali ke awal dek dan mengambili=1,2,...,52 ΔFi=Fi+1−Fi (i+1) i Fi+1=51 Fi=3 ΔFi=51−3=48 i=52 ΔF52=F1−F52 . Jika Anda berakhir dengan angka negatif untuk salah satu , tambahkan 52 untuk membawa perbedaan nilai nominal kembali ke kisaran 1-52.ΔF
Anda akan berakhir dengan satu set perbedaan nilai nominal untuk 52 pasang kartu yang berdekatan, masing-masing jatuh ke kisaran yang diizinkan dari 1-52; hitung frekuensi relatif dari ini menggunakan histogram (yaitu, array satu dimensi) dengan 52 elemen. Histogram merekam semacam "distribusi probabilitas yang diamati" untuk dek; Anda dapat menormalkan distribusi ini dengan membagi jumlah dalam setiap nampan dengan 52. Dengan demikian Anda akan berakhir dengan serangkaian variabel mana masing-masing dapat mengambil diskrit rentang nilai yang mungkin: {0, 1/52, 2/52, 3/52, dll} tergantung pada berapa banyak perbedaan nilai wajah berpasangan yang berakhir secara acak di tempat sampah tertentu dari histogram.p1,p2,...p52
Setelah memiliki histogram, Anda dapat menghitung entropi Shannon untuk iterasi acak acak sebagai
sumber
Saya tahu bahwa posting ini sudah hampir 4 tahun, tetapi saya seorang cryptanalyst yang hobi, dan telah belajar bermain kartu sandi . Akibatnya, saya kembali ke pos ini berulang kali untuk menjelaskan pengocokan geladak sebagai sumber entropi untuk secara acak memasukkan geladak. Akhirnya, saya memutuskan untuk memverifikasi jawabannya dengan stachyra dengan mengocok deck dengan tangan, dan memperkirakan entropi deck setelah setiap pengocokan.
TL; DR, untuk memaksimalkan entropi dek:
Pertama, semua yang disebutkan oleh stachyra untuk menghitung entropi Shannon adalah benar. Ini bisa direbus dengan cara ini:
Di mana stachyra membuat satu asumsi halus, adalah bahwa menerapkan shuffle manusia dalam program komputer akan datang dengan beberapa barang bawaan. Dengan kartu remi berbasis kertas, begitu digunakan, minyak dari tangan Anda berpindah ke kartu. Dalam jangka waktu yang lama, karena penumpukan minyak, kartu akan mulai saling menempel, dan ini akan berakhir dengan shuffle Anda. Semakin banyak dek yang digunakan, semakin besar kemungkinan dua atau lebih kartu yang berdekatan akan saling menempel, dan semakin sering hal itu terjadi.
Lebih lanjut, seharusnya kedua klub dan jack of heart tetap bersatu. Mereka mungkin akan terjebak bersama selama pengocokan Anda, tidak pernah berpisah. Ini bisa ditiru dalam program komputer, tetapi ini tidak terjadi dengan rutin R stachyra.
Juga, stachyra memiliki variabel manipulasi "mixprob". Tanpa sepenuhnya memahami variabel ini, itu adalah sedikit kotak hitam. Anda bisa salah mengaturnya, memengaruhi hasil. Jadi, saya ingin memastikan intuisinya benar. Jadi saya memverifikasi dengan tangan.
Saya mengocok deck 20 kali dengan tangan, dalam dua contoh berbeda (40 total pengocokan). Pada contoh pertama, saya hanya mengacak-acak, menjaga agar potongan kanan dan kiri tetap sama. Dalam contoh kedua, saya memotong geladak dengan sengaja dari tengah geladak (1/3, 2/5, 1/4, dll.) Sebelum melakukan pemotongan genap untuk pengocokan riffle. Perasaan saya pada contoh kedua adalah bahwa dengan memotong geladak sebelum mengocok, dan menjauh dari tengah, saya bisa memasukkan difusi ke dalam geladak lebih cepat daripada mengacak-acak stock riffle.
Inilah hasilnya. Pertama, pengocokan riffle lurus:
Dan di sini memotong dek dikombinasikan dengan pengocokan riffle:
Tampaknya entropi dimaksimalkan sekitar 1/2 waktu klaim oleh stachyra. Lebih lanjut, intuisi saya benar bahwa memotong geladak dengan sengaja menjauh dari tengah terlebih dahulu, sebelum mengacak-acakkan riffle benar-benar memperkenalkan difusi ke dalam geladak. Namun, setelah sekitar 5 mengocok, itu tidak terlalu penting lagi. Anda dapat melihat bahwa setelah sekitar 6-7 mengocok, entropi dimaksimalkan, dibandingkan 10-12 ketika klaim membuat stachyra saya. Mungkinkah 7 mengocok cukup, atau saya dibutakan?
Anda dapat melihat data saya di Google Sheets . Mungkin saja saya salah mencatat satu atau dua kartu remi, jadi saya tidak bisa menjamin akurasi 100% dengan data.
Penting bahwa temuan Anda juga diverifikasi secara independen. Brad Mann, dari Departemen Matematika di Universitas Harvard, mempelajari berapa kali yang diperlukan untuk mengocok setumpuk kartu sebelum dapat diprediksi kartu apa pun di geladak benar-benar tidak dapat diprediksi (entropi Shannon dimaksimalkan). Hasilnya dapat ditemukan di PDF 33 halaman ini .
Yang menarik dengan temuannya, adalah bahwa dia sebenarnya secara mandiri memverifikasi artikel New York Times 1990 oleh Persi Diaconis , yang mengklaim bahwa 7 shuffle cukup untuk mencampur setumpuk kartu remi secara menyeluruh melalui shuffle riffle.
Brad Mann berjalan melalui beberapa model matematika yang berbeda dalam pengocokan, termasuk rantai Markov, dan sampai pada kesimpulan berikut:
Brad Mann hanya memverifikasi hasil stachyra secara independen, dan bukan milikku. Jadi, saya melihat lebih dekat pada data saya, dan saya menemukan mengapa 7 shuffle tidak cukup. Pertama, entropi Shannon maksimum teoretis dalam bit untuk kartu apa pun di dek adalah log (52) / log (2) ~ = 5,7 bit. Tetapi data saya tidak pernah benar-benar rusak jauh di atas 5 bit. Penasaran, saya membuat array dari 52 elemen dengan Python, mengocok array itu:
Menghitung hasil entropi per kartu sekitar 4,8 bit. Melakukan ini selusin kali atau lebih menunjukkan hasil yang serupa bervariasi antara 5,2 bit dan 4,6 bit, dengan rata-rata 4,8 hingga 4,9. Jadi melihat nilai entropi mentah data saya tidak cukup, kalau tidak saya bisa menyebutnya baik di 5 shuffles.
Ketika saya melihat lebih dekat pada data saya, saya perhatikan jumlah "ember nol". Ini adalah kotak di mana tidak ada data untuk delta di antara permukaan kartu untuk nomor itu. Misalnya, ketika mengurangi nilai dua kartu yang berdekatan, tidak ada hasil "15" setelah semua 52 delta telah dihitung.
Saya melihat bahwa itu akhirnya mengendap sekitar 17-18 "zero bucket" sekitar 11-12 shuffles. Benar saja, dek saya yang dikocok melalui Python rata-rata 17-18 "nol ember", dengan tinggi 21 dan rendah 14. Mengapa 17-18 adalah hasil yang ditetapkan, saya belum dapat menjelaskan ... belum. Tapi, sepertinya saya ingin keduanya ~ 4,8 bit entropi DAN 17 "zero bucket".
Dengan stock riffle shuffling saya, itu 11-12 shuffles. Dengan sayangku, itu 6-7. Jadi, ketika datang ke permainan, saya akan merekomendasikan cut-and-shuffles. Tidak hanya ini menjamin bahwa kartu atas dan bawah tercampur ke dalam geladak pada setiap acak, itu juga lebih cepat dari 11-12 shuffle. Saya tidak tahu tentang Anda, tetapi ketika saya bermain kartu dengan keluarga dan teman-teman saya, itu tidak cukup sabar bagi saya untuk melakukan 12 riffle shuffles.
sumber