Proof: For each 1 ::: m 

$\Pi\left(x_{i,\alpha}\right)\ f_{i,\alpha}()$
fi, (xi,, , Π(xi,)),
where x i i , x i 2 , and  x i 3 correspond to the three variables that occur in the 3-module M m .

Therefore, there are 3 t possible matches for the t-3-module.

To prove the second conclusion, we divide the t-3-module into 3 parts M = ( M 1 , M 2 , M 3 ),
where M 1 = (M m, 1 ≤ m ≤ p), M 2 = (M m,p + 1 ≤ m ≤ 3p − 1), and M 3 =
( M 3p , M 3p +1 , M 3p +2 ). Letting L 1 , L 2 , and L 3 be the number of legal possible matches for M 1 , M 2 , M 3 respectively. Since the literals in M 1 are variable-distinct from the literals in M 2 , we have that the number of legal possible matches, L , for the t-3-module M satisfies L1L2 ≤ L ≤ 27L1L2.

We now estimate the order of L 1 . To this end, we consider the probability space ( Ω, P ),
where Ω is the set of sequences ( g 1 ,    , g p ) of local fitness functions that possibly match M 1 and P is the uniform probability distribution. Then, the number of legal possible matches is

$$\Omega\;\;\mathrm{is~legal}\}$$
$\left(4,5\right)$ . 
$$L_{\mathrm{\scriptsize~1}}=|\Omega|\cdot P r\left\{\mathrm{a\,\,\,ra}\right.$$

L 1 = [Ω]  Pr{a random sample from Ω  is legal}
Let g = ( g 1 , . . , g g ) be a random sample from Ω and x om denote the main variable of the local fitness function gm, then we have

$Pr\left\{x_{g_{m}}=\left|u_{m}\right|\right\}=Pr\left\{x_{g_{m}}=\left|u_{m+1}\right|\right\}=Pr\left\{x_{g_{m}}=\left|z_{m}\right|\right\}=\frac{1}{3}$,
where [ u ] denotes the variable corresponding to the literal u .

Let Bm, 0 < m < p be the event that the first m local fitness functions g1, . . , gm in the possible match g = ( g 1 , . .g p ) are mutually distinct. Since in M 1 only consecutive 3-modules share variables, we have

$B_{m}=\{(g_{1},\cdots,g_{m}):\ g_{i}\neq g_{i+1},\ 1\leq i\leq m-1\}$.  
Let bm = Pr { gm ≠ gm-1 | Bm-1 }, m ≥ 2,  and b1 = 1. Notice that B1 = Ω. Then, we have Pr {g = (g1,      , gp) is legal} = Pr {Bp}

$$=\,P r\,\{g_{1}\,\neq g_{2},g_{2}\,\neq g_{3}\,,\,\cdot\,\cdot\,\,,\,g_{p-1}\,\neq g_{p}\,\}$$
$$=Pr\left\{y_{1}\neq y_{2},y_{2}\neq y_{3},\cdots,y_{p-1}\neq y_{p}\right\}\tag{4.6}$$ $$=Pr\left\{B_{1}\right\}Pr\left\{g_{2}\neq g_{1}\mid B_{1}\right\}\cdot Pr\left\{g_{3}\neq g_{2}\mid B_{2}\right\}\cdots Pr\left\{g_{p}\neq g_{p-1}\mid B_{p-1}\right\}$$ $$=b_{1}b_{1}\cdots b_{n}$$

Recalling that x gm  denotes the main variable of the local fitness function gm, we have

$$=Pr\left\{g_{p-1}\neq g_{p},x_{g_{p-1}}=\left|u_{p}\right|\mid B_{p-1}\right\}+Pr\left\{g_{p-1}\neq g_{p},x_{g_{p-1}}\neq\left|u_{p}\right|\mid B_{p-1}\right\}$$ $$=Pr\left\{g_{p-1}\neq g_{p}\mid B_{p-1},x_{g_{p-1}}=\left|u_{p}\right|\right\}\cdot Pr\left\{x_{g_{p-1}}=\left|u_{p}\right|\mid B_{p-1}\right\}+$$ $$Pr\left\{g_{p-1}\neq g_{p}\mid B_{p-1},x_{g_{p-1}}\neq\left|u_{p}\right|\right\}\cdot Pr\left\{x_{g_{p-1}}\neq\left|u_{p}\right|\mid B_{p-1}\right\}$$
$$\begin{array}{r l}{{}}&{{}\quad\cdot\quad}\\ {={}}&{{}{\frac{2}{3}}a_{\,p}+\left(1\,-\,a_{\,p}\right)}\end{array}$$
$$\begin{array}{r l}{={}}&{{}1\,-\,{\frac{1}{3}}a_{\,p},}\end{array}$$
$$(4.7)$$

$$320$$
