coincide-index_method.tex

\section{Метод индекса совпадений}
\selectlanguage{russian}
\label{chap:coincide-index}

Приведём теоретическое обоснование метода индекса совпадений. Пусть алфавит имеет размер $A$. Пронумеруем его буквы числами от $1$ до $A$. Пусть заданы вероятности появления каждой буквы
    \[ \mathcal{P} = \left\{ {p_1 ,p_2 , \ldots , p_A } \right\}. \]
В простейшей модели языка предполагается, что тексты состоят из последовательности букв, порождаемых источником независимо друг от друга с известным распределением $\mathcal{P}$.

Найдём индекс совпадений для различных предположений относительно распределений букв последовательности. Сначала рассмотрим случай, когда вероятности всех букв одинаковы. Пусть
    \[ \mathbf{X} = \left[ X_1, X_2, \dots, X_L \right] \]
случайный текст с распределением
    \[ \mathcal{P}_1 = \left\{ p_{11}, p_{12}, \dots, p_{1A} \right\}. \]
Найдём индекс совпадений
    \[ I_c(\mathcal{P}_1), \]
то есть вероятность того, что в случайно выбранной паре позиций находятся одинаковые буквы.

Для пары позиций $(k,j)$ найдём условную вероятность $P \left( X_k  = X_j \mid (k,j) \right)$:
    \[ P \left( X_k  = X_j \mid (k,j) \right) ~=~ \sum\limits_{i=1}^A p_{1i}^2 ~\equiv~ k_{p_1}. \]
Эта вероятность не зависит от выбора пары позиций $(k,j)$.

Так как число различных пар равно $\frac{L(L - 1)}{2}$, то вероятность случайного выбора пары $(k,j)$ равна
    \[ P_{(K,J)} (k,j) = \frac{2}{L(L - 1)}. \]
Следовательно,
\[
    I(\mathcal{P}_1) ~= \sum \limits_{1 \leq k < j \leq L} P_{(K,J)}(k,j) ~\cdot~ P(X_k  = X_j \mid (k,j)) =
\] \[
    = \sum \limits_{1 \leq k < j \leq L} \frac{2}{L(L - 1)} k_{p_1} = k_{p_1}.
\]

Найдём теперь аналогичную вероятность $I\left( {\mathcal{P}_1 ,\mathcal{P}_2 } \right)$ для случая, когда последовательность независимых случайных букв может быть представлена в виде
\[
\mathbf{X} = \left[ {\begin{array}{*{20}c}
   {X_1 ,}  \\
   {Y_1 ,}  \\
 \end{array} \begin{array}{*{20}c}
   {X_2 ,}  \\
   {Y_2 ,}  \\
 \end{array} \begin{array}{*{20}c}
   { \ldots ,}  \\
   { \ldots ,}  \\
 \end{array} \begin{array}{*{20}c}
   {X_{L/2} }  \\
   {Y_{L/2} }  \\
 \end{array} } \right],
\]
где одинаково распределённые случайные буквы в первой строке имеют распределение
    \[ \mathcal{P}_1  = \left\{ {p_{11} ,p_{12} , \ldots , p_{1A} } \right\}, \]
а одинаково распределённые случайные буквы во второй строке имеют другое распределение
    \[ \mathcal{P}_2  = \left\{ {p_{21} ,p_{22} , \ldots , p_{2A} } \right\}. \]
