Kemungkinan huruf-huruf muncul berurutan

8

Misalkan kita memiliki alfabet yang mengandung simbol , , di mana , dan \ Pr (\ $) = 1 - (\ Pr (a) + \ Pr (b) + \ cdots) = 1-mp .m+1{a,b,c,d,e,...,$}p=Pr(a)=Pr(b)=Pr($)=1(Pr(a)+Pr(b)+)=1mp

Untuk string acak dengan panjang n , berapakah probabilitas bahwa huruf a,b,c,... (tidak termasuk $ ), muncul secara berurutan (tidak harus secara berurutan)? Dengan kata lain, string memiliki panjang n dan memenuhi ekspresi reguler abc .

Beberapa klarifikasi:

Saya hanya perlu surat untuk muncul agar kadang-kadang. Jadi acbc ok karena mengandung abc dalam urutan itu.

Saya membutuhkan semua huruf m untuk ditampilkan secara berurutan.

Surat bisa diulang.

Andrew W
sumber

Jawaban:

11

Ekspresi reguler itu mewakili rantai Markov pada status terkait dengan status awal dan masing-masing huruf. Transisi dibuat dari ke , dari ke , ..., dan dari huruf kedua dari belakang ke yang terakhir, selalu dengan probabilitas . Kalau tidak negara tetap sama. Keadaan akhir adalah kondisi menyerap: ketika telah tercapai, semua huruf telah diamati secara berurutan.m+1ssaabp

Dalam hal status , matriks transisi adalah(s,a,b,)

Pm=(1pp0001pp00p001pp0001)

Teknik-teknik aljabar linier standar (bentuk normal Jordan dan perubahan basis matriksnya sederhana dan jarang, membuat ini cukup mudah dilakukan) menetapkan bahwa untuk merupakan entri terakhir di baris pertama dari kekuatan matriks adalahPmnmPmn

Pmn(1,m+1)=pmi=0nm(m1+im1)(1p)i.

Ini adalah kesempatan untuk mencapai keadaan menyerap dari negara awal setelah transisi: itu menjawab pertanyaan. Jika Anda suka, itu dapat diekspresikan dalam "bentuk tertutup" dalam hal fungsi Hypergeometrik sebagain

Pmn(1,m+1)=1pm(nm1)(1p)m+n+12F1(1,n+1;n+2m;1p).

Jumlahnya memiliki interpretasi kombinatorial yang menyenangkan. Biarkan menjadi posisi di mana huruf terakhir pertama kali muncul. Ini didahului oleh urutan (mungkin kosong) dari non- , masing-masing dengan peluang terjadi; kemudian dengan peluang terjadi; kemudian urutan (mungkin non-kosong) dari non- s, dll. Ada lokasi di mana untuk menempatkan penampilan pertama dari , maka penampilan pertama dari a setelah itu, dll. Jadi - termasuk penampilan pertama dari huruf terakhir di posisi - probabilitasnya adalahm+ia1papb(m1+im1)abm+i(m1+im1)pm(1p)k . Ini memberikan satu istilah jumlah. Dengan demikian, penjumlahan memecah urutan sesuai dengan tempat huruf terakhir pertama kali terjadi, yang dapat di mana saja dari posisi hingga - ini jelas saling terpisah - dan menambahkan probabilitas mereka.m+0m+(nm)

Sebagai contoh sederhana untuk memperjelas interpretasi, misalkan dan pertimbangkan . Ada empat urutan dari tiga simbol, masing-masing probabilitas , dan tiga urutan probabilitas , di mana simbol dan muncul secara berurutan:m=2n=3p3p2(12p)ab

aab,aba,abb,bab;ab$,a$b,$ab.

Karena itu kesempatannya adalah

4p3+3p2(12p)=3p22p3=p2(32p)=p2(1+2(1p))=P23(1,3).

Interpretasi kombinatorial adalah bahwa ekspresi reguler ^ab(dengan pada posisi ) terjadi dengan probabilitas ; dan , dengan di posisi , terjadi dalam dua cara seperti dan , masing-masing dengan probabilitas .b2p2^[^a]*a[^b]*bb3^a[^b]b^[^a]abp2(1p)

whuber
sumber
0

Dengan "Surat dapat diulangi" yang Anda maksudkan bahwa abbc adalah string yang valid? Mereka 'tampil berurutan'?

Jika tidak, tampaknya menjadi jawaban bagi saya. adalah probabilitas bahwa dalam ruang yang diberikan karakter tidak ada kombinasi seperti itu, maka Anda memperluasnya ke semua ruang yang mungkin dari karakter1(1pm)nm+11pmmnm+1m

Jika ya maka Anda memiliki batas bawah

gsmafra
sumber
Rumus ini tidak setuju dengan penghitungan lengkap kasus ketika dan kecil, sehingga umumnya tidak benar. mn
whuber