Brain-teaser: Berapa panjang yang diharapkan dari urutan iid yang meningkat secara monoton ketika ditarik dari distribusi seragam [0,1]?

28

Ini adalah pertanyaan wawancara untuk posisi analis kuantitatif, dilaporkan di sini . Misalkan kita menggambar dari distribusi yang seragam dan gambarnya adalah id, berapa panjang yang diharapkan dari distribusi yang meningkat secara monoton? Yaitu, kita berhenti menggambar jika undian saat ini lebih kecil dari atau sama dengan undian sebelumnya.[0,1]

Saya mendapatkan beberapa yang pertama: \ Pr (\ text {length} = 2) = \ int_0 ^ 1 \ int_ {x_1} ^ 1 \ int_0 ^ {x_2} \ mathrm {d} x_3 \, \ mathrm {d} x_2 \, \ mathrm {d} x_1 = 1/3 \ Pr (\ text {length} = 3) = \ int_0 ^ 1 \ int_ {x_1} ^ 1 \ int_ {x_2} ^ 1 \ int_0 ^ {x_3} \ mathrm {d} x_4 \, \ mathrm { d} x_3 \, \ mathrm {d} x_2 \, \ mathrm {d} x_1 = 1/8

Pr(length=1)=010x1dx2dx1=1/2
Pr(length=2)=01x110x2dx3dx2dx1=1/3
Pr(length=3)=01x11x210x3dx4dx3dx2dx1=1/8

tapi saya merasa menghitung integral tersarang ini semakin sulit dan saya tidak mendapatkan "trik" untuk menggeneralisasi ke Pr(length=n) . Saya tahu jawaban akhir terstruktur

E(length)=n=1nPr(length=n)

Ada ide tentang bagaimana menjawab pertanyaan ini?

Orang Amazon
sumber

Jawaban:

37

Berikut adalah beberapa petunjuk umum untuk menyelesaikan pertanyaan ini:

Anda memiliki urutan variabel acak IID kontinu yang berarti mereka dapat ditukar . Apa artinya ini tentang kemungkinan mendapatkan urutan tertentu untuk nilai n pertama n? Berdasarkan ini, berapakah probabilitas mendapatkan urutan yang meningkat untuk nilai n pertama n? Dimungkinkan untuk mengetahui hal ini tanpa mengintegrasikan distribusi variabel acak yang mendasarinya. Jika Anda melakukan ini dengan baik, Anda akan dapat memperoleh jawaban tanpa asumsi distribusi seragam - yaitu, Anda mendapatkan jawaban yang berlaku untuk setiap urutan variabel acak kontinu yang dapat dipertukarkan.


Ini adalah solusi lengkapnya ( jangan lihat apakah Anda seharusnya memikirkannya sendiri ):

Biarkan menjadi urutan variabel acak kontinu independen Anda, dan biarkan menjadi jumlah elemen yang meningkat di awal urutan. Karena ini adalah variabel acak kontinu yang dapat ditukar, mereka hampir pasti tidak setara satu sama lain, dan setiap pemesanan sama-sama mungkin, jadi kami memiliki: (Perhatikan bahwa hasil ini berlaku untuk setiap urutan IID dari variabel acak kontinu; mereka tidak harus memiliki distribusi yang seragam.) Jadi variabel acak memiliki probabilitas fungsi massaU1,U2,U3,IID Continuous DistNmax{nN|U1<U2<<Un}

P(Nn)=P(U1<U2<<Un)=1n!.
N
pN(n)=P(N=n)=1n!1(n+1)!=n(n+1)!.
Anda akan melihat bahwa hasil ini sesuai dengan nilai yang telah Anda hitung menggunakan integrasi di atas nilai yang mendasarinya. (Bagian ini tidak diperlukan untuk solusi; itu termasuk untuk kelengkapan.) Menggunakan aturan yang terkenal untuk nilai yang diharapkan dari variabel acak non-negatif , kami memiliki: Perhatikan lagi bahwa tidak ada dalam pekerjaan kami yang menggunakan distribusi seragam yang mendasarinya. Oleh karena itu, ini adalah hasil umum yang berlaku untuk setiap urutan variabel acak kontinu yang dapat dipertukarkan.
E(N)=n=1P(Nn)=n=11n!=e1=1.718282.

Beberapa wawasan lebih lanjut:

Dari kerja di atas kita melihat bahwa hasil distribusi dan nilai yang diharapkan ini tidak tergantung pada distribusi yang mendasarinya, asalkan itu merupakan distribusi yang berkelanjutan. Ini benar-benar tidak mengejutkan setelah kami mempertimbangkan fakta bahwa setiap variabel acak skalar kontinu dapat diperoleh melalui transformasi monotonik dari variabel acak seragam (dengan transformasi menjadi fungsi kuantilnya). Karena transformasi monoton mempertahankan urutan-peringkat, melihat probabilitas urutan variabel acak kontinu IID sewenang-wenang adalah sama dengan melihat probabilitas urutan variabel acak seragam IID .

