Masalah ini terkait dengan penelitian lab saya dalam cakupan robot:
Gambar angka secara acak dari set tanpa penggantian, dan urutkan angka dalam urutan menaik. .
Dari daftar angka yang diurutkan ini , menghasilkan perbedaan antara angka berurutan dan batas: . Ini memberi celah.
Apa distribusi kesenjangan maksimum?
Ini dapat dibingkai menggunakan statistik pesanan :
Lihat tautan untuk distribusi kesenjangan , tetapi pertanyaan ini menanyakan distribusi kesenjangan maksimum .
Saya akan puas dengan nilai rata-rata, .
Jika semua kesenjangan adalah ukuran 1. Jika ada satu celah ukuran , dan kemungkinan lokasi. Ukuran celah maksimum adalah , dan celah ini dapat ditempatkan sebelum atau setelah salah satu nomor , untuk total posisi yang memungkinkan. Ukuran celah maksimum terkecil terkecil adalah . Tentukan probabilitas kombinasi apa pun yang diberikan .
Saya telah memecahkan sebagian fungsi massa probabilitas sebagai
Pekerjaan saat ini (1): Persamaan untuk celah pertama, langsung: Nilai yang diharapkan memiliki nilai sederhana: . Dengan simetri, saya berharap semua kesenjangan memiliki distribusi ini. Mungkin solusinya dapat ditemukan dengan menggambar dari distribusi ini kali. P ( a ( 1 ) = k ) = P ( k ; m , n ) = 1E[P(a(1))]=1
Pekerjaan saat ini (2): mudah untuk menjalankan simulasi Monte Carlo.
simMaxGap[m_, n_] := Max[Differences[Sort[Join[RandomSample[Range[m], n], {0, m+1}]]]];
m = 1000; n = 1; trials = 100000;
SmoothHistogram[Table[simMaxGap[m, n], {trials}], Filling -> Axis,
Frame -> {True, True, False, False},
FrameLabel -> {"k (Max gap)", "Probability"},
PlotLabel -> StringForm["m=``,n=``,smooth histogram of maximum map for `` trials", m, n, trials]][![enter image description here][1]][1]
Jawaban:
Misalkan adalah peluang minimum, , sama dengan ; yaitu, sampel terdiri dari dan subset dari . Ada himpunan bagian seperti itu dari subset yang kemungkinan besar sama, dari manaf(g;n,m) a(1) g g n−1 {g+1,g+2,…,m} (m−gn−1) (mn)
Menambahkan untuk semua nilai yang mungkin dari lebih besar dari menghasilkan fungsi survivalf(k;n,m) k g
Biarkan menjadi variabel acak yang diberikan oleh celah terbesar:Gn,m
(Ini menjawab pertanyaan yang awalnya dibingkai, sebelum dimodifikasi untuk memasukkan celah antara dan .)a(n) m
Kami akan menghitung fungsi survivalnya dari mana seluruh distribusi mudah diperoleh. Metode ini adalah program dinamis yang dimulai dengan , yang jelas itu
Untuk , perhatikan bahwa acara adalah gabungan yang tidak terpisahkan dari acara tersebutn>1 Gn,m>g
di mana jarak pertama melebihi , dan memisahkan peristiwag g
di mana celah pertama sama dengan dan kesenjangan lebih besar dari terjadi kemudian dalam sampel. Hukum Probabilitas Total menegaskan probabilitas kejadian ini ditambah, dari manak g
Memperbaiki dan meletakkan array dua arah yang diindeks oleh dan , kita dapat menghitung dengan menggunakan untuk mengisi baris pertama dan untuk mengisi setiap baris berturut-turut menggunakan operasi per baris. Akibatnya tabel dapat diselesaikan dalam operasi dan semua tabel untuk hingga dapat dibangun dalam operasi .g i=1,2,…,n j=1,2,…,m P(g;n,m) (1) (2) O(gm) O(gmn) g=1 g=m−n+1 O(m3n)
Grafik ini menunjukkan fungsi survival untuk . Ketika meningkat, grafik bergerak ke kiri, sesuai dengan peluang penurunan kesenjangan besar.g→P(g;n,64) n=1,2,4,8,16,32,64 n
Rumus tertutup untuk dapat diperoleh dalam banyak kasus khusus, terutama untuk besar , tetapi saya belum dapat memperoleh rumus tertutup yang berlaku untuk semua . Perkiraan yang baik sudah tersedia dengan mengganti masalah ini dengan masalah analog untuk variabel seragam kontinu.P(g;n,m) n g,n,m
Akhirnya, harapan diperoleh dengan menjumlahkan fungsi survivalnya mulai dari :Gn,m g=0
Plot kontur harapan ini menunjukkan kontur pada , lulus dari gelap ke terang.2,4,6,…,32
sumber