В этом случае сумму по всем парам мы разделяем на три суммы: по парам внутри позиций первой строки, по парам внутри позиций второй строки и по парам, в которых первая позиция берётся из первой строки, а вторая -- из второй:
{ \small
\[
    I(\mathcal{P}_1, \mathcal{P}_2) =
        \frac{2}{L(L - 1)} \cdot \left(
        \sum \limits_{1 \leq k < j \leq L/2} P( X_k  = X_j \mid ( k,j )) ~~ + \right.
\] \[
        \left. + \sum\limits_{1 \leq k < j \leq L/2} P(Y_k  = Y_j \mid (k,j)) ~~+~~
            \sum\limits_{k=1}^{L/2} \sum\limits_{j=1}^{L/2} {P(X_k = Y_j \mid (k,j))} \right) =
\] \[
    = \frac{2}{L(L - 1)} \left( \frac{1}{2} \frac{L}{2} \left( \frac{L}{2} - 1 \right) k_{p_1} +
        \frac{1}{2} \frac{L}{2} \left( \frac{L}{2} - 1 \right) k_{p_2} +
        \left( \frac{L}{2} \right)^2 \sum \limits_{i = 1}^A p_{1,i} p_{2,i} \right) =
\] \[
    = \frac{2}{L(L - 1)} \left( \frac{1}{2} \frac{L}{2} \left( \frac{L}{2} - 1 \right) k_{p_1} +
        \frac{1}{2} \frac{L}{2} \left( \frac{L}{2} - 1 \right) k_{p_2} +
        \left( \frac{L}{2} \right)^2 k_{p_1, p_2} \right),
\] }
где обозначено
    \[ k_{p_1, p_2}  = \sum\limits_{i=1}^A p_{1,i} p_{2,i}. \]


В общем случае рассмотрим последовательность, представленную в виде матрицы, состоящей из $m$ строк и $\frac{L}{m}$ столбцов, где
\[
{\mathbf X} = \left[ {\begin{array}{*{20}c}
   {X_1 } & {X_2 } &  \cdots  & {X_{L/m} }  \\
   {Y_1 } & {Y_2 } &  \cdots  & {Y_{L/m} }  \\
    \vdots  &  \vdots  &  \vdots  &  \vdots   \\
   {Z_1 } & {Z_2 } &  \cdots  & {Z_{L/m} }  \\
\end{array}} \right].
\]
Считаем, что одинаково распределённые случайные буквы в первой строке имеют распределение
    \[ P_1  = \left\{ {p_{11} ,p_{12} , \ldots , p_{1A} } \right\}, \]
одинаково распределённые случайные буквы во второй строке имеют распределение
    \[ P_2  = \left\{ {p_{21} ,p_{22} , \ldots , p_{2A} } \right\} \]
и т.~д., одинаково распределённые случайные буквы $m$-й строки имеют распределение
    \[ P_m  = \left\{ {p_{m1},p_{m2} , \ldots , p_{mA} } \right\}. \]

Для вычисления вероятности того, что в случайно выбранной паре позиций будут одинаковые буквы, выполним суммирование по различным парам внутри строк и по парам между различными строками. Аналогично предыдущему случаю получим:
\[\begin{array}{l}
	I(\mathcal{P}_1, \mathcal{P}_2, \ldots, \mathcal{P}_m ) ~= \\
	~=~ \frac{2}{L(L - 1)} \left( \frac{L}{2m} \left( \frac{L}{m} - 1 \right) k_{p_1} ~+~ \frac{L}{2m} \left( \frac{L}{m} - 1 \right) k_{p_2} ~+ \right. \\
	~~+~ \dots ~+~ \left. \frac{L}{2m} \left( \frac{L}{m} - 1 \right) k_{p_m} \right) ~+ \\
	~~+~ \frac{2}{L(L - 1)} \left( \left( \frac{L}{m} \right)^2 k_{p_1, p_2} + \left( \frac{L}{m} \right)^2 k_{p_1, p_3} + \dots + \left( \frac{L}{m} \right)^2 k_{p_{m - 1}, p_m } \right).
\end{array}\]

Первая сумма содержит $m$ слагаемых, вторая -- $ \frac{m(m-1)}{2}$ слагаемых. Полагая
    \[ k_{p_1} = k_{p_2} = \dots = k_{p_m} = k_p, \]
    \[ k_{p_i p_j } = k_r = \frac{1}{A}, ~ i \ne j, \]
получим после несложных выкладок
    \[ m = \frac{k_p  - k_r}{I - k_r  + \frac{k_p  - I}{L}}. \]