랜덤 워드에서 특정 워드가 등장할 확률 (2)

이전 글 “랜덤 워드에서 특정 워드가 등장할 확률“이 수학동아의 폴리매스 프로젝트에 링크된 것을 확인했다. 국가수리과학연구소의 2번째 문제의 추가 문제 2번 문제가 다음과 같다고 한다.

길이 m짜리 단어 l 하나가 금칙어로 지정되었을 때, 길이 n짜리 단어 중 이를 포함하지 않는 것의 개수를 a_{l(n)}이라고 합시다. m이 고정되어 있을 때, n이 무한대로 갈 때 (a_{l(n)})^{\frac{1}{n}}의 극한이 최대/최소가 되는 l은 각각 어떻게 주어질까요?

앞서 이야기한 논의에서 조금 더 연장하면 이 문제 역시 해결될 수 있다. 참고로 위 문제에서는 알파벳 집합 \Sigma\{0,1\}로 주어져 있는데 그냥 일반적인 경우로 봐 |\Sigma|=s라고 둔다.

이전 글에서는 특정 워드 w가 하나라도 포함될 확률에 대해서 다뤘다. 결과를 요약하자면 길이가 n인 uniform random word에서 길이 m인 특정 워드가 등장할 확률을 구하기 위해서 m+1개의 state들로 구성된 Markov chain을 만들고 이것의 transition matrix(stochastic matrix)의 특성방정식을 구한 후, 그 해를 편의상 \lambda_0^{m_0}=1^{m_0}, \lambda_1^{m_1},\ldots,\lambda_k^{m_k}라고 하면 (m_i는 multiplicity) 구하고자 하는 확률은 반드시 1+\lambda_1^n P_1(n)+\cdots+\lambda_k^n P_k(n) 꼴로 나타난다는 것이다. (단, |\lambda_i|<1이며 P_i는 차수가 m_i보다 작은 다항식이다)

이 결과를 응용하면 w가 포함되지 않는 확률은 1에서 이 값을 빼야 하므로 \lambda_1^n P_1(n)+\cdots+\lambda_k^n P_k(n)꼴로 나타나는데, 애초에 랜덤 워드가 균일하게 뽑혔던 것이므로 문제에서 요구하는 경우의 수 a_{l(n)}은 그 확률에 s^n을 곱한 꼴이 되어야 한다. 따라서 1을 제외한 eigenvalue들 중 절대값이 가장 큰 것을 \lambda라 두면 a_{l(n)}^{1/n} \rightarrow s\lambda가 된다.

편의상 우리가 지금까지 생각한 transition matrix를 T_w라 하고, M_w = s T_w로 정의한다. 이 M_w는 모든 항이 정수로 등장하며, eigenvalue가 T_w의 eigenvalue에 s를 곱한 꼴들로만 나오니 문제에서 묻는 극한은 바로 M_w의 second large eigenvalue가 된다.

이전 글에서 확률을 계산할 때 포함과 배제의 원리를 이용한 풀이를 보았는데, 그 풀이는 일반적인 답을 주지는 못했지만 굉장히 중요한 점을 하나 시사하고 있다. 그것은 포함과 배제의 원리 풀이가 적용되는 경우, 즉 w가 겹쳐서 나타날 수 없는 경우라면 그 확률(혹은 경우의 수)은 일정하게 나와야 한다는 것이다. 당연한 것처럼 보이지만 Markov chain 관점에서는 그게 trivial하지가 않다. 예를 들어, 이전 글의 예시의 경우 (\Sigma=\{ \text{A,U,G,C}\}) AUG와 AAU는 그 Markov chain의 구조가 달라져서 행렬들 역시

M_{\text{AUG}} = \begin{bmatrix} 3 & 1 & 0 & 0 \\ 2 & 1 & 1 & 0 \\ 2 & 1 & 0 & 1 \\ 0 & 0 & 0 & 4 \end{bmatrix}, M_{\text{AAU}} = \begin{bmatrix} 3 & 1 & 0 & 0 \\ 3 & 0 & 1 & 0 \\ 2 & 0 & 1 & 1 \\ 0 & 0 & 0 & 4 \end{bmatrix}

