Kesenjangan maksimum antara sampel yang diambil tanpa penggantian dari distribusi seragam diskrit

16

Masalah ini terkait dengan penelitian lab saya dalam cakupan robot:

Gambar angka secara acak dari set tanpa penggantian, dan urutkan angka dalam urutan menaik. .n{1,2,,m}1nm

Dari daftar angka yang diurutkan ini , menghasilkan perbedaan antara angka berurutan dan batas: . Ini memberi celah.{a(1),a(2),,a(n)}g={a(1),a(2)a(1),,a(n)a(n1),m+1a(n)}n+1

Apa distribusi kesenjangan maksimum?

P(max(g)=k)=P(k;m,n)=?

Ini dapat dibingkai menggunakan statistik pesanan : P(g(n+1)=k)=P(k;m,n)=?

Lihat tautan untuk distribusi kesenjangan , tetapi pertanyaan ini menanyakan distribusi kesenjangan maksimum .

Saya akan puas dengan nilai rata-rata, E[g(n+1)] .

Jika n=m semua kesenjangan adalah ukuran 1. Jika n+1=m ada satu celah ukuran 2 , dan n+1 kemungkinan lokasi. Ukuran celah maksimum adalah mn+1 , dan celah ini dapat ditempatkan sebelum atau setelah salah satu nomor n , untuk total n+1 posisi yang memungkinkan. Ukuran celah maksimum terkecil terkecil adalah mnn+1 . Tentukan probabilitas kombinasi apa pun yang diberikan T=(mn)1 .

Saya telah memecahkan sebagian fungsi massa probabilitas sebagai (1)P(g(n+1)=k)=P(k;m,n)={0k<mnn+11k=mnn+11k=1 (occurs when m=n)T(n+1)k=2 (occurs when m=n+1)T(n+1)k=m(n1)n?m(n1)nkmn+1T(n+1)k=mn+10k>mn+1

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 ) = 1a(1)E[P(a(1))]=1

P(a(1)=k)=P(k;m,n)=1(mn)k=1mn+1(mk1n1)
nnE[P(a(1))]=1(mn)k=1mn+1(mk1n1)k=mn1+nnn

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]
AaronBecker
sumber
1
Dengan kondisi ini Anda harus memiliki n <= m. Saya pikir Anda ingin g = {a_ (1), a_ (2) -a_ (1), ..., a_ (n) -a_ (n-1)}. Apakah memilih secara acak berarti memilih setiap angka dengan probabilitas 1 / m pada pengundian pertama? Karena Anda tidak mengganti probabilitas akan menjadi 1 / (m-1) pada detik dan seterusnya ke 1 pada draw mth jika n = m. Jika n <m ini akan berhenti lebih awal dengan undian terakhir yang memiliki probabilitas 1 / (m- (n-1)) pada undian ke-n.
Michael R. Chernick
2
Deskripsi asli Anda tentang tidak masuk akal, karena (saya percaya) Anda mengubah dua subskrip. Harap verifikasi bahwa saya mengedit sesuai dengan niat Anda: khususnya, silakan konfirmasi bahwa Anda berarti untuk itu menjadi kesenjangan, yang adalah yang pertama. n a ( 1 )gna(1)
Whuber
1
@ung saya pikir ini adalah penelitian, bukan belajar sendiri
Glen_b -Reinstate Monica
1
Saya pikir ukuran gap minimum dan maksimum Anda harus dan . Ukuran celah minimum adalah ketika bilangan bulat berturut-turut dipilih, dan ukuran celah maksimum terjadi ketika Anda memilih dan bilangan bulat pertama (atau dan )1mn+1mn11,,n11mn+2,,m
probabilityislogic
1
Terima kasih Michael Chernick dan probabilityislogic, koreksi Anda telah dibuat. Terima kasih @whuber untuk membuat koreksi!
AaronBecker

Jawaban:

9

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)ggn1{g+1,g+2,,m}(mgn1)(mn)

Pr(a(1)=g=f(g;n,m)=(mgn1)(mn).

Menambahkan untuk semua nilai yang mungkin dari lebih besar dari menghasilkan fungsi survivalf(k;n,m)kg

Pr(a(1)>g)=Q(g;n,m)=(mg)(mg1n1)n(mn).

Biarkan menjadi variabel acak yang diberikan oleh celah terbesar:Gn,m

Gn,m=max(a(1),a(2)a(1),,a(n)a(n1)).

(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

P(g;n,m)=Pr(Gn,m>g),
Gn,mn=1

(1)P(g;1,m)=Pr(G1,m>1)=mgm, g=0,1,,m.

Untuk , perhatikan bahwa acara adalah gabungan yang tidak terpisahkan dari acara tersebutn>1Gn,m>g

a1>g,

di mana jarak pertama melebihi , dan memisahkan peristiwagg

a1=k and Gn1,mk>g, k=1,2,,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 manakg

(2)P(g;n,m)=Q(g;n,m)+k=1gf(k;n,m)P(g;n1,mk).

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 .gi=1,2,,nj=1,2,,mP(g;n,m)(1)(2)O(gm)O(gmn)g=1g=mn+1O(m3n)

Angka

Grafik ini menunjukkan fungsi survival untuk . Ketika meningkat, grafik bergerak ke kiri, sesuai dengan peluang penurunan kesenjangan besar.gP(g;n,64)n=1,2,4,8,16,32,64n

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)ng,n,m

Akhirnya, harapan diperoleh dengan menjumlahkan fungsi survivalnya mulai dari :Gn,mg=0

E(Gn,m)=g=0mn+1P(g;n,m).

Gambar 2: plot kontur harapan

Plot kontur harapan ini menunjukkan kontur pada , lulus dari gelap ke terang.2,4,6,,32

whuber
sumber
Saran: baris "Biarkan menjadi variabel acak yang diberikan oleh celah terbesar:", harap tambahkan celah terakhir . Plot harapan Anda cocok dengan simulasi Monte Carlo saya. Gn,mm+1an
AaronBecker