Asked Feb 21st, 9:38 AM 204 0 1
  • 204 0 1
+2

Xác suất thống kê

Share
  • 204 0 1

Xin chào mọi người,

Em đang bị đơ 1 câu hỏi nên muốn nhờ mọi người giải dùm ạ 😃) 😃)

Đề bài: Cho chuỗi A gồm m bits(chuỗi gồm m giá trị 0 và 1), chuỗi B gồm n bits(chuỗi gồm n giá trị 0 và 1). Với n ~ 0.05×m0.05\times{m}. AB là hai chuỗi ngẫu nhiên, có tính thứ tự. Tính xác suất để thứ tự các bits trong chuỗi B tồn tại trong chuỗi A theo đúng thứ tự hay nói cách khác là xác suất để khi ta xóa (mn)(m-n) bits trong chuỗi A ta thu được chuỗi B.

Ví dụ : A: 1000111011 B: 1101 thỏa mãn

A: 1000111011 B: 11001 không thỏa thỏa mãn

Em cảm ơn ạ.

1 ANSWERS


Answered Feb 21st, 10:00 AM
Accepted
+10

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)f(n, m) là xác suất mm bits cuối của chuỗi B là substring của nn 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)=12f(n1,m1)+12f(n1,m)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)=2nf(n,n) = 2^{-n}, bởi vì xác suất một chuỗi với độ dài nn 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)=12n(nm)=n!m!(nm)!2nf(n,m)=\frac{1}{2^n}\begin{pmatrix}n \\ m\end{pmatrix}=\frac{n!}{m!(n-m)!2^n}

Share