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

이전 글: (1), (2)

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

편의상 $x^{m-1}+x^{m-p-1}+\cdots$ 를 $A(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로 이루어진 이진수열로 정의되는데, $X$ 의 $i$ 번째 위치에 $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_i$ 가 $w_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

월	화	수	목	금	토	일
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28

References

이 글 공유하기:

이것이 좋아요:

관련

답글 남기기 응답 취소