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=⎛⎝⎜⎜⎜⎜⎜⎜⎜1−p0⋮00p1−p0⋯00p⋱0⋯⋯⋯p1−p000⋮p1⎞⎠⎟⎟⎟⎟⎟⎟⎟
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 adalahPmn≥mPnm
Pnm(1,m+1)=pm∑i=0n−m(m−1+im−1)(1−p)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
Pnm(1,m+1)=1−pm(nm−1)(1−p)−m+n+12F1(1,n+1;n+2−m;1−p).
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+ia1−papb(m−1+im−1)abm+i(m−1+im−1)pm(1−p)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+(n−m)
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(1−2p)ab
aab,aba,abb,bab;ab$,a$b,$ab.
Karena itu kesempatannya adalah
4p3+3p2(1−2p)=3p2−2p3=p2(3−2p)=p2(1+2(1−p))=P32(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]*b
b3^a[^b]b
^[^a]ab
p2(1−p)