Xác suất thống kê

Vì cả 2 chuỗi cùng random, em có thể giả sử A, B bất kỳ cố định. Hãy nghĩ bài này như một vấn đề trong dynamic programming/induction: định nghĩa $f(n, m)$ là xác suất $m$ bits cuối của chuỗi B là substring của $n$ bits cuối của chuỗi A. Do cả 2 chuỗi cùng random, xác suất 1 bit bất kỳ của A bằng với 1 bit bất kỳ của B là 0.5. Sử dụng điều đó với Bayes' Rule và greedy matching, ta có:

$$f(n,m)=\frac{1}{2}f(n-1,m-1)+\frac{1}{2}f(n-1,m)$$

với phần tử đầu tiên tương ứng với trường hợp chữ cái bên chuỗi A giống với chữ cái bên chuỗi B, và phần tử sau là ngược lại. Cùng lúc, ta có base case $f(n,n) = 2^{-n}$, bởi vì xác suất một chuỗi với độ dài $n$ là substring của một chuỗi khác cùng độ dài chính là xác suất 2 chuỗi bằng nhau. 2 công thức trên có quen thuộc không -- vì nhìn vào đó em có thể ra luôn công thức closed-form cuối cùng đó:

$$f(n,m)=\frac{1}{2^n}\begin{pmatrix}n \\ m\end{pmatrix}=\frac{n!}{m!(n-m)!2^n}$$