Probability
字符串中字母按順序出現的概率
假設我們有一個包含符號，， 在哪裡， 和.
對於一個隨機長度的字符串, 字母的概率是多少（不包括)，按順序發生（不一定連續）？換句話說，字符串是有長度的並且滿足正則表達式.
一些澄清：
我只需要字母在某個時候按順序出現。所以沒關係，因為它包含以該順序。
我確實需要所有字母按順序出現。
字母可以重複。
該正則表達式代表一個馬爾可夫鏈對應於起始狀態的狀態和每個字母。一個過渡是從到， 從到, …, 從倒數第二個字母到最後一個字母，總是有概率. 否則狀態保持不變。最終狀態是一種吸收狀態：當它達到時，所有的字母都按順序被觀察到了。
就各州而言, 轉移矩陣是
標準線性代數技術（Jordan 範式並且它的基矩陣變化簡單而稀疏，這使得這很容易做到）建立矩陣冪第一行的最後一項是
這是在之後從開始狀態達到吸收狀態的機會過渡：它回答了這個問題。如果你願意，它可以用超幾何函數的“封閉形式”表示為
總和有一個令人愉快的組合解釋。 讓是最後一個字母第一次出現的位置。它前面是一個（可能是空的）非s，每個都有一個發生的機會；然後一個與發生的機會；然後是一個（可能是非空的）非空序列s等有首次出現的位置，然後第一次出現之後，等等。因此——包括最後一個字母的第一次出現–概率是. 這給出了總和的一項。因此，總和根據最後一個字母第一次出現的位置分解序列，該位置可以是位置的任何位置通過——這些顯然是不相交的——並將它們的概率相加。
作為一個簡單的例子來澄清解釋，假設並考慮. 有四個三個符號的序列，每個序列的概率，以及其他三個概率序列, 其中符號和按順序出現：
因此機會是
組合解釋是正則表達式
^ab（與就位) 發生概率; 並且^[^a]*a[^b]*b，與就位, 以兩種方式出現^a[^b]b和^[^a]ab, 每種都有概率.