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

이전 글: (1), (2)

이전 글에서는 알파벳 집합이 \Sigma, 그 사이즈가 s로 정해져있을 때 특정 워드 w가 들어가지 않는 길이 n의 워드 개수는 1+(\lambda-s)(\lambda^{m-1}+\lambda^{m-p-1}+\cdots)의 해들로 표현될 수 있음을 보였다. (mw의 길이, pw의 순환주기) 이 특성방정식을 \lambda에 대해 미분한 식과 이 식이 공통근을 갖지 않으므로 중근이 없어, 더 정확히 말하자면 이 해들의 거듭제곱의 선형합이라 할 수 있다. 여기서는 구체적으로 어떤 선형합이 되는지를 살펴보기 위해 생성함수(generating function)를 따져보기로 한다.

편의상 x^{m-1}+x^{m-p-1}+\cdotsA(x)로 두도록 한다. 또한 편의상 M_{01^{p-1}01^{p-1}\cdots} = M으로 표기한다. 그러면 이전 글에서 워드 w가 등장하는 경우의 수는 M^n(0,m)-entry임을 보였다. 이 경우의 수 f(n)에 대한 생성함수 F(x)=\sum_{n \geq 0} f(n) x^{-n}

\begin{aligned} \displaystyle F(x) =& \sum_{n \geq 0} f(n) x^{-n} = \sum_{n \geq 0} (M^n)_{(0,m)} x^{-n} = \left( \sum_{n \geq 0} x^{-n}M^n \right)_{(0,m)} = \left( I - x^{-1}M \right)^{-1}_{(0,m)} \\ =& x \left( xI - M \right)^{-1}_{(0,m)} = \frac{x}{\det(xI-M)} \text{adj}(xI-M)_{(0,m)} \end{aligned}

가 된다. 여기서 분모의 행렬값이 바로 M의 특성방정식 (x-s)(1+(x-s)A)가 되고, adj의 (0,m)-entry는 곧 (m,0)-cofactor에 (-1)^m을 곱한 값이 된다. 그런데 이 (m,0)-cofactor는 주대각선이 전부 -1인 triangular matrix의 행렬값, 즉 (-1)^m이 되므로 결국

\displaystyle F(x) = \frac{x}{(x-s)(1+(x-s)A)}

를 얻는다. 즉 w를 포함하는 경우의 수의 생성함수는 \displaystyle F(x) = \frac{x}{(x-s)(1+(x-s)A)}가 되고, 포함하지 않는 경우의 수의 생성함수는 \displaystyle \frac{x}{x-s} - F(x) = \frac{xA}{1+(x-s)A}가 된다.

이제 여기서 조금 결과를 확장해서, 포함하지 않았으면 하는 워드가 w 하나가 아니라 둘 이상으로 주어진 경우는 어떻게 되는지에 대해 생각할 수 있다. 사실 이에 대해서는 Guibas와 Odlyzko가 해결한 바가 있다.[1] 여기서는 이 논문의 main theorem에 대해서 증명 없이 설명하고자 한다.

두 워드 X,Y에 대해 둘의 상관관계 XY를 정의한다. 이 상관관계는 X의 길이가 n이라 할 때 길이 n의 0과 1로 이루어진 이진수열로 정의되는데, Xi번째 위치에 Y를 놓았을 때 둘이 완벽하게 겹치면 이 이진수열의 i번째 값을 1, 아니면 0으로 정의한다. 예를 들어 알파벳이 H와 T이고 X=HTHTTH, Y=HTTHT이면 XY=001001이며 YX=00010이다. 이를 x진법으로 읽은 결과를 XY_x로 표기한다. 이 값은 x에 대한 다항식이 되는데 앞에서 잡은 예시에서는 각각 XY_x=x^3+1, YX_x=x가 된다.

이제 워드의 집합 \{w_1,w_2,\ldots,w_t\}가 주어져있다고 한다. 여기서 w_iw_j의 subword가 되는 경우가 없다고 하고, 이 w_i들을 전부 포함하지 않는 길이 n의 워드 개수를 f(n)이라 하고, 길이 n의 워드 중 맨 마지막에 w_i가 등장하고 이걸 제외하면 모든 w_1,\ldots,w_n들이 등장하지 않는 경우의 수를 f_i(n)이라 한다. 그리고 각각의 생성함수를 F(x)=\sum_{n \geq 0}f(n)x^{-n}, F_i(x)=\sum_{n \geq 0}f_i(n)x^{-n}으로 두도록 한다. 또한 w_i들의 correlation들로 이루어진 행렬 C_{ij}=(w_i w_j)_x를 잡는다. 그러면 이 t+1개의 생성함수들은 다음 연립방정식을 만족해야 한다.

\displaystyle \begin{aligned} (x-s)F(x)+xF_1(x)+xF_2(x)+\cdots+xF_t(x) =& x \\ F(x)-xC_{11}F_1(x)-xC_{21}F_2(x)-\cdots-xC_{t1}F_t(x) =& 0 \\ \vdots & \\ F(x)-xC_{1n}F_1(x)-xC_{2n}F_2(x)-\cdots-xC_{tt}F_t(x) =& 0 \end{aligned}

이는 앞에서 구한 결과의 일반화인 것을 알 수 있다. 즉 만약 t=1이었으면 이 연립방정식을 풀어 F(x) = \frac{xC_{11}}{1+(x-s)C_{11}}가 되는데, 실은 이 self-correlation C_{11}이 바로 앞에서 잡았던 A(x)와 일치하게 되는 것.

References

[1] L. J. Guibas and A. M. Odlyzko, “String Overlaps, Pattern Matching, and Nontransitive Games” Journal of Combinatorial Theory, Series A 30, 183-208 (1981). https://core.ac.uk/download/pdf/81142890.pdf

답글 남기기

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

WordPress.com 로고

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

Google photo

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

Twitter 사진

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

Facebook 사진

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

%s에 연결하는 중