로 다르게 나오는데, 특성방정식은 동일하게 (\lambda-4)(\lambda^3 - 4\lambda^2 + 1)로 나타난다. 포함과 배제의 원리로 생각하면 AUG든 AAU든 단어 내부의 구조만 동일하다면 디테일과 상관없이 결과가 동일하게 나오는 것.

포함과 배제의 원리 풀이가 적용되지 않는 것은 w가 겹쳐서 나타날 수도 있다는 것이었는데, 그러면 구체적으로 w가 얼마나 겹쳐서 나타날 수 있는지를 따져본다. 예컨대 w=0110110이었다면, 4번째 포지션부터 시작되는 w와도 겹칠 수 있고, 7번째 포지션부터 시작되는 w와도 겹칠 수 있다. 그런데 w가 서로 겹치는건 곧 w가 순순환이란 것을 의미한다. (첫 번째 포지션부터 p번째 포지션까지의 부분이 되풀이해서 등장함) 그러한 (최소의) 순환주기 p를 잡으면, 곧 w는 1번째, p+1번째, 2p+1번째, …에서 시작하는 w들과만 겹치는 것을 확인할 수 있다. (위 예시의 경우 p=3) 참고로 앞서 본 w가 항상 겹치지 않는 “복잡하지 않은” 경우는 p=m으로 둔다.

그러면 p<m인 경우 \text{Pr}(A_i \vee A_j) 같은 값은 조금 더 복잡하게 수정되어야 하는데, 여기서 앞서 눈여겨본 이 풀이의 장점, 즉 w의 구조만 같다면 그 식은 동일하게 나온다는 원리를 또 다시 적용할 수 있다. 즉, 만약 두 워드 w_1, w_2가 같은 순환주기 p를 갖는다면 이 둘에 대한 \text{Pr}(A_i \vee A_j)는 뭔가 복잡한 꼴이 되겠지만 확실한건 이들이 일치한다는 것이다. 이는 물론 \text{Pr}(A_i \vee A_j \vee A_k) 이후의 항들에 대해서도 마찬가지. 예컨대 두 단어가 AUUA일 때와 UCGU일 때 둘 다 m=4, p=3인 경우로 일치하기 때문에 포함과 배제의 원리에 등장하는 식들이 전부 일치하게 되어 같은 확률(경우의 수)을 갖게 된다.

따라서, 만약 w의 길이가 m, 순환주기가 p로 주어졌다면 0,1 \in \Sigma라 할 때 M_wM_{01^{p-1}01^{p-1} \cdots}는 같은 특성방정식을 얻게 된다. 이 행렬의 경우 \det(M-\lambda I)를 Gauss elimination으로 쉽게 구할 수 있고, 그 결과 다음과 같은 결과를 얻는다.

Proposition. w의 길이가 m, 순환주기가 p라면 M_w의 특성방정식은 \displaystyle (\lambda-s)(1+(\lambda-s)(\lambda^{m-1}+\lambda^{m-p-1}+\lambda^{m-2p-1}+\cdots)) 가 된다.

위에서 등장한 다항식들은 전부 s보다 약간 작은 실수해를 하나 갖는데, 이게 s를 제외하고 절대값이 최대인 해임을 확인할 수 있다. 이 결과를 이용해서 고려해야할 m개의 다항식들의 최대해를 비교하면, 문제에서 요구하는 극한이 최대인 경우는 p=1(1+(\lambda-s)(\lambda^{m-1}+\lambda^{m-2}+\cdots+1)=0의 최대의 실수해), 최소인 경우는 p=m(1+(\lambda-s)\lambda^{m-1}의 최대의 실수해)인 것을 확인할 수 있게 된다.

랜덤 워드에서 특정 워드가 등장할 확률 (2)”의 1개의 생각

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중