Since x g is already one of the variables in the 3-module, the probability that Proof :
the other two variables are also in the 3-module is 7 x 1 Now, assume that the variables of the local fitness function g are the same as the variables in the 3-module. From the definition of the fixed ratio model, g has two zeros in its fitness value assignment with probability (1 - α), and has three zeros in its fitness assignment with probability α . Note that the local fitness function g implies the 3-module x Vy V w, x Vy V w if and only if

$$g\bigl(\,\bar{x},\,\bar{y},\,\bar{w}\,\bigr)=0\;\;\;\mathrm{and}\;\;\;\;g\bigl(\,\bar{x},\,\bar{y},\,w\,\bigr)=0.$$

From the definition of the fixed ratio model, this happens with the probability

$${\frac{1}{{\binom{8}{2}}}}(1\,-\,\alpha)+{\frac{6}{{\binom{8}{3}}}}\alpha$$

The Lemma follows.

□
With the above preparation, we can now prove that the average number of t-3-modules contained in N ( n, 2, z ) tends to infinity.

Theorem 4.2. Let A t be the number of t-3-modules contained in N ( n, 2, z ) and t = Θ( ln 2 n ).

Then, if z = 2 + a > 2.837,

$$\operatorname*{lim}_{n\to\infty}E\left\{A_{t}\right\}=\infty\,.$$
$$(4\,,1\,6)$$

Proof ;  From Lemma 4.2, there are more than ( ³± √ √ ) f legal possible matches for a fixed t-3-module. From Lemma 4.3, we know that each possible legal match g = { g1, . . , g1 } implies the t-3-module with probability p . From the proof of Theorem 10.1 in (Franco & Gelder, 1998), there are

$$2^{\,t-2}n\frac{t-1}{-}(n-t+1)^{t}\tag{4.17}$$ $$=\frac{n!}{(n-t+1)!}.\ \ \mbox{Let}\ r=\Big{(}\frac{1}{28}(1-\alpha)+\frac{6}{56}\alpha\Big{)},\ \mbox{and write}\ p_{0}=$$
$$(4\,,1\,7)$$

possible t-3-modules, where nt-1 r. We have

E{At} (4.18)