Saya tahu Anda secara eksplisit telah meminta penjelasan intuitif dan untuk meninggalkan definisi formal, tapi saya pikir mereka agak terkait, jadi izinkan saya mengingat kembali definisi dari set yang khas:
X1,X2,...~ P ( x ) A ( n ) ε p ( x ) ( x 1 , x 2 , . . . , X n ) ∈ χ n 2 - n ( H ( X ) + ε ) ≤ p ( x 1 , x 2 , . adalah variabel acak iid maka himpunan berkenaan dengan adalah himpunan urutan dengan properti
ini berarti bahwa untuk tetap , set khas terdiri dari semua urutan yang probabilitas yang dekat dengan . Jadi, agar suatu urutan menjadi milik set tertentu, ia hanya harus memiliki probabilitas mendekati∼ p(x)A(n)ϵp(x)(x1,x2,...,xn)∈χn2−n(H(X)+ϵ)≤p(x1,x2,...,xn)≤2−n(H(X)−ϵ)(1)
ϵ2−nH(X)2−nH(X), biasanya tidak sekalipun. Untuk memahami alasannya, izinkan saya menulis ulang persamaan 1 dengan menerapkan di atasnya.log2
H(X)−ϵ≤1nlog2(1p(x1,x2,...,xn))≤H(X)+ϵ(2)
Sekarang definisi himpunan tipikal lebih langsung terkait dengan konsep entropi, atau dinyatakan dengan cara lain, informasi rata-rata dari variabel acak. Jangka menengah dapat dianggap sebagai entropi sampel dari urutan, sehingga set khas dibuat oleh semua urutan yang memberikan kita jumlah informasi dekat dengan informasi rata-rata dari variabel acak . Urutan yang paling mungkin biasanya memberi kita informasi lebih sedikit daripada rata-rata. Ingat bahwa, semakin rendah probabilitas suatu hasil, semakin tinggi informasi yang diberikannya kepada kita. Untuk memahami mengapa saya beri contoh:X
Misalkan Anda tinggal di kota yang cuacanya sangat cerah dan hangat, antara 24 ° C dan 26 ° C. Anda mungkin menonton laporan cuaca setiap pagi tetapi Anda tidak akan terlalu peduli tentang itu, maksud saya, selalu cerah dan hangat. Tapi bagaimana jika suatu hari pria / wanita cuaca memberitahu Anda bahwa hari ini akan hujan dan dingin, itu adalah pengubah permainan. Anda harus menggunakan beberapa pakaian yang berbeda dan mengambil payung dan melakukan hal-hal lain yang biasanya tidak Anda lakukan, sehingga petugas cuaca memberi Anda informasi yang sangat penting.
Singkatnya, definisi intuitif dari himpunan tipikal adalah bahwa ia terdiri dari urutan yang memberi kita sejumlah informasi yang dekat dengan yang diharapkan dari salah satu sumber (variabel acak).
$$H(X)-\epsilon\le \frac{1}{n}log_2(\frac{1}{p(x_1,x_2,...,x_n)}) \le H(X)+\epsilon \tag{2}$$
...Jawaban Diegobatt melakukan pekerjaan yang baik untuk menjelaskan secara intuitif apa yang menjadi ciri khasnya. Jawaban ini akan menjawab pertanyaan OP lainnya, digaungkan oleh @tomwesolowski: mengapa Anda mendefinisikan set tipikal dengan cara yang dapat mengecualikan elemen yang paling mungkin?
Jawaban singkatnya adalah bahwa set tip utamanya adalah alat matematika. Itu didefinisikan untuk membantu membuktikan sesuatu, dan definisi ini adalah yang paling nyaman untuk pembuktian. Ini adalah contoh yang baik tentang bagaimana kebutuhan teoritis terkadang dapat mengalahkan preferensi intuitif dalam matematika.
Set khas didefinisikan oleh bapak teori informasi , Claude Shannon . Dia ingin menentukan seberapa efisien seseorang dapat menyandikan aliran simbol dari alfabet tetap, dengan asumsi masing-masing simbol adalah sampel acak iid dari beberapa distribusi. Wawasan utamanya adalah:
Himpunan khas yang ditemukan Shannon terdiri dari sekuens-sekuens yang informasi-diri-nya , atau "kejutan-ness", kira-kira sama dengan informasi-mandiri yang diharapkan , rata-rata, untuk distribusi sumber arus. Urutan seperti itu adalah "tipikal" dalam arti bahwa informasi mereka adalah tentang rata-rata, tetapi definisi ini secara implisit mengecualikan urutan yang memiliki informasi secara signifikan lebih sedikit daripada rata-rata. Urutan yang kurang informatif ini juga merupakan yang paling memungkinkan.
Seperti yang dicatat OP, ini tidak menarik secara intuitif! Pada wajahnya, himpunan khas terdengar seperti itu harus berisi semua urutan yang paling mungkin hingga batas tertentu. Itu akan lebih mewakili apa yang biasanya terlihat di sungai.
Tetapi Shannon tidak menginginkan set tipikal yang paling "tipikal" mungkin; dia menginginkan satu yang membuatnya mudah untuk membuktikan hasil yang ingin dia buktikan. Set tipikal yang didefinisikan oleh Shannon dijamin ada, dijamin kecil, dan dijamin sekecil set lainnya yang mungkin Anda usulkan, seperti yang ditunjukkan oleh jawaban ini . Menambahkan elemen yang paling mungkin membuat set lebih mungkin, yang baik, tetapi juga membuat set lebih besar, yang buruk. Jika semua yang Anda pedulikan adalah menyelesaikan bukti Anda, mengapa memperbaiki apa yang tidak rusak?
Jika Anda memiliki tujuan yang berbeda dari Shannon, konsep kesukaan Anda yang disukai mungkin juga berbeda. Misalnya, dalam pengkodean Huffman , simbol yang paling mungkin (atau urutan simbol) mendapatkan kode terpendek. Dalam pengertian teknis tertentu, pengkodean Huffman adalah solusi optimal untuk masalah asli Shannon, dan lebih baik menangkap intuisi kita tentang tipikal. Di sisi lain, definisi tipikal Shannon lebih cocok untuk membuktikan sesuatu.
sumber
Gagasan tentang seperangkat tipikal secara implisit memperlakukan urutan hasil sebagai multiset, artinya ia menganggap Anda hanya peduli dengan histogram dari setiap urutan, misalnya Anda menganggap semua 10 urutan lemparan koin dengan 7 kepala dan 3 ekor sebagai setara.
Hasil penting adalah bahwa untuk sekuens yang cukup lama hampir semua sekuens sampel akan sewenang-wenang mendekati frekuensi yang diharapkan, yaitu distribusi menjadi sangat memuncak ketika panjang sekuens dianggap meningkat.
Kumpulan tipikal adalah versi yang lebih umum, informasi yang secara teori didefinisikan dari ide ini.
sumber
sumber