Pasang kembali Monica
sumber
6
Bagus sekali! (+1)
jbowman
1
@ Kalau saya mengikuti Anda sampai persamaan terakhir ... Saya pikir nilai yang diharapkan harus, daripada ... bisakah Anda menjelaskan bagian ini lebih lanjut?
E(N)=n=1P(N=n)n=n=1n2/(n+1)!
E(N)=n=1P(Nn)
Amazon
5
Ini adalah aturan terkenal untuk nilai yang diharapkan dari variabel acak non-negatif . Menggunakan teknik yang melibatkan menukar urutan penjumlahan, Anda memiliki: Jadi Anda harus menemukan bahwa .
E(N)=n=1nP(N=n)=n=1k=1nP(N=n)=n=1k=nP(N=k)=n=1P(Nn).
n1n!=nn2(n+1)!
Pasang kembali Monica
Bisakah Anda jelaskan mengapa ? P(Nn)=P(U1<U2<<Un)
badmax
1
@badmax: Variabel acak adalah jumlah elemen bertambah di awal urutan (lihat definisinya). Jadi, jika itu berarti setidaknya ada elemen yang meningkat di awal urutan. Ini berarti bahwa elemen pertama harus dalam urutan yang meningkat, yaitu . NUNnnnU1<U2<<Un
Pasang kembali Monica
8

Metode pemecahan lain yang memberi Anda solusi untuk kasus yang lebih umum.

Misalkan adalah panjang yang diharapkan dari urutan monotonik , sedemikian sehingga . Nilai yang ingin kita hitung adalah . Dan kita tahu . Pengkondisian pada nilai berikutnya,F(x){x1,x2,...}xx1x2F(0)F(1)=0

F(x)=0xπ(y)0dy+x1π(y)(1+F(y))dy=x11+F(y)dy

di mana adalah densitas U [0,1]. Begituπ(y)=1

F(x)=(1+F(x))

Memecahkan dengan kondisi batas , kita mendapatkan . Maka .F(1)=0F(x)=e(1x)1F(0)=e1

jf328
sumber
2
Ini sangat pintar. Cukup dengan sedikit mengutarakannya: pengamatan Anda adalah 1) jika adalah panjang dari urutan kenaikan awal terpanjang dikurangi satu maka cukup untuk menentukan dan set , dan 2) adalah nol jika dan sebaliknya. Karena kita mendapatkan , yang dalam kasus seragam dapat diselesaikan secara langsung. LE(L|X0=x)=:F(x)x=0E(L|X0=x,X1=y)y<x1+E(L|X0=y)E(L|X0=x)=E(E(L|X0=x,X1))=RfX(y)E(L|X0=x,X1=y)dy=x1fX(y)(1+E(L|X0=y))dy=x1fX(y)(1+F(y))dyF(x)=fX(x)(1+F(x))
Matthew Towers
2
+1 Memang sangat pintar. Tetapi karena jawaban akhir tidak tergantung pada distribusi (seperti jawaban yang lain membahas), perhitungan ini juga harusnya tidak bergantung pada . Apakah ada cara untuk melihatnya? CC ke @m_t_. π(y)
Amoeba berkata Reinstate Monica
3
@amoeba Saya setuju tidak boleh bergantung pada distribusi , tetapi nilai-nilai harus: solusi umum DE itu adalahF(0)XFF=Ceπ1
Matthew Towers
1
@ MartijnWeterings Saya pikir , bukan 1, misalnya dalam kasus seragam kita mendapatkanC=eeex1
Matthew Towers
1
Ya kamu benar. Saya menggunakan kasing seragam untuk menyimpulkan pernyataan saya tetapi secara salah menggunakan bukannyace1x1cex1
Sextus Empiricus
0

Metode penyelesaian lain adalah dengan menghitung integral secara langsung.

Peluang menghasilkan urutan yang bagian yang bertambah memiliki panjang adalah , di mana .nfn(0)fn(x)=x1x11x21...xn21xn11dxndxn1...dx2dx1

Yang perlu kita lakukan adalah menghitung .fn(0)

Jika Anda mencoba menghitung beberapa , mungkin Anda akan menemukan bahwafn(x)fn(x)=t=0n(x)tt!(nt)!

Kasus Dasar: ketika ,n=1f1(x)=t=01(x)tt!(nt)!=1x=x1dx1

Hipotesis Induktif: ketika ,n=kfn(x)=t=0k(x)tt!(kt)! , for k1

Langkah Induktif: ketika ,n=k+1

     fn(x)=fk+1(x)=x1fk(x)dx

=x1t=0k(x)tt!(kt)!dx

=t=0k(x)t+1t!(kt)!×(t+1)|x1=t=0k(x)t+1(t+1)!(kt)!|x1

=t=1k+1(x)tt!(kt+1)!|x1

=t=1k+1(1)t+1t!(kt+1)!+t=1k+1(x)tt!(kt+1)!

=t=1k+1(1)t+1Ctk+1(k+1)!+t=1k+1(x)tt!(kt+1)!

=1(k+1)!+t=0k+1(1)t+1Ctk+1(k+1)!+t=1k+1(x)tt!(kt+1)!

=1(k+1)!(11)k+1(k+1)!+t=1k+1(x)tt!(kt+1)!

=t=0k+1(x)tt!(kt+1)!

Dengan Induksi Matematika, asumsi itu berlaku.

Jadi, kita dapatkan bahwafn(0)=1n!

Jadi,E(length)=n=1Pr(lengthn)=n=11n!=e1

劉家維
sumber