arXiv:0704.0197v1  [nlin.CG]  2 Apr 2007
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
Analysis of random Boolean networks using the
average sensitivity
Steffen Schober∗ and Martin Bossert
Institute of Telecommunications and Applied Information Theory, Ulm University
Albert-Einstein-Allee 43, 89081 Ulm, Germany
November 4, 2018
Abstract
In this work we consider random Boolean networks that provide a
general model for genetic regulatory networks. We extend the analysis of
James Lynch who was able to proof Kauffman’s conjecture that in the
ordered phase of random networks, the number of ineffective and freezing
gates is large, where as in the disordered phase their number is small.
Lynch proved the conjecture only for networks with connectivity two and
non-uniform probabilities for the Boolean functions. We show how to
apply the proof to networks with arbitrary connectivity K and to random
networks with biased Boolean functions. It turns out that in these cases
Lynch’s parameter λ is equivalent to the expectation of average sensitivity
of the Boolean functions used to construct the network. Hence we can
apply a known theorem for the expectation of the average sensitivity. In
order to prove the results for networks with biased functions, we deduct
the expectation of the average sensitivity when only functions with specific
connectivity and specific bias are chosen at random.
Keywords: Random Boolean networks, phase transition, average sensitivity
PACS numbers: 02.10.Eb, 05.45.+b, 87.10.+e
1 Introduction
In 1969 Stuart Kauffman started to study random Boolean networks as simple
models of genetic regulatory networks [1]. Random Boolean networks that con-
sists of a set of Boolean gates that are capable of storing a single Boolean value.
At discrete time steps these gates store a new value according to an initially
chosen random Boolean function, which receives its inputs from random chosen
gates. We will give a more formal definition later. Kauffman made numerical
∗Corresponding author. E-Mail: Steffen.Schober@uni-ulm.de
http://arxiv.org/abs/0704.0197v1
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
studies of random networks, where the functions are chosen from the set of all
Boolean functions with K arguments (the so called NK-Networks). He recog-
nised that if K ≤ 2, the random networks exhibit a remarkable form of ordered
behaviour: The limit cycles are small, the number of ineffective gates, which are
gates that can be perturbed without changing the asymptotic behaviour, and
the number of freezing gates that stop changing their state is large. In contrast
if K ≥ 3, the networks do not exhibit this kind of ordered behaviour (see [1, 2]).
The first analytical proof for this phase transition was given by Derrida and
Pomeau (see [3]) by studying the evolution of the Hamming distance of random
chosen initial states by means of so called annealed approximation. The first
proof for the number of freezing and ineffective gates was given by James Lynch
(see [4], although slightly weaker results appeared earlier [5, 6]). Depending on
a parameter λ, that depends on the probabilities of the Boolean functions, he
showed that if λ ≤ 1 almost all gates are ineffective and freezing, otherwise not.
Although his analysis is very general, until now it was only applied to networks
with connectivity 2 and non-uniform probabilities for the Boolean function: if
the probability of choosing a constant function is larger or equal the probability
of choosing a non-constant non-canalizing function (namely the XOR- or the
inverted XOR-function), λ is less or equal to one. But it turns out that in some
cases λ is equal to the expectation of the average sensitivity. Therefore we will
first study the average sensitivity in Section 3. Afterwards it will be shown
in Section 4 how to use the results from the previous section to apply Lynch’s
analysis to classical NK-Networks and biased random Boolean networks 1. But
first we will give some basic definition used throughout the paper in Section 2.
2 Basic Definitions
In the following F2 = {0, 1} denotes the Galois field of two elements, where
addition, denoted by ⊕, is defined modulo 2. The set of vectors of length K
over F2 will be denoted by F
2 . If x is a vector from F
2 , its ith component
will be denoted by xi. With u
(i) ∈ FK2 we will denote the unit vector which has
all components zero except component i which is one. The Hamming weight of
x ∈ FK2 is defined as
wH(x) = |{i | xi 6= 0, i = 1, . . . ,K}|
and the Hamming distance of x,y ∈ FK2 as
dH(x,y) = wH(x⊕ y).
A Boolean function is a mapping f : FK2 → F2. A function f may be represented
by its truth table tf , that is, a vector in F
2 , where each component of the truth
table gives the value of f for one of the 2K possible arguments. To fix an order
on the components of the truth table, suppose that its ith component equals
the value of the corresponding function, given the binary representation (to K
bits) of i as an argument.
1a definition will be given later
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
3 Average Sensitivity
In this section we will focus on the average sensitivity. The average sensitivity
is a known complexity measure for Boolean functions, see for example [7]2. It
was already used to study Boolean and random Boolean networks for example
in [8, 9].
Definition 1. Let f denote a Boolean function FK2 → F2 and u
(i) a unit vector.
1. The sensitivity sf(w) is defined as:
sf (w) =
i | f(w) 6= f(w⊕ u(i)), i = 1, . . . ,K
2. The average sensitivity sf is defined as the average of sf (w) over all w ∈
sf = 2
sf (w)
Now consider the random variable FK : Ω → FK, where FK denotes the set
a all 22
Boolean function with K arguments. The probability measure is given
by P (FK = f) =
K . The expected value of the average sensitivity of this
random variable is denoted by EFK (sf ), and is given by
EFK (sf ) =
P (FK = f)sf
The expected value was already derived in [10], and is given by:
Theorem 1 (Bernasconi [10]).
Let the random variable FK be defined as above, then
EFK (sf ) =
P (FK = f)sf =
We will now concentrate on biased Boolean functions. The bias of a Boolean
function f : FK2 → F2 is defined as the number of 1 in the functions truth table
divided by 2K . To define the bias of a random Boolean function two definitions
are possible. First we can assumes that the truth tables of the Boolean functions
are produced by independent Bernoulli trials with probability p for a one (This
should be called mean bias, used for example in [3, 8] ). Therefore consider the
random variable FK,p. The probability of choosing a function f is given by
P (FK,p = f) = p
wH(tf )(1− p)2
K−wH(tf )
For p = 1/2 this is equivalent to the definition of FK .
2here it is called critical complexity
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
As a second possibility, we can only choose functions which have bias p
whereas to all other functions we assign probability 0 (we will call this fixed
bias). Therefore consider the random variables F fixedK,p : Ω → FK. Denote the
truth table of a function f by tf . Further denote the set of all Boolean functions
f with K arguments and wH(tf ) = p2
K with FK,p. The probability for a certain
function chosen according F fixedK,p is given by
P (F fixedK,p = f) =
|FK,p|
if f ∈ FK,p
0 if f /∈ FK,p
Both definitions ensure that the expectation to get a one is equal to p if the
input of a function is chosen at random (with respect to uniform distribution).
But it will turn out that these two different methods of creating biased Boolean
functions, have a major impact on the average sensitivity.
The expectation of the average sensitivity of FK,p was derived in [8]:
Theorem 2 ([8]). Let the random variable FK,p be defined as above:
EFK,p(sf ) = 2Kp(1− p)
For the random variable F fixedK,p we will now proof the following theorem:
Theorem 3. Let the random variable F
fixed
be defined as above:
fixed
(sf ) =
2K+1Kp(1− p)
(2K − 1)
Proof. To find EF fixed
(sf ) we will first consider the random variable FK,t : Ω →
FK where t ∈ {0, 1, · · · , 2
K} and the probability of a function is given by
P (FK,t = f) =
if wH(tf ) = t
0 else
Consider the Boolean functions as functions into R by identifying 0, 1 ∈ F2
with 0, 1 ∈ R. Then we get or the function f :
sf = 2
i | f(w) 6= f(u(i) ⊕w), i = 1, . . . ,K
= 2−K
(f(w)− f(w⊕ u(i)))2
= 2−K
(f(w) + f(w⊕ u(i))− 2f(w)f(w⊕ u(i))).
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
where u(i) again denotes the unit vector with ith component set to 1. Hence by
the linearity of the expectation
EFK,t(sf ) = 2
EFK,t(f(w)) + EFK,t(f(w ⊕ u
(i)))
− 2EFK,t(f(w)f(w ⊕ u
(i)))
Now we form a matrix with the truth tables of all functions with Hamming
weight t as column vectors:
c(1), c(2), · · · , c((
where c(i) ∈ F2
M has exactly
columns and 2K rows. Each entry Mi,j in the ith row and
jth column equals the value of function fj given the binary representation of i
as input.
Hence EFK,t(f(w)) is determined by the number of 1 in the row associated
with w divided by the length of the row. Consider an arbitrary row i. This row
has a one at position j if the corresponding column c(j) has a one at position i.
But there are
column vectors with a 1 at position i. It follows:
∀w ∈ FK2 : EFK,t(f(w)) =
. (2)
As this holds for all w, we have
∀w,u(i) ∈ FK2 : EFK,t(f(w⊕ u
(i))) =
. (3)
To find an expression for EF fixed
(f(w)f(w⊕u(i))) we consider two arbitrary
rows l,m (l 6= m). Define the following sum:
γl,m =
(Kt )
Ml,iMm,i.
Obviously Ml,iMm,i = 1 only if we have a 1 in both rows at position i. This
means for the column vectors c(i) of M , we have c
m = 1. But there are
exactly
such column vectors in M . Therefore we have
∀l,m, l 6= m : γl,m =
2K − 2
As w 6= w ⊕ u(i) for all w,u(i) it follows:
EFK,t(f(w)f(w ⊕ u
(i))) =
t(t− 1)
2K(2K − 1)
. (4)
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
Hence substituting Equations (2), (3) and (4) into Equation (1) leads to
EFK,t(sf ) =
K(2K − t)t
2K−1(2K − 1)
Finally the claimed expression for EF fixed
(sf ) can be obtained from the above
equation by a substitution of t: t → p2K .
It should be noted, that the Theorems 1 and 2 can be proved using in a
similar way. Also worth noting is the fact, that if the functions are chosen
according FK , F
fixed
K,p or FK,p the expectation of the sensitivity of a fixed vector
w (namely the expectation of sf (w)) is independent of w (see Equation (1),(2),
(3) and (4)). Hence the following lemma holds
Lemma 1. If F = FK , F
fixed
or FK,p, then
∀w,v ∈ FK2 : EF (sf (w)) = EF (sf (v))
Before proceeding to the next section, it should be noted, that using the same
arguments as in the proof of Theorem 3, we can also prove the expectation of
average sensitivity of order l , defined as
s(l)(f) = 2−K
x ∈ FK2 |wH(x) = l and f(w) 6= f(w⊕ x)
In this case, instead of summing up all unit vectors in Equation (1), we sum
up all vectors of Hamming weight l. As the equations (2) and (4) hold for all
w ∈ FK2 we conclude that
E(s(l)(F fixedK,p )) =
2K+1p(1− p)
(2K − 1)
and by similar arguments
E(s(l)(FK,p)) =
2p(1− p)
respectively
E(s(l)(FK)) =
4 Extending Lynch’s analysis
As already mentioned James Lynch gave a very general analysis of randomly
constructed Boolean networks (see [4]). Before stating his results we give a
formal definition for Boolean networks A Boolean network B is a 4-tuple
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
(V,E, F̃ ,x) where V = {1, ..., N} is a set of natural numbers, E is a set of
labeled edges on V , F̃ = {f1, ..., fN} is a ordered set of Boolean functions such
that for each v ∈ V the number of arguments of fv is the in-degree of v in
E, these edges are labeled with 1, ..., in-degree(v), and x = (x1, . . . xn) ∈ F
Suppose that a vertex i has Ki in-edges from vertices vi,1, . . . , vi,Ki . For y ∈ F
we define
B(y) =
f1(yv1,1 , . . . , yv1,K1 ), . . . , fN(yvN,1 , . . . , yvN,KN )
The state of B at time 0 is called the initial state x, so we define B0(x) = x. For
time t ≥ 1 the state is inductively defined as Bt(x) = B(Bt−1(x)). Hence we
can in interpret V as set of gates, E and F̃ describes their functional dependence
and x is the networks initial state.
Assume some ordering f1, f2, ... on the set of all Boolean functions F , where
each function fi depends on Ki arguments. Further a random variable F : Ω →
F with probabilities pi = P (F = fi) such that
i=i pi = 1 and
i=1 piK
∞. Now a random Boolean network consisting of N gates is constructed as
follows: For each gate a Boolean function is chosen independently, where the
probability of choosing fi is given by pi. Suppose a function f was chosen that
has K arguments, these arguments are chosen at random from all
equally
likely possibilities. At last an initial state is chosen at random from the set on
all equally likely states. If the Boolean functions are chosen according to our
previously defined random variable FK we will call this networks NK-Networks
with connectivity K. If the functions are chosen according to F fixedK,p or FK,p
we will call this networks biased random Boolean networks with connectivity K
and fixed bias p respectively mean bias p.
Let us now state Lynch’s results. His analysis depends on a parameter
R ∋ λ ≥ 0 depending only on the functions and their probabilities. We will
define λ later in Definition 3. First we have to state Lynch’s definition of
freezing and ineffective gates:
Definition 2 (Lynch [4] Definition 1 Item 2 and 5).
Let x ∈ FN2 and v ∈ V .
1. Gate v freezes to y ∈ FN2 in t steps on input x if B
v (x) = y for all t
′ ≥ t.
2. Let u(i) ∈ Fn2 .
A gate v is t-ineffective at input x ∈ FK2 if B
t(x) = Bt(x⊕ u(v)).
Now we will state the main result.
Theorem 4 (Lynch [4] Theorem 4 and 6).
Let α, β be positive constants satisfying 2α log δ+2β < 1 and α log δ < β where
δ = E(Ki).
1. There is a constant r such that for all x ∈ FN2
P (v is ineffective in α log N steps) = r
When λ ≤ 1, r = 1 and when λ > 1 , r < 1.
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
2. There is a constant r such that for all x ∈ FN2
P (v is freezing in α log N steps) = r
When λ ≤ 1, r = 1 and when λ > 1 , r < 1. 3
The above theorem shows that if λ ≤ 1 almost all gates are freezing and
ineffective and otherwise not. The next corollary gives us more information
what happens if λ > 1:
Corollary 1 (Lynch [4] Corollary 3 and Corollary 6). Let λ > 1. For almost
all random Boolean networks
1. if gate v is not α logN -ineffective, there is a positive constant W such that
for t ≤ α logN , the number of gates affected by v at time t is asymptotic
to Wλt,
2. if gate v is not freezing in α logN steps , there is a positive constant W
such that for t ≤ α logN , the number of gates that affect v at time t is
asymptotic to Wλt.
Now we will state the definition of λ for Boolean networks:
Definition 3 (Lynch [4], Definition 4). Let f be a Boolean function of K ar-
guments. For i ∈ {1, . . . ,K}, we say that argument i directly affects f on input
w ∈ FK2 if f(w) 6= f(w ⊕ u
(i)). Now put γ(f,w) as the number of i’s that
directly affect f on input w. Given a constant a ∈ [0, 1], we define
γ(fi,w)a
wH(w)(1− a)Ki−wH(w).
Obviously γ(f,w) is identical to sf (w) which will be used instead in the
further discussion. The constant a is the probability that a random gate is one
(at infinite time) given that all gates at time 0 have probability 0.5 of being one.
(see [4, Definiton 2]). Assume that we choose the functions according a random
variable F which should be either FK , F
fixed
K,p or FK,p. The functions are chosen
out the set FK , we denote a function’s probability with pf . It follows that
awH(w)(1− a)K−wH(w)
pfsf (w) (5)
awH(w)(1− a)K−wH(w)E(sF (w)) (6)
= E(sF (w))
ai(1− a)K−i (7)
= E(sF (w)) = EF (sf ) (8)
3Please note that we here state a slightly weaker result than in the original analysis.
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
E(sF (w)) denotes the expectation of the sensitivity for a fixed w, Equation (7)
follows from Lemma 1. Therefore, together with Theorem 1 and Theorem 3 we
proved the following:
Theorem 5 (Biased random Boolean networks). For random Boolean networks,
1. the functions are chosen according random variable FK,p, it follows that
λ = 2Kp(1− p),
2. the functions are chosen according random variable F
fixed
, it follows that
2K+1Kp(1− p)
2K − 1
As a special case of the above theorem we get (or by using Theorem 1)
Theorem 6 (NK-Networks). In random Boolean networks, where the functions
are chosen according to the random variable FK
5 Discussion
The results about NK-Networks are consistent with experimental results. In
fact if K ≤ 2 almost all networks almost all gates are freezing and almost all
gates are ineffective and otherwise not (see [2]).
Obviously, the border between the ordered and disordered phase is given
by λ = 1. The resulting phase diagram for biased random Boolean networks,
where the functions are chosen according to F fixedK,p and FK,p is shown in Figure
1. It it interesting to note that if the functions are chosen with fixed bias, then
also Boolean networks with connectivity K = 2 can become unstable. This
conclusion can be drawn from Lynch’s original result already. As mentioned in
the introduction, he showed for K = 2, that λ > 1 if the probability of choosing
a non-constant non-canalizing function, namely the XOR or the inverted XOR
function, is larger than the probability of choosing a constant function. For
example if the bias is 0.5, the probability of choosing a constant function is
zero, whereas both XOR and inverted XOR function have probability greater
zero, hence λ > 1.
It is interesting to compare our results with previous results obtained first
by Derrida and Pomeau using the so called annealed approximation (see [3]).
In their annealed model the functions and connections are chosen at random
at each time step. Considering two instances of the same annealed network
starting in two randomly chosen initial states s1(0), s2(0) they show that
dH(s1(t), s2(t))
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
1 3 4 52
Figure 1: Phase diagram for biased random networks: Functions chosen accord-
ing FK,p (dashed) and F
fixed
K,p (solid)
where c = 1 if
2Kp(1− p) ≤ 1
and c ≤ 1 otherwise. It is remarkable that the two models behave similar, but
it is unclear whether this holds in general.
6 Acknowledgement
We would like to thank our colleges Georg Schmidt and Stephan Stiglmayr for
proofreading and Uwe Schoening for useful hints.
References
[1] S. Kauffman, Metabolic stability and epigenesis in randomly constructed
nets, Journal of Theoretical Biology 22 (1969) 437–467.
[2] S. Kauffman, The large scale structure and dynamics of genetic control
circuits: an ensemble approach, Journal of Theoretical Biology 44 (1974)
167–190.
[3] B. Derrida, Y. Pomeau, Random networks of automata - a simple annealed
approximation, Europhysics Letters 2 (1986) 45–49.
[4] J. F. Lynch, Dynamics of random boolean networks, in: Conference on
Mathematical Biology and Dynamical Systems, University of Texas at
Tyler, 2005.
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
[5] J. F. Lynch, On the threshold of chaos in random boolean cellular au-
tomata, Random Structures and Algorithms (1995) 236–260.
[6] J. F. Lynch, Critical points for random boolean networks, Physica D: Non-
linear Phenomena 172 (1-4) (2002) 49–64.
[7] I. Wegener, The Complexity of Boolean Functions, Wiley-Teubner Series
in Computer Science, John Wiley, B.G. Teubner, 1987.
[8] I. Shmulevich, S. A. Kauffman, Activities and sensitivities in boolean net-
work models, Physical Review Letters 93 (4).
[9] S. Kauffman, C. Peterson, B. Samuelsson, C. Troeln, Genetic networks with
canalyzing boolean rules are always stable, Proceedings of the Nationial
Academy of Science 101 (49).
[10] A. Bernasconi, Mathematical techniques for the analysis of boolean func-
tions, Ph.D. thesis, Dipartimento di Informatica, Universita di Pisa (March
1998).

  In this work we consider random Boolean networks that provide a general model
for genetic regulatory networks. We extend the analysis of James Lynch who was
able to proof Kauffman's conjecture that in the ordered phase of random
networks, the number of ineffective and freezing gates is large, where as in
the disordered phase their number is small. Lynch proved the conjecture only
for networks with connectivity two and non-uniform probabilities for the
Boolean functions. We show how to apply the proof to networks with arbitrary
connectivity $K$ and to random networks with biased Boolean functions. It turns
out that in these cases Lynch's parameter $\lambda$ is equivalent to the
expectation of average sensitivity of the Boolean functions used to construct
the network. Hence we can apply a known theorem for the expectation of the
average sensitivity. In order to prove the results for networks with biased
functions, we deduct the expectation of the average sensitivity when only
functions with specific connectivity and specific bias are chosen at random.

Introduction
In 1969 Stuart Kauffman started to study random Boolean networks as simple
models of genetic regulatory networks [1]. Random Boolean networks that con-
sists of a set of Boolean gates that are capable of storing a single Boolean value.
At discrete time steps these gates store a new value according to an initially
chosen random Boolean function, which receives its inputs from random chosen
gates. We will give a more formal definition later. Kauffman made numerical
∗Corresponding author. E-Mail: Steffen.Schober@uni-ulm.de
http://arxiv.org/abs/0704.0197v1
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
studies of random networks, where the functions are chosen from the set of all
Boolean functions with K arguments (the so called NK-Networks). He recog-
nised that if K ≤ 2, the random networks exhibit a remarkable form of ordered
behaviour: The limit cycles are small, the number of ineffective gates, which are
gates that can be perturbed without changing the asymptotic behaviour, and
the number of freezing gates that stop changing their state is large. In contrast
if K ≥ 3, the networks do not exhibit this kind of ordered behaviour (see [1, 2]).
The first analytical proof for this phase transition was given by Derrida and
Pomeau (see [3]) by studying the evolution of the Hamming distance of random
chosen initial states by means of so called annealed approximation. The first
proof for the number of freezing and ineffective gates was given by James Lynch
(see [4], although slightly weaker results appeared earlier [5, 6]). Depending on
a parameter λ, that depends on the probabilities of the Boolean functions, he
showed that if λ ≤ 1 almost all gates are ineffective and freezing, otherwise not.
Although his analysis is very general, until now it was only applied to networks
with connectivity 2 and non-uniform probabilities for the Boolean function: if
the probability of choosing a constant function is larger or equal the probability
of choosing a non-constant non-canalizing function (namely the XOR- or the
inverted XOR-function), λ is less or equal to one. But it turns out that in some
cases λ is equal to the expectation of the average sensitivity. Therefore we will
first study the average sensitivity in Section 3. Afterwards it will be shown
in Section 4 how to use the results from the previous section to apply Lynch’s
analysis to classical NK-Networks and biased random Boolean networks 1. But
first we will give some basic definition used throughout the paper in Section 2.
2 Basic Definitions
In the following F2 = {0, 1} denotes the Galois field of two elements, where
addition, denoted by ⊕, is defined modulo 2. The set of vectors of length K
over F2 will be denoted by F
2 . If x is a vector from F
2 , its ith component
will be denoted by xi. With u
(i) ∈ FK2 we will denote the unit vector which has
all components zero except component i which is one. The Hamming weight of
x ∈ FK2 is defined as
wH(x) = |{i | xi 6= 0, i = 1, . . . ,K}|
and the Hamming distance of x,y ∈ FK2 as
dH(x,y) = wH(x⊕ y).
A Boolean function is a mapping f : FK2 → F2. A function f may be represented
by its truth table tf , that is, a vector in F
2 , where each component of the truth
table gives the value of f for one of the 2K possible arguments. To fix an order
on the components of the truth table, suppose that its ith component equals
the value of the corresponding function, given the binary representation (to K
bits) of i as an argument.
1a definition will be given later
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
3 Average Sensitivity
In this section we will focus on the average sensitivity. The average sensitivity
is a known complexity measure for Boolean functions, see for example [7]2. It
was already used to study Boolean and random Boolean networks for example
in [8, 9].
Definition 1. Let f denote a Boolean function FK2 → F2 and u
(i) a unit vector.
1. The sensitivity sf(w) is defined as:
sf (w) =
i | f(w) 6= f(w⊕ u(i)), i = 1, . . . ,K
2. The average sensitivity sf is defined as the average of sf (w) over all w ∈
sf = 2
sf (w)
Now consider the random variable FK : Ω → FK, where FK denotes the set
a all 22
Boolean function with K arguments. The probability measure is given
by P (FK = f) =
K . The expected value of the average sensitivity of this
random variable is denoted by EFK (sf ), and is given by
EFK (sf ) =
P (FK = f)sf
The expected value was already derived in [10], and is given by:
Theorem 1 (Bernasconi [10]).
Let the random variable FK be defined as above, then
EFK (sf ) =
P (FK = f)sf =
We will now concentrate on biased Boolean functions. The bias of a Boolean
function f : FK2 → F2 is defined as the number of 1 in the functions truth table
divided by 2K . To define the bias of a random Boolean function two definitions
are possible. First we can assumes that the truth tables of the Boolean functions
are produced by independent Bernoulli trials with probability p for a one (This
should be called mean bias, used for example in [3, 8] ). Therefore consider the
random variable FK,p. The probability of choosing a function f is given by
P (FK,p = f) = p
wH(tf )(1− p)2
K−wH(tf )
For p = 1/2 this is equivalent to the definition of FK .
2here it is called critical complexity
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
As a second possibility, we can only choose functions which have bias p
whereas to all other functions we assign probability 0 (we will call this fixed
bias). Therefore consider the random variables F fixedK,p : Ω → FK. Denote the
truth table of a function f by tf . Further denote the set of all Boolean functions
f with K arguments and wH(tf ) = p2
K with FK,p. The probability for a certain
function chosen according F fixedK,p is given by
P (F fixedK,p = f) =
|FK,p|
if f ∈ FK,p
0 if f /∈ FK,p
Both definitions ensure that the expectation to get a one is equal to p if the
input of a function is chosen at random (with respect to uniform distribution).
But it will turn out that these two different methods of creating biased Boolean
functions, have a major impact on the average sensitivity.
The expectation of the average sensitivity of FK,p was derived in [8]:
Theorem 2 ([8]). Let the random variable FK,p be defined as above:
EFK,p(sf ) = 2Kp(1− p)
For the random variable F fixedK,p we will now proof the following theorem:
Theorem 3. Let the random variable F
fixed
be defined as above:
fixed
(sf ) =
2K+1Kp(1− p)
(2K − 1)
Proof. To find EF fixed
(sf ) we will first consider the random variable FK,t : Ω →
FK where t ∈ {0, 1, · · · , 2
K} and the probability of a function is given by
P (FK,t = f) =
if wH(tf ) = t
0 else
Consider the Boolean functions as functions into R by identifying 0, 1 ∈ F2
with 0, 1 ∈ R. Then we get or the function f :
sf = 2
i | f(w) 6= f(u(i) ⊕w), i = 1, . . . ,K
= 2−K
(f(w)− f(w⊕ u(i)))2
= 2−K
(f(w) + f(w⊕ u(i))− 2f(w)f(w⊕ u(i))).
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
where u(i) again denotes the unit vector with ith component set to 1. Hence by
the linearity of the expectation
EFK,t(sf ) = 2
EFK,t(f(w)) + EFK,t(f(w ⊕ u
(i)))
− 2EFK,t(f(w)f(w ⊕ u
(i)))
Now we form a matrix with the truth tables of all functions with Hamming
weight t as column vectors:
c(1), c(2), · · · , c((
where c(i) ∈ F2
M has exactly
columns and 2K rows. Each entry Mi,j in the ith row and
jth column equals the value of function fj given the binary representation of i
as input.
Hence EFK,t(f(w)) is determined by the number of 1 in the row associated
with w divided by the length of the row. Consider an arbitrary row i. This row
has a one at position j if the corresponding column c(j) has a one at position i.
But there are
column vectors with a 1 at position i. It follows:
∀w ∈ FK2 : EFK,t(f(w)) =
. (2)
As this holds for all w, we have
∀w,u(i) ∈ FK2 : EFK,t(f(w⊕ u
(i))) =
. (3)
To find an expression for EF fixed
(f(w)f(w⊕u(i))) we consider two arbitrary
rows l,m (l 6= m). Define the following sum:
γl,m =
(Kt )
Ml,iMm,i.
Obviously Ml,iMm,i = 1 only if we have a 1 in both rows at position i. This
means for the column vectors c(i) of M , we have c
m = 1. But there are
exactly
such column vectors in M . Therefore we have
∀l,m, l 6= m : γl,m =
2K − 2
As w 6= w ⊕ u(i) for all w,u(i) it follows:
EFK,t(f(w)f(w ⊕ u
(i))) =
t(t− 1)
2K(2K − 1)
. (4)
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
Hence substituting Equations (2), (3) and (4) into Equation (1) leads to
EFK,t(sf ) =
K(2K − t)t
2K−1(2K − 1)
Finally the claimed expression for EF fixed
(sf ) can be obtained from the above
equation by a substitution of t: t → p2K .
It should be noted, that the Theorems 1 and 2 can be proved using in a
similar way. Also worth noting is the fact, that if the functions are chosen
according FK , F
fixed
K,p or FK,p the expectation of the sensitivity of a fixed vector
w (namely the expectation of sf (w)) is independent of w (see Equation (1),(2),
(3) and (4)). Hence the following lemma holds
Lemma 1. If F = FK , F
fixed
or FK,p, then
∀w,v ∈ FK2 : EF (sf (w)) = EF (sf (v))
Before proceeding to the next section, it should be noted, that using the same
arguments as in the proof of Theorem 3, we can also prove the expectation of
average sensitivity of order l , defined as
s(l)(f) = 2−K
x ∈ FK2 |wH(x) = l and f(w) 6= f(w⊕ x)
In this case, instead of summing up all unit vectors in Equation (1), we sum
up all vectors of Hamming weight l. As the equations (2) and (4) hold for all
w ∈ FK2 we conclude that
E(s(l)(F fixedK,p )) =
2K+1p(1− p)
(2K − 1)
and by similar arguments
E(s(l)(FK,p)) =
2p(1− p)
respectively
E(s(l)(FK)) =
4 Extending Lynch’s analysis
As already mentioned James Lynch gave a very general analysis of randomly
constructed Boolean networks (see [4]). Before stating his results we give a
formal definition for Boolean networks A Boolean network B is a 4-tuple
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
(V,E, F̃ ,x) where V = {1, ..., N} is a set of natural numbers, E is a set of
labeled edges on V , F̃ = {f1, ..., fN} is a ordered set of Boolean functions such
that for each v ∈ V the number of arguments of fv is the in-degree of v in
E, these edges are labeled with 1, ..., in-degree(v), and x = (x1, . . . xn) ∈ F
Suppose that a vertex i has Ki in-edges from vertices vi,1, . . . , vi,Ki . For y ∈ F
we define
B(y) =
f1(yv1,1 , . . . , yv1,K1 ), . . . , fN(yvN,1 , . . . , yvN,KN )
The state of B at time 0 is called the initial state x, so we define B0(x) = x. For
time t ≥ 1 the state is inductively defined as Bt(x) = B(Bt−1(x)). Hence we
can in interpret V as set of gates, E and F̃ describes their functional dependence
and x is the networks initial state.
Assume some ordering f1, f2, ... on the set of all Boolean functions F , where
each function fi depends on Ki arguments. Further a random variable F : Ω →
F with probabilities pi = P (F = fi) such that
i=i pi = 1 and
i=1 piK
∞. Now a random Boolean network consisting of N gates is constructed as
follows: For each gate a Boolean function is chosen independently, where the
probability of choosing fi is given by pi. Suppose a function f was chosen that
has K arguments, these arguments are chosen at random from all
equally
likely possibilities. At last an initial state is chosen at random from the set on
all equally likely states. If the Boolean functions are chosen according to our
previously defined random variable FK we will call this networks NK-Networks
with connectivity K. If the functions are chosen according to F fixedK,p or FK,p
we will call this networks biased random Boolean networks with connectivity K
and fixed bias p respectively mean bias p.
Let us now state Lynch’s results. His analysis depends on a parameter
R ∋ λ ≥ 0 depending only on the functions and their probabilities. We will
define λ later in Definition 3. First we have to state Lynch’s definition of
freezing and ineffective gates:
Definition 2 (Lynch [4] Definition 1 Item 2 and 5).
Let x ∈ FN2 and v ∈ V .
1. Gate v freezes to y ∈ FN2 in t steps on input x if B
v (x) = y for all t
′ ≥ t.
2. Let u(i) ∈ Fn2 .
A gate v is t-ineffective at input x ∈ FK2 if B
t(x) = Bt(x⊕ u(v)).
Now we will state the main result.
Theorem 4 (Lynch [4] Theorem 4 and 6).
Let α, β be positive constants satisfying 2α log δ+2β < 1 and α log δ < β where
δ = E(Ki).
1. There is a constant r such that for all x ∈ FN2
P (v is ineffective in α log N steps) = r
When λ ≤ 1, r = 1 and when λ > 1 , r < 1.
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
2. There is a constant r such that for all x ∈ FN2
P (v is freezing in α log N steps) = r
When λ ≤ 1, r = 1 and when λ > 1 , r < 1. 3
The above theorem shows that if λ ≤ 1 almost all gates are freezing and
ineffective and otherwise not. The next corollary gives us more information
what happens if λ > 1:
Corollary 1 (Lynch [4] Corollary 3 and Corollary 6). Let λ > 1. For almost
all random Boolean networks
1. if gate v is not α logN -ineffective, there is a positive constant W such that
for t ≤ α logN , the number of gates affected by v at time t is asymptotic
to Wλt,
2. if gate v is not freezing in α logN steps , there is a positive constant W
such that for t ≤ α logN , the number of gates that affect v at time t is
asymptotic to Wλt.
Now we will state the definition of λ for Boolean networks:
Definition 3 (Lynch [4], Definition 4). Let f be a Boolean function of K ar-
guments. For i ∈ {1, . . . ,K}, we say that argument i directly affects f on input
w ∈ FK2 if f(w) 6= f(w ⊕ u
(i)). Now put γ(f,w) as the number of i’s that
directly affect f on input w. Given a constant a ∈ [0, 1], we define
γ(fi,w)a
wH(w)(1− a)Ki−wH(w).
Obviously γ(f,w) is identical to sf (w) which will be used instead in the
further discussion. The constant a is the probability that a random gate is one
(at infinite time) given that all gates at time 0 have probability 0.5 of being one.
(see [4, Definiton 2]). Assume that we choose the functions according a random
variable F which should be either FK , F
fixed
K,p or FK,p. The functions are chosen
out the set FK , we denote a function’s probability with pf . It follows that
awH(w)(1− a)K−wH(w)
pfsf (w) (5)
awH(w)(1− a)K−wH(w)E(sF (w)) (6)
= E(sF (w))
ai(1− a)K−i (7)
= E(sF (w)) = EF (sf ) (8)
3Please note that we here state a slightly weaker result than in the original analysis.
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
E(sF (w)) denotes the expectation of the sensitivity for a fixed w, Equation (7)
follows from Lemma 1. Therefore, together with Theorem 1 and Theorem 3 we
proved the following:
Theorem 5 (Biased random Boolean networks). For random Boolean networks,
1. the functions are chosen according random variable FK,p, it follows that
λ = 2Kp(1− p),
2. the functions are chosen according random variable F
fixed
, it follows that
2K+1Kp(1− p)
2K − 1
As a special case of the above theorem we get (or by using Theorem 1)
Theorem 6 (NK-Networks). In random Boolean networks, where the functions
are chosen according to the random variable FK
5 Discussion
The results about NK-Networks are consistent with experimental results. In
fact if K ≤ 2 almost all networks almost all gates are freezing and almost all
gates are ineffective and otherwise not (see [2]).
Obviously, the border between the ordered and disordered phase is given
by λ = 1. The resulting phase diagram for biased random Boolean networks,
where the functions are chosen according to F fixedK,p and FK,p is shown in Figure
1. It it interesting to note that if the functions are chosen with fixed bias, then
also Boolean networks with connectivity K = 2 can become unstable. This
conclusion can be drawn from Lynch’s original result already. As mentioned in
the introduction, he showed for K = 2, that λ > 1 if the probability of choosing
a non-constant non-canalizing function, namely the XOR or the inverted XOR
function, is larger than the probability of choosing a constant function. For
example if the bias is 0.5, the probability of choosing a constant function is
zero, whereas both XOR and inverted XOR function have probability greater
zero, hence λ > 1.
It is interesting to compare our results with previous results obtained first
by Derrida and Pomeau using the so called annealed approximation (see [3]).
In their annealed model the functions and connections are chosen at random
at each time step. Considering two instances of the same annealed network
starting in two randomly chosen initial states s1(0), s2(0) they show that
dH(s1(t), s2(t))
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
1 3 4 52
Figure 1: Phase diagram for biased random networks: Functions chosen accord-
ing FK,p (dashed) and F
fixed
K,p (solid)
where c = 1 if
2Kp(1− p) ≤ 1
and c ≤ 1 otherwise. It is remarkable that the two models behave similar, but
it is unclear whether this holds in general.
6 Acknowledgement
We would like to thank our colleges Georg Schmidt and Stephan Stiglmayr for
proofreading and Uwe Schoening for useful hints.
References
[1] S. Kauffman, Metabolic stability and epigenesis in randomly constructed
nets, Journal of Theoretical Biology 22 (1969) 437–467.
[2] S. Kauffman, The large scale structure and dynamics of genetic control
circuits: an ensemble approach, Journal of Theoretical Biology 44 (1974)
167–190.
[3] B. Derrida, Y. Pomeau, Random networks of automata - a simple annealed
approximation, Europhysics Letters 2 (1986) 45–49.
[4] J. F. Lynch, Dynamics of random boolean networks, in: Conference on
Mathematical Biology and Dynamical Systems, University of Texas at
Tyler, 2005.
DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  DRAFT  --  
[5] J. F. Lynch, On the threshold of chaos in random boolean cellular au-
tomata, Random Structures and Algorithms (1995) 236–260.
[6] J. F. Lynch, Critical points for random boolean networks, Physica D: Non-
linear Phenomena 172 (1-4) (2002) 49–64.
[7] I. Wegener, The Complexity of Boolean Functions, Wiley-Teubner Series
in Computer Science, John Wiley, B.G. Teubner, 1987.
[8] I. Shmulevich, S. A. Kauffman, Activities and sensitivities in boolean net-
work models, Physical Review Letters 93 (4).
[9] S. Kauffman, C. Peterson, B. Samuelsson, C. Troeln, Genetic networks with
canalyzing boolean rules are always stable, Proceedings of the Nationial
Academy of Science 101 (49).
[10] A. Bernasconi, Mathematical techniques for the analysis of boolean func-
tions, Ph.D. thesis, Dipartimento di Informatica, Universita di Pisa (March
1998).
